Haskell如何在没有我们的数据类型定义Eq的情况下进行模式匹配？ [英] How does Haskell do pattern matching without us defining an Eq on our data types?
问题描述
数据Tree = Null |节点树Int Tree
并且已经实现了一个函数，该函数将产生所有它的值的总和节点：$ b
$ b
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（节点t1 v t2）
| t1 ==空&& t2 == Null = v
| t1 == Null = v +（sumOfValues2 t2）
| t2 == Null = v +（sumOfValues2 t1）
|否则= v +（sumOfValues2 t1）+（sumOfValues2 t2）
但这个不起作用，因为我还没有执行 Eq ，我相信：
在zzz3.hs：13：3-12
使用'=='没有引发（Eq Tree）
的实例可能的修正：为（Eq Tree）
在'（&& amp;）'的第一个参数中，即't1 == Null'
在表达式中：t1 == Null&& t2 == Null
在
的模式守卫的stmt中，`sumOfValues2'的定义：
t1 == Null&& t2 ==空
必须提出的问题， ，Haskell如何在不知道传递参数匹配的情况下进行模式匹配，而不诉诸 Eq ？
编辑
你的论点似乎围绕这样的事实：Haskell确实没有比较函数的参数，而是在形式和类型的签名上知道哪个子功能匹配。但如何呢？
f :: Int - > Int - > Int
f 1 _ = 666
f 2 _ = 777
f _ 1 = 888
f _ _ = 999
运行 f 2 9 时，是不是必须使用 Eq 知道哪一个子功能是正确的？所有这些都是平等的（与我们最初的树例子有树/节点/空）相反。或者是 Int的实际定义
$ b
data Int = -2 ^ 32 | -109212 ... | 0 | ... + 2 ^ 32
？
sumOfValues（节点空5（节点空10空））
$ b 它从上到下检查模式：
-
第一个 Null 不匹配，因为它具有不同的结构
- 第二个元素
（Node Null v Null）不匹配，因为最后一个元素 Null ，具有与不同的结构（节点空10空）（模式匹配以递归方式进行） 第三部分一个与绑定到5的 v 匹配并且绑定到（节点为空10空）的 t2 。
Eq 它定义的==运算符是一个不相关的机制;使得树 Eq 的实例不会改变模式匹配的工作方式。
我认为您的想法有点落后：模式匹配是在Haskell中使用值的最基本方式;除了像 Int ， Eq 这样的基本类型之外，它是通过模式匹配来实现的，而不是相反。
模式匹配和数字
原来数字文字是一种特殊情况。根据Haskell报告（链接）：
匹配值 v 的数字，字符或字符串文字模式 k 如果 v == k ，其中==根据模式的类型重载。
I have defined a binary tree:
data Tree = Null | Node Tree Int Tree
and have implemented a function that'll yield the sum of the values of all its nodes:
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)
It works as expected. I had the idea of also trying to implement it using guards:
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)
but this one doesn't work because I haven't implemented Eq, I believe:
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
The question that has to be made, then, is how can Haskell make pattern matching without knowing when a passed argument matches, without resorting to Eq?
Edit
Your arguments seem to revolve around the fact that Haskell is not indeed comparing the arguments of the function, but instead on the "form" and types of signature to know which sub-function to match. But how about this?
f :: Int -> Int -> Int
f 1 _ = 666
f 2 _ = 777
f _ 1 = 888
f _ _ = 999
When running f 2 9, won't it have to use Eq to know which one of the subfunctions is the right one? All of them are equal (contrary to my initial Tree example when we had Tree/Node/Null). Or is the actual definition of an Int something like
data Int = -2^32 | -109212 ... | 0 | ... +2^32
?
解决方案 For pattern matching, Haskell uses the structure of the value and the constructors used. For example, if you evaluate
sumOfValues (Node Null 5 (Node Null 10 Null))
it checks the patterns from top to bottom:
the first one, Null, doesn't match because it has a different structure
the second one, (Node Null v Null), doesn't match because the last component, Null, has a different structure than (Node Null 10 Null) (pattern matching proceeds recursively)
the third one matches with v bound to 5 and t2 bound to (Node Null 10 Null).
Eq and the == operator it defines are an unrelated mechanism; making Tree an instance of Eq won't change how pattern matching works.
I think your thinking here is a bit backward: Pattern matching is the most basic way of using a value in Haskell; except for some basic types like Int, Eq is implemented using pattern matching, not the other way around.
Pattern matching and numbers
It turns out numeric literals are a special case. According to the Haskell report (link):
Matching a numeric, character, or string literal pattern k against a value v succeeds if v == k, where == is overloaded based on the type of the pattern.
这篇关于Haskell如何在没有我们的数据类型定义Eq的情况下进行模式匹配？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
