haskell - 理解代数数据类型的困难

Question

我不太确定这个 ZInt 实际描述的是什么。

data Nat = Zero | S Nat
data ZInt = Z Nat Nat deriving Show

addZ :: ZInt -> ZInt -> ZInt
addZ (Z a b) (Z c d) = Z (add a c) (add b d)

with
add ::  Nat -> Nat -> Nat
add a Zero  = a
add a (S b) = S (add a b)

mult :: Nat -> Nat -> Nat
mult _ Zero  = Zero
mult a (S b) = add a (mult a b)

乍一看，我认为这可能是复数的表示，添加虚数和实数分量(在函数 addZ 中)，而不显示

a+b*i

但是这个函数中发生了什么？

 subZ :: ZInt -> ZInt -> ZInt 
 subZ (Z a b) (Z c d) = Z (add a d) (add b c)

multZ :: ZInt -> ZInt -> ZInt
multZ (Z a b) (Z c d) = Z (add (mult a d) (mult c b)) (add (mult a c) (mult b d))

所以我确实理解数据 Nat = 0 | S Nat 以及 add 和 mult 函数，但不包括 addZ、subZ 和 multZ。

Answer 1

这只是整数。 Nat 表示自然数。 ZInt 表示整数。在 Z a b 中，如果 a >= b 则整数为 a - b，否则为 -(b - a)。

例如:

ZInt representation | Traditional representation
Z Zero Zero         | 0
Z (S Zero) Zero     | 1
Z Zero (S Zero)     | -1
Z (S Zero) (S Zero) | 0
...

正如我们所见，要求反一个整数，只需交换其表示形式中的Nat值即可:

negate :: ZInt -> ZInt
negate (Z n m) = Z m n

我们可以这样定义subZ:

a `subZ` b = a `addZ` negate b

这种表示形式并不规范，Z (S Zero) (S Zero) 与 Z Zero Zero 是相同的整数。因此，我们可以这样定义规范形式:

canonical :: ZInt -> ZInt
canonical (Z (S n) (S m)) = canonical (Z n m)
canonical x               = x

为什么要这样定义整数？

首先，它在数学上是清楚的。如果有人定义了名为 N 的自然数集合，我们可以轻松地将名为 Z 的整数集合定义为 Z = N * N 其中 ( *) 是两组的乘积。

在 Haskell 中，我只能看到一个原因。通过这种方式，我们可以在类型级别上定义整数。