O código para a função myAny nesta pergunta usa foldr. Para de processar uma lista infinita quando o predicado é satisfeito.
Eu o reescrevi usando foldl:
myAny p list = foldl step False list
step acc item = p item || acc
(Observe que os argumentos para a função de etapa foram revertidos corretamente.)
No entanto, ele não pára mais de processar listas infinitas.
Tentei rastrear a execução da função como na resposta do Apocalisp :
foldl step False [1..]
step (foldl step False [2..]) 1
even 1 || (foldl step False [2..])
False  || (foldl step False [2..])
foldl step False [2..]
step (foldl step False [3..]) 2
even 2 || (foldl step False [3..])
True   || (foldl step False [3..])
No entanto, não é assim que a função se comporta. Como isso está errado?
haskell lazy-evaluation combinators fold
Como foldas diferenças parecem ser uma fonte frequente de confusão, então aqui está uma visão geral:
Considere dobrar uma lista de n valores [x1, x2, x3, x4 ... xn ]com alguma função fe semente z.
foldl é:
Associativo esquerdo :f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
Cauda recursiva : itera pela lista, produzindo o valor posteriormente
Preguiçoso : nada é avaliado até que o resultado seja necessário
Para trás : foldl (flip (:)) []inverte uma lista.
foldr é:
Associativo certo :f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))
Recursivo em um argumento : cada iteração se aplica fao próximo valor e ao resultado de dobrar o restante da lista.
Encaminha :foldr (:) [] retorna uma lista inalterada.
Há um ponto ligeiramente sutil aqui que as viagens de pessoas até às vezes: Porque foldlé para trás de cada aplicação de fé adicionada ao lado de fora do resultado; e por ser preguiçoso , nada é avaliado até que o resultado seja necessário. Isso significa que, para calcular qualquer parte do resultado, Haskell primeiro percorre toda a lista, construindo uma expressão de aplicativos de funções aninhadas, depois avalia a função mais externa , avaliando seus argumentos conforme necessário. Se fsempre usa seu primeiro argumento, isso significa que Haskell deve recorrer até o termo mais interno e, em seguida, trabalhar com computação inversa de cada aplicativo f.
Obviamente, isso está muito longe da eficiente recursão da cauda que a maioria dos programadores funcionais conhece e ama!
De fato, embora foldlseja tecnicamente recursivo da cauda, ​​porque toda a expressão do resultado é criada antes de avaliar qualquer coisa, foldlpode causar um estouro de pilha!
Por outro lado, considere foldr. Também é preguiçoso, mas, como é executado em frente , cada aplicativo de fé adicionado à parte interna do resultado. Portanto, para calcular o resultado, Haskell constrói um aplicativo de função única , cujo segundo argumento é o restante da lista dobrada. Se ffor preguiçoso em seu segundo argumento - um construtor de dados, por exemplo - o resultado será incrementalmente preguiçoso , com cada etapa da dobra calculada apenas quando parte do resultado que precisa dele for avaliada.
Assim, podemos ver por que foldràs vezes funciona em listas infinitas quando foldlnão funciona: a primeira pode converter uma lista infinitamente preguiçosamente em outra estrutura de dados infinita lenta, enquanto a segunda deve inspecionar a lista inteira para gerar qualquer parte do resultado. Por outro lado, foldrcom uma função que precisa de ambos os argumentos imediatamente, como (+), funciona (ou melhor, não funciona) foldl, criando uma expressão enorme antes de avaliá-la.
Portanto, os dois pontos importantes a serem observados são os seguintes:
foldr pode transformar uma estrutura de dados recursiva lenta em outra.
Caso contrário, as dobras preguiçosas travarão com um estouro de pilha em listas grandes ou infinitas.
Você deve ter notado que parece que foldrpode fazer tudo o que foldlpode, além de mais. Isso é verdade! De fato, foldl é quase inútil!
Mas e se quisermos produzir um resultado não preguiçoso dobrando uma lista grande (mas não infinita)? Para isso, queremos uma dobra estrita , fornecida pelas bibliotecas padrão :
foldl' é:
Estrito : cada aplicativo de função é avaliado ao longo do caminho
Para trás : foldl' (flip (:)) []inverte uma lista.
Por foldl'ser rigoroso , para calcular o resultado que Haskell avaliará f a cada etapa, em vez de deixar o argumento da esquerda acumular uma expressão enorme e não avaliada. Isso nos dá a recursão da cauda usual e eficiente que queremos! Em outras palavras:
foldl' pode dobrar listas grandes com eficiência.
foldl' travará em um loop infinito (não causará um estouro de pilha) em uma lista infinita.
O wiki da Haskell também tem uma página discutindo isso .
Eu vim aqui porque estou curioso por que foldré melhor do que foldlem Haskell , enquanto o oposto é verdadeiro em Erlang (que aprendi antes de Haskell ). Desde Erlang não é preguiçoso e funções não são curry , por isso, foldlem Erlang se comporta como foldl'acima. Esta é uma ótima resposta! Bom trabalho e obrigado!
Essa é principalmente uma ótima explicação, mas acho a descrição de foldl"atrasada" e foldr"encaminhada" problemática. Isso ocorre em parte porque flipestá sendo aplicado (:)na ilustração de por que a dobra está para trás. A reação natural é: "é claro que é para trás: você pode fliplistar a concatenação!" Também é estranho ver o chamado "backward", uma vez que foldlse aplica fao primeiro elemento da lista primeiro (mais interno) em uma avaliação completa. É foldrque "retrocede", aplicando- fse ao último elemento primeiro.
@DaveAbrahams: Entre just foldle foldrignorar rigor e otimizações, primeiro significa "mais externo", não "mais interno". É por isso que foldrpode processar listas infinitas e foldlnão pode - a dobra direita se aplica primeiro fao primeiro elemento da lista e o resultado (não avaliado) de dobrar a cauda, ​​enquanto a dobra esquerda deve percorrer a lista inteira para avaliar a aplicação mais externa f.
Só estou me perguntando se existe algum exemplo em que foldl seria preferido em relação a foldl ', você acha que existe um?
— Kazuoua
@kazuoua onde a preguiça é essencial, por exemplo last xs = foldl (\a z-> z) undefined xs.
foldl step (step False 1) [2..]
foldl step (step (step False 1) 2) [3..]
foldl step (step (step (step False 1) 2) 3) [4..]
Intuitivamente, foldlestá sempre do lado de fora ou do lado esquerdo, para que seja expandido primeiro. Ao infinito.
Você pode ver na documentação de Haskell aqui que foldl é recursivo de cauda e nunca terminará se for passado uma lista infinita, já que se chama o próximo parâmetro antes de retornar um valor ...
Não conheço Haskell, mas em Scheme fold-rightsempre 'atuará' no último elemento de uma lista primeiro. Assim, não funcionará para a lista cíclica (que é igual a uma infinita).
Não tenho certeza se fold-rightpode ser escrito com recursividade de cauda, ​​mas para qualquer lista cíclica você deve obter um estouro de pilha. fold-leftNormalmente, o OTOH é implementado com recursão de cauda e fica preso em um loop infinito, se não for finalizado cedo.