comportamento foldl versus foldr com listas infinitas

124

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 :: (a -> Bool) -> [a] -> Bool
myAny p list = foldl step False list
   where
      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 :

myAny even [1..]
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..])
True

No entanto, não é assim que a função se comporta. Como isso está errado?

titaniumdecoy
fonte

Respostas:

231

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.
  • Preguiçoso : nada é avaliado até que o resultado seja necessário
  • 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' é:

  • Associativo esquerdo :f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
  • Cauda recursiva : itera pela lista, produzindo o valor posteriormente
  • 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 .

CA McCann
fonte
6
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!
você precisa saber é o seguinte
7
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.
Dave Abrahams
1
@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.
CA McCann
1
Só estou me perguntando se existe algum exemplo em que foldl seria preferido em relação a foldl ', você acha que existe um?
Kazuoua
1
@kazuoua onde a preguiça é essencial, por exemplo last xs = foldl (\a z-> z) undefined xs.
Will Ness
28
myAny even [1..]
foldl step False [1..]
foldl step (step False 1) [2..]
foldl step (step (step False 1) 2) [3..]
foldl step (step (step (step False 1) 2) 3) [4..]

etc.

Intuitivamente, foldlestá sempre do lado de fora ou do lado esquerdo, para que seja expandido primeiro. Ao infinito.

Artelius
fonte
10

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 ...

Romain
fonte
0

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.

leppie
fonte
3
É diferente em Haskell por causa da preguiça.
Lifu Huang