模式匹配，我無法理解的代碼這個簡單的片斷無限列表

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，這又需要自己的第二個參數進行評估，這是另一個...

好吧，你明白了。第二個不會停下來。