如果没有我们在数据类型上定义Eq,Haskell如何进行模式匹配？

Question

我已经定义了一个二叉树:

data Tree = Null | Node Tree Int Tree

并实现了一个函数,它将产生所有节点的值的总和:

sumOfValues :: Tree -> Int
sumOfValues Null = 0
sumOfValues (Node Null v Null) = v
sumOfValues (Node Null v t2) = v + (sumOfValues t2)
sumOfValues (Node t1 v Null) = v + (sumOfValues t1)
sumOfValues (Node t1 v t2) = v + (sumOfValues t1) + (sumOfValues t2)

它按预期工作.我有想法也尝试使用警卫来实现它:

sumOfValues2 :: Tree -> Int
sumOfValues2 Null = 0
sumOfValues2 (Node t1 v t2)
    | t1 == Null && t2 == Null  = v
    | t1 == Null            = v + (sumOfValues2 t2)
    |               t2 == Null  = v + (sumOfValues2 t1)
    |   otherwise       = v + (sumOfValues2 t1) + (sumOfValues2 t2)

但是这个没有用,因为我没有实施Eq,我相信:

No instance for (Eq Tree)
  arising from a use of `==' at zzz3.hs:13:3-12
Possible fix: add an instance declaration for (Eq Tree)
In the first argument of `(&&)', namely `t1 == Null'
In the expression: t1 == Null && t2 == Null
In a stmt of a pattern guard for
             the definition of `sumOfValues2':
        t1 == Null && t2 == Null

那么,必须要做的问题是,Haskell如何在不知道何时传递的参数匹配的情况下进行模式匹配,而不是诉诸于Eq？

编辑

你的论证似乎围绕着这样一个事实:Haskell确实没有比较函数的参数,而是在"形式"和签名类型上知道要匹配哪个子函数.但是这个怎么样？

f :: Int -> Int -> Int
f 1 _ = 666
f 2 _ = 777
f _ 1 = 888
f _ _ = 999

在运行时f 2 9,是否必须使用Eq才能知道哪个子功能是正确的？所有这些都是相同的(与我的Tree/Node/Null时的初始Tree示例相反).或者是Int类似的东西的实际定义

data Int = -2^32 | -109212 ... | 0 | ... +2^32 

？

Answer 1

对于模式匹配,Haskell使用值的结构和使用的构造函数.例如,如果您评估

sumOfValues (Node Null 5 (Node Null 10 Null))

它从上到下检查模式:

• 第一个,Null因为它有不同的结构,所以不匹配

• 第二个,(Node Null v Null)不匹配,因为最后一个组件Null,具有不同的结构(Node Null 10 Null)(模式匹配递归)

• 第三个匹配v绑定到5并t2绑定到(Node Null 10 Null).

Eq它定义的==运算符是一个不相关的机制; 制作Tree一个实例Eq不会改变模式匹配的工作方式.

我认为你的想法有点落后:模式匹配是在Haskell中使用值的最基本方式; 除了一些基本类型之外Int,Eq是使用模式匹配实现的,而不是相反.

模式匹配和数字

事实证明,数字文字是一种特殊情况.根据Haskell报告(链接):

如果v == k,则将数字,字符或字符串文字模式k与值v匹配成功,其中==基于模式的类型重载.

Answer 2

Haskell知道使用什么类型的构造函数来构造特定的实例,这就是为了成功模式匹配所需要的全部内容.

Answer 3

你缺少的是你假设Null是一些像C或Java一样的常量值.它不是 - 它是Tree类型的构造函数.

模式匹配反向构建.您不是向构造函数提供两个值,而是为您提供适当类型的值,而是为构造函数提供类型的值,并为您提供构成该类型的组成值.语言知道区分联合的哪个分支用于构造值,因此它可以匹配正确的模式.因此,不需要相等,因为它只是构造函数和变量 - 没有实际值进行比较(或者甚至必须进行评估).

关于你对Ints的编辑:

是的,Int基本上是一个类型,其中包含大量的构造函数-2 | -1 | 0 | 1 | 2 | 3 | 4 ….它有点手工,但它在实践中有效.