Sobre folds e uma pegadinha

Em Haskell uma maneira bem comum de iterar sobre uma lista e acumular valores é por meio de recursão. Geralmente usamos pattern matching para tratar o caso da lista vazia, seguido do caso da lista com um ou mais valores, aplicando a função e chamando a função novamente com o restante da lista.

somaInteiros :: [Int] -> Int
somaInteiros []     = 0
somaInteiros (x:xs) = x + (somaInteiros xs)

somaInteiros [1,2,3,4,5] -- 15

Na medida que vamos nos habituando com recursão esse tipo de função se torna comum em código Haskell. Por se tratar de um padrão muito comum, algumas funções foram incluídas junto da linguagem para abstrair o uso de recursão, e essas funções são chamadas folds.

Uma função fold recebe 3 parâmetros, a função acumuladora, um valor inicial e a lista que será acumulada.

foldr

Acumulando uma lista com a função foldr:

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

{- execução passo a passo

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

1 + (2 + (3 + (4 + (5 + 0))))
1 + (2 + (3 + (4 + 5)))
1 + (2 + (3 + 9))
1 + (2 + 12)
1 + 14
15
-}

Manipular pequenas listas não será um problema, agora imagine uma lista com 1000000000 itens. Para cada item a função + adicionará um item a pilha de execução enquanto aguarda o resultado da execução seguinte do foldr, até que um estouro de pilha aconteça.

foldr (+) 0 [1..1000000000]

*** Exception: stack overflow

O problema com a função foldr é que os resultados intermediários poderiam ser acumulados antes da próxima chamada, o que não é feito, como deixa claro no exemplo acima.

foldl

Para resolver este problema temos a função foldl, que vai funcionar de maneira análoga, mas com uma diferença sutil, vai acumular os itens de cada etapa até o final, o que evita milhares de itens sendo adicionados a pilha de execução. Seria algo assim:

foldl f z []     = z
foldl f z (x:xs) = let y = f z x
                   in foldl f y xs

Executando o foldl em uma lista com muitos valores:

foldl (+) 0 [1..1000000000]

*** Exception: stack overflow

WTF! Se está acumulando os valores intermediários, porque diabos está acontecendo um estouro de pilha?

Rá! Pegadinha do malandro.

Devemos lembrar que Haskell é uma linguagem com avaliação preguiçosa, e só avalia uma expressão quando esta realmente é necessária para retornar um valor, por conta disso os valores não estavam sendo acumulados de fato. Vamos ao passo a passo de execução usando foldl:

foldl (+) 0 [1,2,3,4,5]

{- execução passo a passo
let v1 = 0 + 1
in foldl (+) v1 [2,3,4,5]

let v1 = 0 + 1
    v2 = v1 + 2
in foldl (+) v2 [3,4,5]

let v1 = 0 + 1
    v2 = v1 + 2
    v3 = v2 + 3
in foldl (+) v3 [4,5]

let v1 = 0 + 1
    v2 = v1 + 2
    v3 = v2 + 3
    v4 = v3 + 4
in foldl (+) v4 [5]

let v1 = 0 + 1
    v2 = v1 + 2
    v3 = v2 + 3
    v4 = v3 + 4
    v5 = v4 + 5
in foldl (+) v5 []

((((0 + 1) + 2) + 3) + 4) + 5
(((1 + 2) + 3) + 4) + 5
((3 + 3) + 4) + 5
(6 + 4) + 5
10 + 5
15

Ao invés de acumular os valores, os mesmos agora estão sendo alocados no heap, que é limitado pela quantidade de memória e swap presente na máquina, o que acaba causando o um stack overflow quando não há mais espaço para alocação. Triste, não? :(

É um comportamento inesperado que surpreende a primeira vez que nos deparamos com isso. Mas então, como resolver isso?

foldl’

Temos de forçar a avaliação dos acumuladores para evitar este problema, e é exatamente o que a função foldl’ faz, utilizando por debaixo dos panos a função seq:

foldl' f z []     = z
foldl' f z (x:xs) = let z' = f z x
                    in seq z' (foldl' f z' xs)

A função seq é uma função que recebe 2 parâmetros, avalia o primeiro e retorna o segundo, perfeito para resolver o problema do foldl. Com o acumulador sendo avaliado forçadamente em cada passo, não temos alocações exageradas no heap, com isso evita-se o estouro de pilha.

foldl' (+) 0 [1..100000000] -- 5000000050000000

Conclusão

Para a maioria dos casos foldr será suficiente, funcionando mesmo com listas infinitas. Para os outros casos quando a lista manipulada for bem grande e finita, foldl’ será a opção. Dado os motivos já discutidos anteriormente neste post, é melhor evitar o foldl.

Para mais detalhes, consulte a wiki do site haskell.org em inglês: Foldr_Foldl_Foldl’