Почему этот код на 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

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

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

True || and (repeat True)

Но это не так:

and (repeat True) || True

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

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

Answer 2

  

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

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 не является строгим. & Quot; нестрогие & Quot; означает, что он допускает нестрогие функции, что, в свою очередь, означает, что параметры функции могут быть оценены не полностью, прежде чем их можно будет использовать. Это, очевидно, допускает ленивую оценку, которая является «техникой задержки вычисления до тех пор, пока не потребуется результат».

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

Answer 4

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

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