模式匹配，我无法理解的代码这个简单的片断无限列表

Question

：

-- This works:  foldr go1 [] [1..] 
-- This doesn't: foldr go2 [] [1..] 

go1 a b = a : b 

go2 a [] = a : [] 
go2 a b = a : b 

与go1折叠马上开始返回值，但go2似乎等待列表的末尾。

很明显，模式匹配导致某些东西被不同地处理。有人可以解释这里究竟发生了什么吗？

Answer 1

与go1不同，go2检查其第二个参数是否为空。为了做到这一点，需要对第二个参数进行评估，至少要确定它是否为空。

因此，对于您的来电foldr这意味着：

两个go1和go2首先调用两个参数：1和foldr go [] [2 ..]结果。在go1的情况下，第二个参数保持不变，因此foldr的结果只是1 :: foldr go [] [2 ..]，而不进一步评估尾部，直到它被访问。

然而在go2的情况下，需要评估foldr go [] [2 ..]以检查它是否为空。要做到这一点foldr go [] [3 ..]然后需要评估出于同样的原因。等无止境。

Answer 2

这是因为懒惰....由于本示例中定义了go1和go2的方式，它们的行为与b==[]的行为完全相同，但编译器不知道这一点。

对于go1，最左边的折叠将使用尾递归来立即输出a的值，然后计算b的值。

go1 a b -> create and return the value of a, then calculate b 

对于go2，编译器甚至不知道要匹配的情况下，直至b值计算....这永远不会发生。

go2 a b -> wait for the value of b, pattern match against it, then output a:b 

Answer 3

要测试一个表达式是否满足某种模式，至少需要将其评估为弱头法线形式。因此模式匹配力评估。 一个常见的例子是交织两个列表的interleave函数。它可以像

interleave :: [a] -> [a] -> [a] 
interleave xs  [] = xs 
interleave []  ys = ys 
interleave (x:xs) (y:ys) = x : y : interleave xs ys 

但是这个函数在第二个参数中是严格的。而更懒的版本是

interleave [] ys = ys 
interleave (x:xs) ys = x : interleave ys xs 

你可以在这里阅读更多：http://en.wikibooks.org/wiki/Haskell/Laziness

Answer 4

要看到差距试试这个在GHCI：

> head (go1 1 (error "urk!")) 
1 
> head (go2 1 (error "urk!")) 
*** Exception: urk! 

的问题是，go2将之前评估其第二个参数返回列表的头部。即go2是严格在其第二个参数，不像go1这是懒惰。

当你折叠了无限的名单这一点很重要：

fold1 go1 [] [1..] = 
go1 1 (go1 2 (go1 3 (..... = 
1 : (go1 2 (go1 3 (..... = 
1 : 2 : (go1 3 (... 

工作正常，但

fold1 go1 [] [1..] = 
go2 1 (go2 2 (go2 3 (..... 

不能因为go2评估其第二个参数，这是另一个呼叫坚持简化为1:...到go2，这又需要自己的第二个参数进行评估，这是另一个...

好吧，你明白了。第二个不会停下来。