Capítulo 4  Funções de ordem superior

Funções de ordem superior como map e filter permitem a implementação de operações comuns em estruturas de dados: aplicar uma função a todos os elementos da estrutura de dados e filtrar os elementos que satisfazem a um predicado.

No entanto, estes são casos especiais de uma operação mais expressiva, chamada de fold (ou reduce), que permite obter um resultado pela aplicação de uma função binária aos elementos de uma estrutura de dados para obtenção de um resultado final, a partir de um valor inicial.

O uso de fold abstrai o uso de recursão primária sobre listas, e permite que o programador defina apenas a função binária e o valor inicial necessários para obtenção do resultado de percorrer os elementos da lista, a partir do elemento inicial, aplicando-se a função binária.

Há duas formas de fold sobre listas: foldr (“fold right”), i.e. fold sobre os elementos da lista da direita para a esquerda, em outras palavras, do último até o primeiro elemento da lista, e foldl (“fold left”), i.e. fold dos elementos da lista da esquerda para a direita, em outras palavras, do primeiro até o último elemento).

4.1  foldr

Consideremos primeiro foldr. O tipo dessa função é:

foldr f z aplicado a uma lista [x₁, …, x_n] fornece o resultado:

Em outras palavras, o resultado de foldr f z aplicado à lista x₁ : (… (x_n : [])) é obtido substituindo [] por z e (:) por `f`.

O valor de tipo b obtido em aplicações sucessivas de f em um fold é chamado de acumulador.

O resultado é calculado da direita para a esquerda, isto é, a primeira aplicação é f x_n z, depois f x_n−1 r₁, sendo r₁ o resultado obtido por essa primeira aplicação, até f x₁ r_n−1, sendo esse o último e r_n−1 o penúltimo resultado obtido com aplicações de f. A definição de foldr é a seguinte:

Exemplos

Exemplos básicos de uso de foldr são mostrados a seguir. Procure exercitar, definindo você mesmo, antes de ver a definição.

Para isso, pense o seguinte: foldr f z obtém um valor final aplicando f a partir do valor inicial z. É preciso definir f e z. Leve em conta que: f recebe um elemento da lista, o resultado (de tipo r) de fazer foldr no restante da lista, e retorna um valor (do mesmo tipo de r); z é o valor retornado quando a lista é vazia.

É útil também ter em mente como foldr computa seu resultado, como mostrado em (4.1).

1. soma de todos os elementos:

   sum = foldr (+) 0

2. multiplicação de todos os elementos:

   prod = foldr (*) 1

3. concatenação de todos os elementos (de uma lista de listas):

   concat = foldr (++) []

4. conjunção de todos os elementos:

   and = foldr (&&) True

5. disjunção de todos os elementos:

   or = foldr (||) False

6. máximo dos elementos (de uma lista não vazia):

   maximum (a:x) = foldr max a x

7. mínimo dos elementos (de uma lista não vazia):

   minimum (a:x) = foldr min a x

8. comprimento (número de elementos):

   len = foldr (\ _ -> (+1)) 0

9. map:

   map f = foldr ((:) . f) []

10. filter:

    filter p = foldr (\ a -> if p a then (a:) else id) []

Mais exemplos são mostrados a seguir.

1. teste de pertinência a lista:

   elem a = foldr ((||) . (==a)) False

2. ordenação por inserção:

   insertionSort = foldr ins [] ins a [] = [a] ins a (b:x) | a <= b = a:b:x | otherwise = b: ins a x

3. inserção de valor (k) entre dois elementos consecutivos de uma lista; na definição de intersperse mostrada abaixo, o elemento k a ser inserido entre cada elemento da lista não é inserido após o último elemento:

   intersperse k = foldr (ins_apos k) [] ins_apos _ a [] = [a] ins_apos k a x = a:k:x

4.2  foldl

foldl f z aplicado a uma lista [x₁, …, x_n] fornece o resultado:

O tipo de foldl é:

A função f em foldl f, ao contrário de foldr, recebe o “acumulador” primeiro, e depois o elemento da lista.

foldl é útil em casos em que é necessário processar a lista a partir da esquerda (como o sufixo l de foldl sugere), ou quando se deseja inverter a ordem dos elementos da lista. A definição de foldl é a seguinte:

Exemplos de uso de foldl:

1. cálculo do valor inteiro correspondente a uma lista de dígitos, na base 10 (por exemplo, convDigsInt "923" retorna o inteiro 923):

   convDigsInt = foldl (\ x ch -> (fromEnum ch - fromEnum '0') + x*10) 0

   ou, usando notação sem argumentos:

   convDigsInt = foldl (flip ((+) . subtract (fromEnum '0') . fromEnum) . (*10)) 0

2. inversão da ordem dos elementos em uma lista:

   reverse = foldl (flip (:)) []

3. cálculo de

   approxe n =

   n ∑ i=1

   1 i!

   Usando foldl, o cálculo de approxe n pode ser feito de modo que o fatorial de i seja calculado a partir do fatorial da parcela anterior (evitando assim que o cálculo de approxe n fique ineficiente):

   approxe n = fst $ foldl somaSerieHarmonica (0,1) [1..n] somaSerieHarmonica (soma, fatDen) i = (soma + 1 / fatDen', fatDen') where fatDen' = fatDen * i

4. maiorComFatMenorQue x retorna o menor inteiro k≥ 2 tal que k! >x.

   maiorComFatMenorQue:: Integer -> Integer -> Maybe Integer -- maiorComFatMenorQue x retorna Just k tal que 2<=k<100, k!>x, (k-1)!<=x, se existir, -- senão retorna Nothing. maiorComFatMenorQue x = fst $ foldl (multIfFatMenorQue x) (1,False) [2..100] -- multIfFatMenorQue:: Integer -> (Integer,Bool) -> Integer -> (Integer,Bool) multIfFatMenorQue x (fat,False) k | fatk < x = (fatk,False) | otherwise = (k,True) where fatk = fat * k multIfFatMenorQue _ r _ = r

5. subtraiAte0De n x retorna Just k, se k é o elemento da lista x a partir do qual a subtração de cada elemento de x a n, a partir do primeiro, dá resultado menor que zero, senão retorna Nothing.

   subtraiAte0De n = case foldl subtraiAte0 (n,False) of (k,True) -> Just k _ -> Nothing subtraiAte0 (k,False) e | k_e < 0 = (k,True) | otherwise = (k_e,False) where k_e = k - e subtraiAte0 r _ = r

4.2.1  Ineficiência da complexidade de espaço da avaliação preguiçosa de foldl

Ao contrário da complexidade de tempo, a complexidade de espaço da estratégia de avaliação preguiçosa não é ótima. Por exemplo, a quantidade de espaço usada para obter o resultado de:

é O(n), onde n é o tamanho da lista, quando f é estrita. A complexidade de espaço usada para obter o resultado de foldr f z x é também O(n) quando f é estrita. Se a lista for grande, isso poderá acarretar problema de falta de espaço suficiente para obter o resultado.

No entanto, no caso de foldl, a complexidade de espaço usada pela estratégia de avaliação gulosa é O(1): para calcular foldl f z x, sendo x = [x₁,…,x_n], o resultado r_i de f z x_i é calculado imediatamente, em vez de ser salvo para ser calculado posteriormente (no cálculo de f r₁ x_i+1), para i=1,…,n. Isso evita que espaço de memória tenha que ser alocado a cada i de 1 até n.

No caso de foldr, a complexidade de espaço da avaliação preguiçosa não pode ser melhorada, no pior caso (de O(n) para uma complexidade menor), porque a construção dos resultados tem que ser realizada a partir o primeiro elemento da lista e terminar com o último elemento da lista (e isso envolve custo O(n)), de modo a permitir que os resultados sejam calculados do último elemento da lista até o primeiro.

4.3  foldr versus foldl

Quando analisamos a eficiência, em termos de tempo e espaço, de foldr e foldl, por exemplo para decidir quando usar uma ou outra função, podemos chegar a algumas conclusões, expostas a seguir.

Consideremos foldr primeiro:

Note:

1. Se f e não for estrita (isto é, se o resultado da avaliação de e₁ for suficiente para estabelecer o resultado de f e₁ e₂, em outras palabras , se a avaliação de e₂ puder não ser necessária para estabelecer o resultado de e₁ ‘f‘ e₂), a complexidade de tempo do cálculo de (foldr f z x) é sub-linear, pois o número de valores de x, a partir de x₁, necessários para que f estabeleça um resultado, será menor ou igual a n.

   Por exemplo, foldr (&&) True (repeat False) é igual a False (apesar de repeat False ser uma lista infinita), e o tempo necessário para avaliação é constante (esse é o tempo necessário para o cálculo de False && l, podendo l ser qualquer lista, finita ou infinita).

   O mesmo acontece para a complexidade de espaço.

2. Se, no entanto, se f e f e forem estritas (isto é, se o resultado da avaliação de e₁ e de e₂ forem necessários para a avaliação de e₁ ‘f‘ e₂), a complexidade de tempo do cálculo de foldr f z x (onde n é o número de elementos de x) é O(n*t(n)), onde t é a complexidade de tempo do cálculo de f.

   O mesmo acontece para a complexidade de espaço.

3. No caso de foldl, a avaliação de f ocorre internamente:

   foldl f  z  ( x1 : (… : (xn :  [ ]) …)) =    f ( … (f ( f  z  x1 )  x2)  …  xn)

   Por exemplo, a avaliação de foldl (&&) True (repeat False) não termina, é preciso que uma lista infinita de valores seja processada para obtenção do resultado, pois a avaliação é feita sempre a partir da função mais externa.

4.4  Exercícios

1. Escreva, usando foldl ou foldr  uma função que recebe uma lista de cadeias de caracteres (valores do tipo String) e retorna uma cadeia de caracteres que contém os 3 primeiros caracteres de cada cadeia.

   Por exemplo, ao receber ["Abcde", "1Abcde", "12Abcde", "123Abcde"] deve retornar "Abc1Ab12A123".

2. Escreva, usando foldr ou foldl, uma função que recebe uma lista de valores do tipo Pessoa, definido a seguir, e retorna a soma das idades (valores do campo idade) de todos os elementos da lista.

   data Pessoa = Pessoa {nome::Nome, idade::Idade, id::RG} type Nome = String type Idade = Integer type RG = String

   Note: a definição do tipo Pessoa com campo idade de tipo Idade cria automaticamente função idade:: Pessoa -> Idade, que seleciona o valor no campo idade do argumento de tipo Pessoa.

3. Escreva, usando foldr ou foldl, uma função que recebe uma lista não vazia de valores de tipo Pessoa, da definição acima, e retorna o nome da pessoa mais nova da lista.
4. Escreva, usando foldl ou foldr, uma função que recebe uma lista de cadeias de caracteres (valores do tipo String) e retorna uma cadeia de caracteres que contém os 3 primeiros caracteres de cada cadeia removidos se não forem letras, ou com as letras em caixa alta se forem letras, e com os demais caracteres depois dos 3 primeiros sem alteração.

   Por exemplo, ao receber ["Abcde", "1Abcde", "12Abcde", "123Abcde"] deve retornar "ABCdeABcdeAbcdeAbcde".

5. Explique porque foldr f x pode não percorrer toda a lista x, ao passo que toda a lista x é sempre percorrida, no caso de foldl.cc
6. A função remdups remove elementos iguais adjacentes de uma lista, conservando só um dos elementos.

   Por exemplo, remdups [1,2,2,3,3,3,1,1] = [1,2,3,1].

   Defina remdups usando foldr ou foldl.

7. Suponha x uma lista ordenada, mais precisamente lista de elementos de uma instância de Ord a => [a]; escreva, usando foldr, função contaAdjs:: Ord a => [a] -> [(Int,a)], tal que contaAdjs x é a lista dos valores (n,e) tais que n é o número de ocorrências de e em x.

   Por exemplo, contaAdjs "aabbbccd" retorna [(2,'a'),(3,'b'),(2,'c'),(1,'d')].