Por que este trabalho de código Haskell com sucesso com listas infinitas?

Question

Eu tenho algum código Haskell que não trabalho corretamente em uma lista infinita, mas eu não entendo por pode fazê-lo com sucesso. (Eu modifiquei meu código original - que não lidar com listas infinitas - para incorporar algo de algum outro código on-line, e de repente eu ver que ele funciona, mas não sei porquê).

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

O meu entendimento de foldr é que ele irá passar por cada item na lista (e, talvez, que a compreensão é incompleta). Se assim for, não deve importa como a função "passo" é formulada ... o código deve ser incapaz de lidar com loops infinitos.

No entanto, os seguintes trabalhos:

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

Por favor, me ajudar a entender: por que ??

Answer 1

Vamos fazer um pequeno traço em nossas cabeças de como Haskell irá avaliar a sua expressão. Substituindo iguais para iguais em cada linha, a expressão avalia muito rapidamente como 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

Isso funciona porque acc é passado como um thunk unevaluated (avaliação preguiçosa), mas também porque a função || é rigorosa em sua início argumento.

Portanto, este termina:

True || and (repeat True)

Mas isso não:

and (repeat True) || True

Veja a definição de || para ver porque este é o caso:

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

Answer 2

O meu entendimento de foldr é que ele loop de vontade através de cada item no lista (e, talvez, que a compreensão é incompleto).

foldr (foldl ao contrário) não tem que percorrer todos os itens da lista. É instrutivo ver como foldr está definido.

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

Quando uma chamada para foldr é avaliado, ele força a avaliação de uma chamada para o f função. Mas note como a chamada recursiva para foldr é encaixado em um argumento para o f função. Essa chamada recursiva não é avaliado se f não avalia seu segundo argumento.

Answer 3

O ponto chave aqui é que Haskell é uma linguagem não-estrita. "Non-rigorosas" significa que ela permite que as funções não rígidas, que por sua vez significa que os parâmetros de função podem não ser completamente avaliadas antes de poderem ser usadas. Isto, obviamente, permite a avaliação preguiçosa, que é "uma técnica de atrasar um cálculo até que o resultado é exigido".

Iniciar a partir este artigo Wiki

Answer 4

Eu não sei Haskell, mas eu suspeito que no seu caso, ele funciona por causa da avaliação preguiçosa. Porque permite que você trabalhe com lista infinitamente longo, quando você acessá-lo, ele irá calcular o resultado que for necessário.

Consulte http://en.wikipedia.org/wiki/Lazy_evaluation