为什么乘积总和可以被视为代数数据类型中的标准形式？

Question

我正在阅读一本Haskell 书（第 412 页）。在本书中，对积和的范式有一个解释：

所有现有的乘积和和的代数规则都适用于类型系统，其中包括分配属性。让我们来看看它在算术中是如何工作的：

2 * (3 + 4)
2 * (7)
14

我们可以用分布在加法上的乘法重写它并获得相同的结果：

2 * 3 + 2 * 4
(6) + (8)
14

这被称为“乘积总和”。在普通算术中，表达式在被简化为最终结果时是普通形式。但是，如果您将上述表达式中的数字视为集合基数的表示，那么乘积之和表达式就是正常形式，因为不需要执行计算。

我知道正常形式表示表达式完全减少。在上面的描述中，该书的作者解释说，当我们将表达式视为集合基数的表示时，可以将乘积之和视为正常形式。我不明白。

类型的基数意味着该类型（如集合）中可以包含多少个不同的值。例如，Bool输入 haskell 的基数为2，即加 1 forFalse和 1 for Trueeach。

乘积之和 ( 2 * 3 + 2 * 4) 是正规形式吗？该表达式可以进一步减少，因为完全减少的表达将是14。我不明白为什么乘积和它的基数与正常形式有关。

Answer 1

让我们声明一些类型来表示数字：

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

现在我们可以看到 type 的可能值的数量Two实际上是2。同为Three，Four和Seven。

现在，如果我们构造一个 sum 类型：

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。

但这里有一个技巧：我们可以用不同的方式写出一个等价的类型：

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，因为这为我们提供了所有可能的值组合。但是，我们不能重写他们作为具有直上14个可能的值，而不结合型2，3和4。这将是一个全新的，无关的类型，而不是组合Two，Three和Four。

还有一个可能的术语误解：

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

术语“正常形式”并不意味着“最短”。该术语通常用于表示非常规则的形式，因此更易于使用，并且至关重要的是，它可以表示域中所有可能的情况。在这种情况下，范式被定义为“乘积之和”。

它可能是“总和的乘积”吗？不，它不能，因为，虽然总和的乘积总是可以转换为乘积的总和，但反过来并不总是可能的，这意味着并非所有可能的类型都可以用定义为“乘积”的标准形式表示总和”。

可能是“可能值的数量”，比如14？再次不，因为转换为这种形式会丢失一些信息（见上文）。