Почему этот код Haskell успешно работает с бесконечными списками?

Question

У меня есть код Haskell, который делает работает правильно в бесконечном списке, но я не понимаю , почему он может сделать это успешно. (Я изменил свой исходный код, который не обрабатывал бесконечные списки, - чтобы включить что-то из какого-либо другого кода в Интернете, и вдруг я вижу, что он работает, но не знает почему).

myAny :: (a -> Bool) -> [a] -> Bool 
myAny p list = foldr step False list 
    where 
     step item acc = p item || acc 

Мое понимание foldr является то, что он будет цикл через каждый элемент списка (и, возможно, что понимание является неполным). Если это так, не имеет значения, как выражается функция «шаг» ... код не должен обрабатывать бесконечные циклы.

Однако следующие работы:

*Main Data.List> myAny even [1..] 
True 

Пожалуйста, помогите мне понять: почему ??

Answer 1

Давайте сделаем небольшой след в наших головах того, как Haskell будет оценивать ваше выражение. Подставив равно для равных по каждой строке, выражение довольно быстро вычисляется в True:

myAny even [1..] 
foldr step False [1..] 
step 1 (foldr step False [2..]) 
even 1 || (foldr step False [2..]) 
False || (foldr step False [2..]) 
foldr step False [2..] 
step 2 (foldr step False [3..]) 
even 2 || (foldr step False [3..]) 
True || (foldr step false [3..]) 
True 

Это работает, потому что acc передается как невычисленный стук (ленивая оценка), но и потому, что функция || строго в его первого аргумент.

Так это заканчивается:

True || and (repeat True) 

Но это вовсе не так:

and (repeat True) || True 

Посмотрите на определение || чтобы понять, почему это так:

True || _ = True 
False || x = x 

Answer 2

Ключевым моментом здесь является то, что Haskell является нестрогим языком. «Нестрогий» означает, что он позволяет выполнять нестрогие функции, что, в свою очередь, означает, что параметры функции могут не полностью оцениваться до их использования. Это, очевидно, допускает ленивую оценку, которая является «методом задержки вычисления, пока результат не потребуется».

Начинает this Wiki article

Answer 3

Я не знаю Haskell, но я подозреваю, что в вашем случае, это работает из-за ленивую оценку. Поскольку он позволяет работать со списком бесконечно долго, когда вы обращаетесь к нему, он будет вычислять результат по мере необходимости.

См http://en.wikipedia.org/wiki/Lazy_evaluation

Answer 4

Мое понимание foldr является то, что она будет цикл по каждому элементу в списке (и, возможно, что понимание является неполным).

foldr (в отличие от foldl) не Переберите каждый элемент списка. Поучительно посмотреть, как определяется foldr.

foldr f z []  = z 
foldr f z (x:xs) = f x (foldr f z xs) 

Когда вызов foldr оценивается, она заставляет оценку вызова функции f. Но обратите внимание, как рекурсивный вызов foldr встроен в аргумент функции f. Этот рекурсивный вызов не оценивается, если f не оценивает свой второй аргумент.