Почему этот Haskell кодирует работу успешно с бесконечными списками?
Сложнее управлять? Да, но не медленнее. Буферизованные очереди реализованы в виде циклических буферов (см. Java-массив ArrayDeque), что увеличивает сложность, но вставка и удаление даже для deque требует O (1).
Разница возникает, когда буфер должен быть перераспределен. В очереди (или, вообще говоря, в кольцевом буфере) вам может потребоваться сместить много элементов (по крайней мере, вы не смещаете все элементы в каждой вставке), и в стеке вам никогда не понадобится это делать.
Если вы создаете циклический буфер, вы можете использовать его как стек, очередь и деку.
4 ответа
Let's do a little trace in our heads of how Haskell will evaluate your expression. Substituting equals for equals on each line, the expression pretty quickly evaluates to 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
This works because acc is passed as an unevaluated thunk (lazy evaluation), but also because the || function is strict in its first argument.
So this terminates:
True || and (repeat True)
But this does not:
and (repeat True) || True
Look at the definition of || to see why this is the case:
True || _ = True
False || x = x
Я понимаю, что это фолдер будет проходить через каждый элемент в список (и, возможно, это понимание является неполным).
foldr (в отличие от foldl ) не должен перебирать все элементы списка. Поучительно посмотреть, как определяется foldr .
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
Когда вычисляется вызов foldr , он вызывает оценку вызова функции f . Но обратите внимание, как рекурсивный вызов foldr встроен в аргумент функции f . Этот рекурсивный вызов не оценивается, если f не оценивает его второй аргумент.
The key point here is that Haskell is a non-strict language. "Non-strict" means that it allows non-strict functions, which in turn means that function parameters may not be fully evaluated before they may be used. This obviously allows for lazy evaluation, which is "a technique of delaying a computation until the result is required".
Start from this Wiki article
I do not know Haskell, but I suspect that in your case, it works because of lazy evaluation. Because it allows you to work with list infinitely long, when you access it, it will compute the result as you need it.