O operador foldl

O mecanismo foldl é usado para aplicar uma função f, de forma recorrente, a todos os elementos de uma lista.

foldl função base lista

A função f tem necessariamente dois paramentos de entrada. O primeiro é do tipo do resultado que desejamos obter e o segundo do tipo dos elementos que constituem a lista.

Exemplo 1: a expressão foldl (+) 0 [1..10] , descreve o somatório dos 10 primeiros números inteiros positivos.

Na avaliação da expressão, a função f, aqui representada pelo operador "+", e por isso expressa entre parênteses, é aplicada recorrentemente ao resultado parcial e a um elemento da lista. Inicialmente o operador é aplicado ao elemento base e ao primeiro elemento da lista, resultando no primeiro resultado parcial e assim sucessivamente. Vejamos um trace da avaliação da expressão:

1) 0 [1..10]
2) 1 [2..10]
3) 3 [3..10]
4) 6 [4..10]
5) 10 [5..10]
...
n) 55 [ ]

O elemento base é escolhido de modo a não interferir no resultado final. Neste caso usamos o elemento neutro da adição, o zero.

Exemplo 2: a expressão foldl (*) 1 [1..10] , descreve o produtório dos 10 primeiros números inteiros positivos. O elemento base aqui usado foi o número 1, o elemento neutro da multiplicação.

Exemplo 3: Descrever a pertinência (ocorrência) de um elemento e a uma lista xs.

Apresentaremos 3 soluções para ilustrar diferentes possibilidades. Todas terão como base a aplicação recorrente da comparação do elemento e com um elemento da lista. Podemos observar aqui que a função a ser aplicada recorrentemente precisa de 3 parâmetros, entretanto o operador foldl só dá suporte a 2 parâmetros.

Vamos primeiro construir uma solução preliminar, em que o elemento que desejamos verificar a ocorrência é um valor constante. Tomemos 5 como este elemento constante.

Solução 0:
ocorre xs = foldl ocorreaux False xs
ocorreaux a b = a || (b==5)

a avaliação da função ocorre resultará em True se pelo menos um dos elementos da lista xs for igual a 5.

Usando a definição:

Main> ocorre [1..10]
True
Main> ocorre [50..100]
False
Main> ocorre []
False


Voltando à situação inicial, precisamos generalizar, usando um valor e ao invés da constante 5.
as soluções apresentadas a seguir apresentam diferentes maneiras de introduzir o terceiro parametro para a função ocorreaux.

Solução 1: usando uma definição local para ocorreaux.

ocorre' e xs = foldl ocorreaux False xs
where
ocorreaux a b = a || (b==e)

aqui o elemento e é usado diretamente da entrada pois sendo ocorreaux é definida localmente, sua definição compartilha as variáveis da interface de ocorre'.

Aplicando ocorre' obtemos:

Main> ocorre' 5 [1..20]
True
Main> ocorre' 5 [10..20]
False
Main> ocorre' 5 []
False

Solução 2: usando uma definição global para ocorreaux, com 3 parâmetros, combinado com a aplicação de ocorreaux ao primeiro parâmetro para obter uma função com apenas dois parametros a ser utilizada pelo foldl.

ocorre'' e xs = foldl (ocorreaux' e) False xs
ocorreaux' x a b = a || (b==x)

neste caso, a função f é realizada pela função (ocorreaux' e). Relembramos aqui que a aplicação de uma função a um valor, descreve uma nova função.

Aplicando ocorre'' obtemos:

Main> ocorre'' 5 [1..20]
True
Main> ocorre'' 5 [10..20]
False
Main> ocorre'' 5 []
False


Solução 3: Usando uma definição anônima para a função f através do operador lambda.

ocorre''' e xs = foldl (\a b -> a || (b==e)) False xs

relembramos que uma definição lambda representado por "->" tem duas partes, a introdução das variáveis, à esquerda de "->" e o corpo da função à sua direita.

Aplicando ocorre''' obtemos:

Main> ocorre''' 5 [1..20]
True
Main> ocorre''' 5 [10..20]
False
Main> ocorre''' 5 []
False