Um outra forma de entender o operador Foldl

Considere o conceito teórico da aplicação recorrente de uma função g a um determinado valor v, que podemos representar por:

(g v)*

por exemplo, seja g v = v + 1, então (g 3)* => 3, 4, 5, 6, 7, 8, 9, 10 ...

a aplicação de g prossegue enquanto o valor resultante de uma aplicação for um valor válido como entrada de g. Assim, dependendo de g e do valor inicial, a aplicação recorrente pode ser infinita.

O valor v pode ser estruturado. Vamos considerar uma situação mais complexa.

problema: definir uma função g que compute o somatório dos elementos de uma lista xs.

podemos definir
g xs = (g1 (0, xs) ) *
onde g1 (v1, xs) = (v1 + head xs, tail xs)

assim, g [1,3,5,7,9] = g1 (0, [1, 3, 5, 7, 9]) *
cuja seqüência de computação seria:
(0+1, [3, 5, 7, 9]),
(1 + 3, [5, 7, 9]),
(4+5, [7, 9]),
(9+7, [9]),
(16+9, []),
(26, ?)


Podemos entender o foldl como uma função de segunda ordem que tem comportamento semelhante a este conceito teórico acima apresentado.

O foldl funciona como a aplicação recorrente de uma função f a um par, onde o primeiro elemento é um valor x qualquer e o segundo uma lista xs. A cada passo, o foldl aplica a função f ao valor corrente de x e ao primeiro elemento de xs, para obter um novo valor para x. Sobre xs é aplicada a função tail xs.

ou seja foldl = ( (f x head xs, tail xs) )*

Por exemplo, para determinar o somatório dos elementos de uma lista xs, podemos escrever:

somatorio xs = foldl (+) 0 xs

uma aplicação desta definição, à lista [3, 8, 25, 1, 10], geraria as seguintes computações:

( 0, [3, 8, 25, 1, 10] )
( 0 + 3, [8, 25, 1, 10] )
( 0 + 3 + 8, [25, 1, 10] )
( 0 + 3 + 8 + 25, [1, 10] )
( 0 + 3 + 8 + 25 + 1, [10] )
( 0 + 3 + 8 + 25 + 1 + 10, [] )
(47, ?)

Vejamos que não é necessário que os elementos de xs sejam considerados na computação.
Por exemplo, vejamos uma função para descrever uma Progessão Aritmética, com primeiro termo a1, razão r e n termos.

pa a1 r n = foldl f ( r, [a1]) [2..n]
where
f (r, ys) b = ( r, ys ++ [last ys + r])

Para explicitar um pouco mais a expressividade computacional, vejamos a aplicação de uma função f a uma tripla, onde para cada elemento da tripla é definida uma função fi.

h a1 a2 a3 n = foldl f (a1, a2, a3) [2..n]
where
f (a1, a2, a3) b = ( f1 a1, f2 a2, f3 a3)
f1 x = x + 1
f2 y = y + 2
f3 z = z + 3