我正在读取haskell book(第412页)。本书对乘积和的正规形式进行了解释:
[产品和和的所有现有代数规则都适用于类型系统,其中包括分布属性。让我们看看它在算术中是如何工作的:
2 * (3 + 4)
2 * (7)
14
我们可以用加法器上的乘法重写它,并获得相同的结果:
2 * 3 + 2 * 4
(6) + (8)
14
这被称为“乘积之和。”在常规算术中,当将表达式简化为最终结果时,该表达式为正则形式。但是,如果您将上述表达式中的数字视为集合基数的表示,则乘积之和的表达式为标准形式,因为没有要执行的计算。
我知道,正常形式可以使表达式完全被简化。在上面的描述中,这本书的作者解释说,当我们将表达式视为集合基数的表示形式时,可以将乘积之和视为正常形式。我不明白。
类型的基数表示该类型(如集合)中可以包含多少个不同的值。例如,haskell中的Bool
类型具有2
的基数,即False
分别加1,True
分别加1。
乘积之和(2 * 3 + 2 * 4
)是否为正常形式?该表达可以进一步降低,因为完全降低的表达为14
。我不明白为什么乘积和基数与正常形式有关。
让我们声明一些代表数字的类型:
data Two = OneOfTwo | TwoOfTwo
data Three = OneOfThree | TwoOfThree | ThreeOfThree
data Four = ... (similar)
现在我们可以看到类型Two
的可能值的数量实际上是2
。与Three
,Four
和Seven
相同。
现在,如果我们构造求和类型:
data A = A Two
[此类型仅将Two
的值自动换行,因此A
的可能值的数量也为2
。到目前为止一切顺利吗?
现在让我们构造一个更复杂的一个:
data B = B1 Three | B2 Four
现在,此类型包装任一类型为Three
的值或类型为Four
的值(但不能同时包含两者!)这意味着可能值的数量应为是3 + 4
。至今为止吗?
现在,进一步:
data C = C Two B
此类型包装两个值同时-一个Two
类型的值和一个B
类型的值。这意味着C
的可能值的数量是Two
和B
的可能组合的数量,正如我们从中学数学中知道的那样,这将是它们的乘积或2 * (3 + 4) = 2 * (7) = 14
。
但是这是窍门:我们可以用其他方式写下equivalent类型:
data CNew = C1 Two Three | C2 Two Four
看看我在那里做什么?对于CNew
,Two
,Three
和Four
的值之间所有可能组合的集合与C
相同。看:在两种情况下,它要么是Two
的值与Three
的值相结合,要么是Two
的值与Four
的值相结合。除了在CNew
中直接合并外,在C
中它们通过B
合并。
但是CNew
的公式将不同:2 * 3 + 2 * 4 = (6) + (8) = 14
。这就是书的意思。
现在更直接回答这个问题:
乘积之和(2 * 3 + 2 * 4)是正常形式吗?该表达可以进一步减少,因为完全减少的表达将是14
如果我们要处理整数,这是正确的,但事实并非如此。我们可以用C
的形式重写CNew
,因为这给了我们所有相同的可能值组合。但是,如果不组合2
,3
和4
,就不能将它们重写为具有14个可能的值的类型。与Two
,Three
和Four
的组合相反,这将是一个全新的,无关的类型。
以及可能的术语误解:
乘积之和(2 * 3 + 2 * 4)是正常形式吗?
术语“正常形式”并不表示“最短形式”。该术语通常用于表示一种非常规则的形式,因此更易于使用,并且至关重要的是,它可以表示域中所有可能的情况。在这种情况下,标准格式定义为“产品总和”。
它不是“和的乘积”吗?不,这不可能,因为虽然和的乘积可以总是
转换为乘积的和,但并非总是可能相反,这意味着并非每种可能的类型都可以用正常形式表示定义为“总和”。像14
一样,可能只是“可能值的数量”吗?再一次不,因为转换为这种形式会丢失一些信息(请参见上文)。