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

У меня есть код 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

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

Ответ 1

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

Итак, это завершает:

True || and (repeat True)

Но это не так:

and (repeat True) || True

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

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

Ответ 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 не оценивает свой второй аргумент.

Ответ 3

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

Начните с эту статью Wiki

Ответ 4

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

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