为什么总和可以在代数数据类型中视为正常形式?

问题描述 投票:0回答:1

我正在读取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。我不明白为什么乘积和基数与正常形式有关。

haskell functional-programming algebraic-data-types
1个回答
0
投票

让我们声明一些代表数字的类型:

data Two = OneOfTwo | TwoOfTwo
data Three = OneOfThree | TwoOfThree | ThreeOfThree
data Four = ... (similar)

现在我们可以看到类型Two的可能值的数量实际上是2。与ThreeFourSeven相同。

现在,如果我们构造求和类型:

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的可能值的数量是TwoB的可能组合的数量,正如我们从中学数学中知道的那样,这将是它们的乘积或2 * (3 + 4) = 2 * (7) = 14

但是这是窍门:我们可以用其他方式写下equivalent类型:

data CNew = C1 Two Three | C2 Two Four

看看我在那里做什么?对于CNewTwoThreeFour的值之间所有可能组合的集合与C相同。看:在两种情况下,它要么是Two的值与Three的值相结合,要么是Two的值与Four的值相结合。除了在CNew中直接合并外,在C中它们通过B合并。

但是CNew的公式将不同:2 * 3 + 2 * 4 = (6) + (8) = 14。这就是书的意思。

现在更直接回答这个问题:

乘积之和(2 * 3 + 2 * 4)是正常形式吗?该表达可以进一步减少,因为完全减少的表达将是14

如果我们要处理整数,这是正确的,但事实并非如此。我们可以用C的形式重写CNew,因为这给了我们所有相同的可能值组合。但是,如果不组合234,就不能将它们重写为具有14个可能的值的类型。与TwoThreeFour的组合相反,这将是一个全新的,无关的类型。

以及可能的术语误解:

乘积之和(2 * 3 + 2 * 4)是正常形式吗?

术语“正常形式”并不表示“最短形式”。该术语通常用于表示一种非常规则的形式,因此更易于使用,并且至关重要的是,它可以表示域中所有可能的情况。在这种情况下,标准格式定义为“产品总和”。

它不是“和的乘积”吗?不,这不可能,因为虽然和的乘积可以总是

转换为乘积的和,但并非总是可能相反,这意味着并非每种可能的类型都可以用正常形式表示定义为“总和”。

14一样,可能只是“可能值的数量”吗?再一次不,因为转换为这种形式会丢失一些信息(请参见上文)。

© www.soinside.com 2019 - 2024. All rights reserved.