函数内部的非穷举模式

Question

我目前正致力于解决问题62

我尝试了以下代码来解决它:

data Tree a = Empty | Branch a (Tree a) (Tree a)
              deriving (Show, Eq)

internals :: Tree a -> [a]

internals (Branch a Empty Empty) = []

internals (Branch a b c) = [a]++(internals b)++(internals c)

internals (Branch a b Empty) = [a]++(internals b)

internals (Branch a Empty c) = [a]++(internals c)

基本上说:

1. 如果两个子项都为空,则不在内部列表中包含该列表元素.
2. 如果两个子节点都是非空的,那么node(a)是一个内部包含它,并继续检查以查看任何子节点a也是内部的.
3. 如果其中一个子节点非空,则该节点是内部节点,并递归地检查子节点是否也是内部节点.

在GHCi中,我运行了以下内容:

> let tree4 = Branch 1 (Branch 2 Empty (Branch 4 Empty Empty)) (Branch 2 Empty Empty)
> internals tree4

并获得以下运行时错误:

[1,2*** Exception: Untitled.hs:(6,1)-(12,49): Non-exhaustive patterns in function internals

我不明白为什么这个东西是非详尽的,我以为它会去分支1,注意它的孩子是非空的,然后往两个分支2下去,发现一个分支是空的,一个不是,停在那是一个,并继续沿着那个没有的那个,直到分支"4",然后在那里结束.它确实如此,我在列表中得到1,2,但为什么它不详尽？

提前致谢.

谢谢你帮助Tikhon将我的功能改为:

data Tree a = Empty | Branch a (Tree a) (Tree a)
              deriving (Show, Eq)

internals :: Tree a -> [a]

internals (Branch a Empty Empty) = []

internals (Branch a b Empty) = [a]++(internals b)

internals (Branch a Empty c) = [a]++(internals c)

internals (Branch a b c) = [a]++(internals b)++(internals c)

Answer 1

另一个答案实际上并没有解决错误消息的原因,它确实解决了一个问题(模式的顺序很重要).

错误消息是Non-exhaustive patterns,这意味着internals正在调用一个与任何模式都不匹配的值(此值为Empty).正如Tikhon所说,这是因为Branch a b c匹配所有分支,因此后来的模式从未使用过,而且Empty可以通过.我们可以看到如果我们跟踪执行会发生什么internals (Branch 1 (Branch 2 Empty Empty) Empty)(假设严格的评估,它使得说明更简单):

internals (Branch 1 (Branch 2 Empty Empty) Empty) =>
[1] ++ internals (Branch 2 Empty Empty) ++ internals Empty =>
[1] ++ [] ++ internals Empty =>
[1] ++ internals Empty =>
[1] ++ ???

正确的修复将意味着不会发生,即internals从部分函数(对于某些输入值未定义)转换为总函数(为所有输入定义).总的功能是多得多不是部分的人更好的,特别是在Haskell,其中类型系统为程序员提供了标记在编译时"部分"用作这样的能力(例如,经由Maybe或Either).

我们可以考虑自下而上的递归,即计算出基本情况:

• 空树没有内部节点
• 作为单个节点的树没有内部节点

我们反复出现任何不满足这些要求的树; 在这种情况下,当前节点是一个内部节点(所以将其添加到列表中),并且子节点中可能有内部节点,因此也要检查它们.

我们可以在Haskell中表达这个:

internals :: Tree a -> [a]

internals Empty = [] 
internals (Branch a Empty Empty) = []

internals (Branch a b c) = [a] ++ internals b ++ internals c

这有使得代码更整洁更短的额外好处:我们不必担心递归中子节点的细节,有一个处理任何Emptys 的基本情况.

Answer 2

模式的顺序很重要.由于Branch a b c匹配不仅仅Empty包括类似的东西Branch a b Empty,你的第三和第四个案例永远不会被击中.

这应该解决它:

internals :: Tree a -> [a]
internals (Branch a Empty Empty) = []
internals (Branch a b Empty)     = [a] ++ internals b
internals (Branch a Empty c)     = [a] ++ internals c
internals (Branch a b c)         = [a] ++ internals b ++ internals c