соответствия шаблона и бесконечные списки

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 (..... 

не может быть упрощено до 1:..., поскольку go2 настаивает на оценке ее второй аргумент, который является еще один вызов до go2, который, в свою очередь, требует оценки своего второго аргумента, который является другим ...

Ну, вы понимаете. Второй не остановится.