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

Criando listas com foldl

Vários exemplos apresentados na literatura produzem, com o foldl, elementos simples, como um número. Mas também podemos produzir listas.

No exemplo a seguir, desejamos produzir, a partir de uma lista xs, uma lista com o quadrado de cada número de xs.

A função quadaux opera produzindo uma nova lista, acrescentando ao final da lista xs o quadrado do número x dado, usando a operação "++" para concatenar duas listas. Primeiro produzimos uma lista com o quadrado do número dado e depois concatenamos.

quadaux xs x= xs ++ [x * x]

A função lquad aplica a função quadaux a cada elemento da lista de entrada xs, tendo como elemento neutro a lista vazia.

lquad xs = foldl quadaux [ ] xs

Vejamos a aplicação da função usando o ambiente HUGS

>lquad [1..10]
[1,4,9,16,25,36,49,64,81,100]

> lquad []
[]

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

Ordenação de Dados - II

O que resultaria da tentativa de usar a definição apresentada em "Ordenação de Dados - I" para uma lista com repetição?

> ordena [3,5, 4,2,6,5]
[2,3,4,5,
Program error: pattern match failure: head []

como o valor 5 se repete, e sua segunda ocorrência é desconsiderada, o elemento de índice 4 da lista ordenada não existe e assim, a lista de elementos para i igual a 4 é vazia e portanto a apliação de head [ ] falha.

Há como contornar a situação? A definição anterior pode ser estendida para contemplar a repetição?

Podemos voltar à definição apresentada na postagem anterior e verificar que na se deixarmos de usar a a operação head xs, na definição de "elempos i xs", teriamos como resultado uma lista de listas.

menores y xs = [x | x<-xs, x <>
qmen y xs = length (menores y xs)
elempos i xs = [ x | x <-xs, qmen x xs == i]
ordena xs = [ elempos i xs | i <- [0..length xs -1]]

> ordena [8, 7, 5 , 9, 20, 4, 2]
[[2],[4],[5],[7],[8],[9],[20]]

e agora, aplicando a definição para uma lista com repetição, obtemos:

> ordena [3,5, 3, 4,2,6,5, 3]
[[2],[3,3,3],[],[],[4],[5,5],[],[6]]

podemos observar que no caso de repetição, surgem n-1 listas vazias, correspondendo ao elementos que por serem repetidos se associam no índice anterior.

Estamos a um passo da solução. Podemos concatenar todas as listas e assim obtermos o resultado desejado.

ordena xs = concat [ elempos i xs | i <- [0..length xs -1]]

> ordena [3,5, 3, 4,2,6,5, 3]
[2,3,3,3,4,5,5,6]
> ordena [8, 7, 5 , 9, 20, 4, 2]
[2,4,5,7,8,9,20]

Como podemos agora refrasear a nossa descrição informal da solução?

Ordenação de Dados - I

Estamos interessados em descrever a ordenação de uma lista usando o mecanismo de List Comprehension.
Para principiantes, esta é uma atividade que traz bastante dificuldades. Há uma forte inclinação em descrever como ordenar uma lista, em detrimento da preocupação com a descrição do que é uma lista ordenada.
Vamos primeiro restringir nosso problema de ordenação: comecemos pela ordenação crescente de uma lista de números inteiros distintos.

No primeiro passo, a descrição informal, devemos encontrar uma propriedade de lista ordenada crescente de números inteiros distintos, que seja aderente ao mecanismo List Comprehension.

Descrevendo Informalmente:

• em uma lista ordenada crescente de números distintos, o índice de um elemento é igual à quantidade de elementos menores que ele na referida lista;
• que pode ser reescrita como: para cada índice i, de uma lista ordenada, o i-ésimo elemento é aquele que possui exatamente i elementos menores que ele na lista.

Formalizando:
--
-- a ordenação de xs é uma lista formada por elempos i xs, tal que i pertence ao intervalo de
-- indexação de xs
--
ordena xs = [ elempos i xs | i <- [0..length xs - 1]]
--
-- o elemento de xs que tem posição i é o cabeça da lista dos elementos x pertencentes xs tal
-- que a quantidade de menores que x em xs é igual a i
--
elempos i xs = head [ x | x <-xs, qmen x xs == i]
--
-- a quantidade de menores que x em xs é o tamanho da lista de menores
--
qmen y xs = length (menores y xs)
--
-- a lista de elementos de xs menores que y é formada pelos elementos de xs que satisfazem a
-- propriedade: y <>
--
menores y xs = [x | x<-xs, x <>

vejamos alguns exemplos de uso, rodando em HUGS para windows:

Testando a Solução

> ordena [7, 3, 5, 2, 9, 4, 6, 1, 10, 0]
[0,1,2,3,4,5,6,7,9,10]

> ordena [100]
[100]

> ordena []
[]

> ordena [10,9..0]
[0,1,2,3,4,5,6,7,8,9,10]

Alguns possíveis prosseguimentos:

• e se a a lista possui elementos repetidos?
• e se a ordem desejada for decrescente?
• e se a lista for formada por elementos de outro tipo?