Почему этот код на Haskell успешно работает с бесконечными списками?
У меня есть некоторый код на Haskell, который правильно работает с бесконечным списком, но я не понимаю, почему он может делать это успешно. (Я изменил свой исходный код - который не обрабатывал бесконечные списки - чтобы включить что-то из какого-то другого кода в сети, и вдруг я вижу, что он работает, но не знаю почему).
myAny :: (a -> Bool) -> [a] -> Bool
myAny p list = foldr step False list
where
step item acc = p item || acc
Я понимаю, что foldr будет циклически проходить по каждому пункту в списке (и, возможно, это понимание неполное). Если так, то не должно иметь значения, как сформулирована функция "step"... код не должен обрабатывать бесконечные циклы.
Тем не менее, следующие работы:
*Main Data.List> myAny even [1..]
True
Пожалуйста, помогите мне понять: почему??
4 ответа
Давайте сделаем небольшой след в наших головах о том, как Хаскелл оценит ваше выражение. Подставляя 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 (ленивая оценка), но также потому, что || функция является строгой в своем первом аргументе.
Так что это заканчивается:
True || and (repeat True)
Но это не так:
and (repeat True) || True
Посмотрите на определение || чтобы понять, почему это так:
True || _ = True
False || x = x
Я понимаю, что foldr будет циклически проходить по каждому пункту в списке (и, возможно, это понимание неполное).
foldr (В отличие от foldl) не нужно перебирать каждый элемент списка. Поучительно посмотреть на то, как foldr определено.
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
Когда звонок в foldr оценивается, это вызывает оценку вызова функции f, Но обратите внимание, как рекурсивный вызов foldr встроен в аргумент функции f, Этот рекурсивный вызов не оценивается, если f не оценивает свой второй аргумент.
Я не знаю Haskell, но подозреваю, что в вашем случае это работает из-за ленивой оценки. Поскольку он позволяет работать со списком бесконечно долго, при обращении к нему он будет вычислять результат по мере необходимости.
Ключевым моментом здесь является то, что Haskell - не строгий язык. "Нестрогий" означает, что он допускает нестрогие функции, что, в свою очередь, означает, что параметры функции могут быть оценены не полностью, прежде чем их можно будет использовать. Это, очевидно, допускает ленивую оценку, которая является "техникой задержки вычислений до тех пор, пока не потребуется результат".
Начните с этой статьи Wiki