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

Question

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

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

Насколько я понимаю, свёртка заключается в том, что она будет проходить по всем пунктам в списке (и, возможно, это понимание неполное). Если это так, то не должно иметь значения, как сформулирована функция «step» ... код не должен обрабатывать бесконечные циклы.

Тем не менее, следующие работы:

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

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

Answer 1

Давайте сделаем небольшой след в наших головах о том, как Хаскелл оценит ваше выражение. Подставляя equals для equals в каждой строке, выражение довольно быстро оценивается как 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 передается как неоцененный thunk (ленивая оценка), а также потому, что функция || строга в своем аргументе first .

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

True || and (repeat True)

Но это не так:

and (repeat True) || True

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

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

Answer 2

Я понимаю, что это фолдр будет перебирать каждый элемент в список (и, возможно, это понимание является неполным).

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

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

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

Answer 3

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

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

Answer 4

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

Начните с этой статьи в вики