foldl é recursivo, então como o foldr é executado mais rápido que o foldl?

Question

Eu queria testar o foldl vs o foldr.Pelo que vi, você deve usar foldl over foldr sempre que puder, devido à otimização da recursão final.

Isso faz sentido.No entanto, depois de executar este teste, estou confuso:

foldr (leva 0,057s ao usar o comando time):

a::a -> [a] -> [a]
a x = ([x] ++ )

main = putStrLn(show ( sum (foldr a [] [0.. 100000])))

foldl (leva 0,089s ao usar o comando time):

b::[b] -> b -> [b]
b xs = ( ++ xs). (\y->[y])

main = putStrLn(show ( sum (foldl b [] [0.. 100000])))

É claro que este exemplo é trivial, mas estou confuso sobre por que o foldr está superando o foldl.Este não deveria ser um caso claro em que o foldl vence?

Answer 1

Bem-vindo ao mundo da avaliação preguiçosa.

Quando você pensa sobre isso em termos de avaliação estrita, foldl parece "bom" e foldr parece "ruim" porque foldl é recursivo, mas foldr teria que construir uma torre na pilha para poder processar o último item primeiro.

No entanto, a avaliação preguiçosa vira o jogo.Tomemos, por exemplo, a definição da função map:

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

Isso não seria muito bom se Haskell usasse avaliação estrita, já que teria que calcular primeiro a cauda e depois acrescentar o item (para todos os itens da lista).A única maneira de fazer isso de forma eficiente seria construir os elementos ao contrário, ao que parece.

No entanto, graças à avaliação preguiçosa de Haskell, esta função de mapa é realmente eficiente.As listas em Haskell podem ser consideradas geradores, e esta função de mapa gera seu primeiro item aplicando f ao primeiro item da lista de entrada.Quando precisa de um segundo item, ele faz a mesma coisa novamente (sem usar espaço extra).

Acontece que map pode ser descrito em termos de foldr:

map f xs = foldr (\x ys -> f x : ys) [] xs

É difícil dizer olhando para isso, mas a avaliação preguiçosa entra em ação porque o foldr pode fornecer f seu primeiro argumento imediatamente:

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

Porque o f definido por map pode retornar o primeiro item da lista de resultados usando apenas o primeiro parâmetro, a dobra pode operar preguiçosamente em espaço constante.

Agora, a avaliação preguiçosa revida.Por exemplo, tente executar soma [1..1000000].Isso produz um estouro de pilha.Por que deveria?Deve apenas avaliar da esquerda para a direita, certo?

Vejamos como Haskell avalia isso:

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

sum = foldl (+) 0

sum [1..1000000] = foldl (+) 0 [1..1000000]
                 = foldl (+) ((+) 0 1) [2..1000000]
                 = foldl (+) ((+) ((+) 0 1) 2) [3..1000000]
                 = foldl (+) ((+) ((+) ((+) 0 1) 2) 3) [4..1000000]
                   ...
                 = (+) ((+) ((+) (...) 999999) 1000000)

Haskell tem preguiça de realizar as adições à medida que avança.Em vez disso, acaba com uma torre de bandidos não avaliados que precisam ser forçados a obter um número.O estouro de pilha ocorre durante esta avaliação, uma vez que é necessário recorrer profundamente para avaliar todas as conversões.

Felizmente, existe uma função especial em Data.List chamada foldl' que opera estritamente. foldl' (+) 0 [1..1000000] não acumulará estouro.(Observação:Eu tentei substituir foldl com foldl' no seu teste, mas na verdade ele ficou mais lento.)

Answer 2

EDIT: Ao olhar para esse problema novamente, acho que todas as explicações atuais são um pouco insuficientes, por isso escrevi uma explicação mais longa.

A diferença está em como foldl e foldr aplique sua função de redução. Olhando para o foldr Caso, podemos expandi -lo como

foldr (\x -> [x] ++ ) [] [0..10000]
[0] ++ foldr a [] [1..10000]
[0] ++ ([1] ++ foldr a [] [2..10000])
...

Esta lista é processada por sum, que consome o seguinte:

sum = foldl' (+) 0
foldl' (+) 0 ([0] ++ ([1] ++ ... ++ [10000]))
foldl' (+) 0 (0 : [1] ++ ... ++ [10000])     -- get head of list from '++' definition
foldl' (+) 0 ([1] ++ [2] ++ ... ++ [10000])  -- add accumulator and head of list
foldl' (+) 0 (1 : [2] ++ ... ++ [10000])
foldl' (+) 1 ([2] ++ ... ++ [10000])
...

Deixei de fora os detalhes da concatenação da lista, mas é assim que a redução prossegue. A parte importante é que tudo é processado para minimizar os travessos da lista. o foldr Somente atravessa a lista uma vez, as concatenações não exigem travessias de lista contínua e sum Finalmente consome a lista em um passe. Criticamente, o chefe da lista está disponível em foldr imediatamente para sum, assim sum pode começar a funcionar imediatamente e os valores podem ser GC'D à medida que são gerados. Com estruturas de fusão, como vector, até as listas intermediárias provavelmente serão fundidas.

Contraste isso com o foldl função:

b xs = ( ++xs) . (\y->[y])
foldl b [] [0..10000]
foldl b ( [0] ++ [] ) [1..10000]
foldl b ( [1] ++ ([0] ++ []) ) [2..10000]
foldl b ( [2] ++ ([1] ++ ([0] ++ [])) ) [3..10000]
...

Observe que agora o chefe da lista não está disponível até foldl terminou. Isso significa que a lista inteira deve ser construída na memória antes sum pode começar a trabalhar. Isso é muito menos eficiente em geral. Executando as duas versões com +RTS -s Mostra o desempenho miserável da coleção de lixo da versão Foldl.

Este também é um caso em que foldl' não vai ajudar. A rigor adicional de foldl' Não muda a maneira como a lista intermediária é criada. A cabeça da lista permanece indisponível até que Foldl 'termine, então o resultado ainda será mais lento do que com foldr.

Eu uso a regra seguinte para determinar a melhor escolha de fold

• Para dobras que são um redução, usar foldl' (por exemplo, este será o único/final travessal)
• Caso contrário, use foldr.
• Não use foldl.

Na maioria dos casos foldr é a melhor função de dobra porque a direção de travessia é ideal para avaliação preguiçosa das listas. É também o único capaz de processar listas infinitas. A rigidez extra de foldl' pode torná -lo mais rápido em alguns casos, mas isso depende de como você usará essa estrutura e quão preguiçoso é.

Answer 3

Eu não acho que ninguém tenha dito a resposta real neste ainda, a menos que esteja perdendo alguma coisa (que pode muito bem ser verdadeira e bem -vinda com votos).

Eu acho que o maior diferente neste caso é que foldr Construa a lista como esta:

[0] ++ ([1] ++ ([2] ++ (... ++ [1000000])))

Enquanto foldl Construa a lista como esta:

((([0] ++ [1]) ++ [2]) ++ ... ) ++ [999888]) ++ [999999]) ++ [1000000]

A diferença em sutil, mas observe que no foldr versão ++ Sempre tem apenas um elemento de lista como argumento esquerdo. Com o foldl versão, existem até 999999 elementos em ++O argumento da esquerda (em média, cerca de 500000), mas apenas um elemento no argumento certo.

No entanto, ++ leva tempo proporcional ao tamanho do argumento de esquerda, pois ele deve procurar por toda a lista de argumentos da esquerda até o final e depois apontar esse último elemento ao primeiro elemento do argumento direito (na melhor das hipóteses, talvez ele realmente precise fazer um cópia de). A lista de argumentos certos permanece inalterada, por isso não importa o quão grande é.

É por isso que o foldl A versão é muito mais lenta. Não tem nada a ver com preguiça na minha opinião.

Answer 4

O problema é que a otimização de recursão da cauda é uma otimização de memória, não uma otimização de tempo de execução!

A otimização de recursão da cauda evita a necessidade de lembrar os valores para cada chamada recursiva.

Então, Foldl é de fato "bom" e Foldr é "ruim".

Por exemplo, considerando as definições de Foldr e Foldl:

foldl f z [] = z
foldl f z (x:xs) = foldl f (z `f` x) xs

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

É assim que a expressão "dobra (+) 0 [1,2,3] é avaliada:

foldl (+) 0 [1, 2, 3]
foldl (+) (0+1) [2, 3]
foldl (+) ((0+1)+2) [3]
foldl (+) (((0+1)+2)+3) [ ]
(((0+1)+2)+3)
((1+2)+3)
(3+3)
6

Observe que Foldl não se lembra dos valores 0, 1, 2 ..., mas passe toda a expressão (((0+1) +2) +3) como argumento preguiçosamente e não o avalie até a última avaliação de Foldl, onde atinge o estojo base e retorna o valor passado como o segundo parâmetro (z) que ainda não foi avaliado.

Por outro lado, é assim que Foldr funciona:

foldr (+) 0 [1, 2, 3]
1 + (foldr (+) 0 [2, 3])
1 + (2 + (foldr (+) 0 [3]))
1 + (2 + (3 + (foldr (+) 0 [])))
1 + (2 + (3 + 0)))
1 + (2 + 3)
1 + 5
6

A diferença importante aqui é que, onde Foldl avalia toda a expressão na última chamada, evitando a necessidade de voltar para alcançar valores lembrados, Foldr não. Foldr Lembre -se de um número inteiro para cada chamada e executa uma adição em cada chamada.

É importante ter em mente que o dobro e o dobro nem sempre são equivalentes. Por exemplo, tente calcular essas expressões em abraços:

foldr (&&) True (False:(repeat True))

foldl (&&) True (False:(repeat True))

Foldr e Foldl são equivalentes apenas sob certas condições descritas aqui

(Desculpe pelo meu inglês ruim)

Answer 5

Para A, o [0.. 100000] A lista precisa ser expandida imediatamente para que o Foldr possa começar com o último elemento. Então, ao dobrar as coisas juntas, os resultados intermediários são

[100000]
[99999, 100000]
[99998, 99999, 100000]
...
[0.. 100000] -- i.e., the original list

Como ninguém tem permissão para alterar esse valor de lista (Haskell é uma linguagem funcional pura), o compilador é livre para reutilizar o valor. Os valores intermediários, como [99999, 100000] pode até ser simplesmente pontere para o expandido [0.. 100000] Lista em vez de listas separadas.

Para B, observe os valores intermediários:

[0]
[0, 1]
[0, 1, 2]
...
[0, 1, ..., 99999]
[0.. 100000]

Cada uma dessas listas intermediárias não pode ser reutilizada, porque se você alterar o final da lista, alterou outros valores que apontam para ela. Então, você está criando várias listas extras que levam tempo para construir na memória. Portanto, neste caso, você gasta muito mais tempo alocando e preenchendo essas listas que são valores intermediários.

Como você está apenas fazendo uma cópia da lista, uma corrida mais rápida porque começa expandindo a lista completa e continua movendo um ponteiro da parte de trás da lista para a frente.

Answer 6

Nenhum foldl nem foldr é otimizado para a cauda. É apenas foldl'.

Mas no seu caso usando ++ com foldl' não é uma boa ideia porque avaliação sucessiva de ++ causará atravessando o crescente acumulador repetidamente.

Answer 7

Bem, deixe -me reescrever suas funções de uma maneira que a diferença deve ser óbvia -

a :: a -> [a] -> [a]
a = (:)

b :: [b] -> b -> [b]
b = flip (:)

Você vê que B é mais complexo que a. Se você quer ser preciso a precisa de uma etapa de redução para o valor ser calculado, mas b precisa de dois. Isso faz a diferença de tempo que você está medindo, no segundo exemplo duas vezes mais reduções devem ser executadas.

// Editar: Mas a complexidade do tempo é a mesma, então eu não me incomodaria muito com isso.