Haskell/Funções de alta ordem

Este módulo encontra-se em processo de tradução. A sua ajuda é bem vinda.

A ideia central de programação funcional é que funções são como qualquer outro valor. O poder do estilo funcional vem de podermos lidar com funções como se fossem valores comuns, isto é, passando funções para outras funções como argumentos e recebendo funções como saída. Uma função que uma função (ou mais de uma) como argumento é chamada de função de alta ordem. Elas podem ser encontradas em qualquer lugar num programa em Haskell, sendo já conhecemos algumas delas, como map e as folds. Vimos alguns exemplos do uso de map em Listas II. Agora, vamos explorar os jeitos mais comuns de escrever programas que manipulem funções.

Um algoritmo de ordenação

Como exemplo concreto, considere o problema de ordenar uma lista. Quick sort é um algoritmo recursivo bastante conhecido. A estratégia por trás dele é selecionar um elemento de da lista (chamado pivô) e depois dividi-la em três partes: A) os elementos que devem vir antes do pivô; B) os elementos que são iguais ao pivô; e C) os que devem vir depois do pivô. Depois, o mesmo algoritmo é aplicado às partes A e C. Depois de um número de vezes necessário, basta juntar tudo e teremos uma lista ordenada com resultado. Essa estratégia pode ser escrita em Haskell de maneira bem simples.

-- Assinatura de tipo: qualquer lista cujos elementos pertençam à classe Ord podem ser ordenados
quickSort :: (Ord a) => [a] -> [a]

-- Caso base: se a lista estiver vazia, não fazer nada
quickSort [] = []

-- Caso recursivo: escolher o primeiro elemeto como pivô e ordenar o restante
-- Note como o pivô acaba sendo incluído no meio de tudo
quickSort (x:xs) = (quickSort menores) ++ (x : iguais) ++ (quickSorte maiores)
    where menores = filter (< x) xs
          maiores = filter (> x) xs
          iguais  = filter (== x) xs

Deve-se observar que nosso quickSort é bem simples. Uma versão mais eficiente evitaria chamar filter três vezes, e também não usaria (++) para criar a lista final. Além do mais, ao contrário desta implementação, versão original de quick sort faz a ordenação in loco, usando mutabilidade, isto é, sem criar uma nova variável dentro da função e depois entregando-a na saída, mas alterando a própria variável de entrada. Esses problemas serão ignorados, pois, em vez da implementação exata, estamos mais interessados no padrões de uso de funções de ordenação.

A classe Ord

Quase todos os tipos básico em Haskell pertecem à classe Ord, que trata de comparações de ordenação, assim com a classe Eq trata de testes de igualdade. Ord define qual ordem é "natural" para um certo tipo. Ela fornece a função chamada compare cujo tipo é

compare :: (Ord a) => a -> a -> Ordering

compare toma dois valores e os compara, retornando um valor do tipo Ordering, que pode ser

• LT, que significa menor que (do inglês less than), caso o primeiro valor seja menor que o seguindo,
• EQ, que significa igual (do inglês equal), caso ambos os valores seja iguais, e
• GT que significa maior que (do inglês greater than), caso o primeiro valor seja maior que o segundo.

Funções com o (<) e (>) pode ser vistas como atalhos para compare, pois elas comparam as três possibilidades e retornam um Bool para indicar se a ordem dos argumentos é válida. Perceba que cada um dos testes feitos com filter em quickSort corresponde a um dos possíveis resultados de compare. Portanto, poderíamos ter escrito menores = filter (\y -> y `compare` x == LT) xs, por exemplo.

Escolhendo como comparar

Usando quickSort, ordenar qualquer lista com elementos Ord se torna bastante fácil. Suponha que você tenha uma lista de String e deseje ordena-la. Basta usar quickSort nessa lista. Pelo resto deste capítulo, vamos usar um dicionário com algumas palavras (um dicionários com milhares de palavras também funcionaria).

dicionario = ["Eu", "gosto", "muito", "de", "sistemas", "Linux"]

Escrever quickSort dicionario retorna:

*Main> quickSort dicionario
["Eu","Linux","de","gosto","muito","sistemas"]

Como pode-se ver, letras maiúsculas ou minúsculas influenciam na ordenação. Em Haskell, o tipo String é uma lista de caracteres Unicode, o qual especifica que o código para letras maiúsculas é menor que os de letras minúsculas. Assim, "Z" é menor que "a", por exemplo.

Para ordernarmos o dicionário corretamente, precisamos que quickSort seja insensível a capitalização. Para conseguirmos isso, primeiro vamos tornar evidente o uso de compare, como foi sugerido acima:

quickSort compare (x : xs) = (quickSort compare menores) ++ (x : iguais) ++ (quickSort compare maiores)
    where
        menores = filter (\y -> y `compare` x == LT) xs
        iguais  = filter (\y -> y `compare` x == EQ) xs
        maiores = filter (\y -> y `compare` x == GT) xs

Isso deixa claro que podemos substituir compare por qualquer função cuja anotação de tipo seja (Ord a) => a -> a -> Ordering. Se trocarmos compare como argumento c, podemos escrever uma nova função quickSort':

quickSort' :: (Ord a) => (a -> a -> Ordering) -> [a] -> [a]
quickSort' _ [] = []
quickSort' c (x : xs) = (quickSort c menores) ++ (x : iguais) ++ (quickSort c maiores)
    where
        menores = filter (\y -> y `c` x == LT) xs
        iguais  = filter (\y -> y `c` x == EQ) xs
        maiores = filter (\y -> y `c` x == GT) xs

A nova quickSort' pode ser usada de várias maneiras. Por exemplo, se quisermos inverter a ordem do resultado, bastaria fazer reverse (quickSort dictionary). Ou, para inverter a ordem sem precisar percorrer toda a lista usando reverse, basta usar uma função especial com quickSort':

ordemComum   x y = compare x y
ordemReversa x y = compare y x

Nota: Data.List tem uma função sort que não usa quick sort, mas um outro algoritmo chamado merge sort. Há também uma função como quickSort' chamada sortBy que permite que escolhamos qual função de comparação deve ser usada.

Exercícios
Escreva a função especial insensivel que faz com que quickSort' consiga ordernar dicionario de forma apropriada, isto é: *Main> quickSort' insensivel dicionario ["de","Eu","gosto","Linux","muito","sistemas"]

Funções de alta ordem e tipos

O conceito de currying já foi apresentado em outro capítulo. Agora temos uma bom motivo para revisar como currying funciona.

Muitas das vezes, a assinatura de tipo de uma função de alta ordem fornece dicas de como ela deve ser usada. Por exemplo, quickSort' tem o seguinte tipo: (a -> a -> Ordering) -> [a] -> [a]. Uma maneira simples de lê-lo seria: "quickSort' recebe como primeiro argumento, uma função que retorna a ordem de dois valores do tipo a, sendo que o segundo argumento é uma lista de as, e retorna uma nova lista de as." Isso já é o bastante para para supormos que quickSort' usa a ordem que sai do primeiro argumento para ordenar a lista do segundo argumento.

Perceba que os parênteses em volta de a -> a -> Ordering são obrigatórios. Eles especificam que a -> a -> Ordering formam um único argumento. Sem os parênteses, a assinatura de tipo ficaria a -> a -> Ordering -> [a] -> [a], o que significaria que a função recebe quatro argumentos ao todo, dos quais nenhum é uma função. Lembre-se que -> é associativo à direita, portanto, essa assinatura errada é o mesmo que a -> (a -> (Ordering -> ([a] -> [a]))), que é diferente de (a -> a -> Ordering) -> ([a] -> [a]), que é a versão correta com todos parênteses explícitos.

Escrevendo (a -> a -> Ordering) -> ([a] -> [a]) fica bastante evidente que quickSort' é uma função que gera funções parecidas com quickSort, bastando fornecer uma função de comparação, e assim teremos uma função resultante com a mesma assinatura que quickSort, que é [a] -> [a].

Exercícios

Este exercício combina o que já vimos sobre funções de alta ordem, recursividade e entrada/saída. Vamos recriar o conhecido laço de repetição for, bastante usado em linguagens de programação imperativas. Escreva a função for :: a -> (a -> Bool) -> (a -> a) -> (a -> IO ()) -> IO () for i p f acao = --... Um exemplo de uso seria for 1 (<10) (+1) print que imprime na tela os números de 1 a 9. O comportamento desejável para for é A partir de num valor inicial i, for checa se p i é verdadeiro; se for, então executa acao i, se não for, se encerra e não faz nada. Se acao i for executada, então executa f i e chega a condição p novamente como o novo valor: p (f i) e repete até que a condição p seja falsa. A descrição acima é imperativa. Sua tarefa é escrever for de forma funcional. Depois disso, tente: Escreva os números de 1 a 10 na tela. Dado que print é uma função, poderíamos simplesmente usar map print [1..10]. Mas funciona? Implemente a função sequenceIO :: [IO a] -> IO [a]. Dada uma lista de ações, esta função executa cada uma delas na ordem da lista e retorna uma lista com seus resultados. Escreva a função mapIO :: (a -> IO b) -> [a] -> IO [b] que recebe uma função a -> IO b e uma lista [b], executa uma ação em cada item da lista, e retorna seus resultados.

Manipulação de funções

Este capítulo se encerra discutindo alguns exemplos bastante comuns e úteis de funções de alta ordem. Estar familiarizado com elas aumenta bastante sua habilidade para escrever e entender códigos em Haskell.

Invertendo argumentos

A função flip está disponível no Prelude. Ela recebe uma função de dois argumentos e retorna a mesma função com argumentos trocados. Veja:

Prelude> :t flip
flip :: (a -> b -> c) -> b -> a -> c
Prelude> (flip (/)) 1 3
3.0
Prelude> (/) 1 3
0.3333333333333333
Prelude> map (*2) [1,2,3]
[2,4,6]
Prelude> (flip map) [1,2,3] (*2)
[2,4,6]

Por acaso, poderíamos ter usado flip para inverter a ordem de organização de quickSort' simplemente aplicando-a compare:

ordemComum   = compare
ordemInversa = flip compare

Composição

O operador de composição de funções (.) é outra função de alta ordem, cuja assinatura é:

(.) :: (b -> c) -> (a -> b) -> a -> c

(.) recebe duas funções como argumento e retorna uma nova função que aplica a segunda função e depois a primeira. Aprender a usar composição e funções de alta ordem é um grande bônus. Como pequeno exemplo, considere a função inits, definida no módulo Data.List. A documentação diz que ela "retorna todos os segmentos iniciais do argumento, começando pelo mais curto", portanto:

Prelude> :m + Data.List
Prelude Data.List> inits [1,2,3]
[[],[1],[1,2],[1,2,3]]

Podemos escrever inits numa única linha usando funções do Prelude (.), flip, scanl e map:

minhaInits :: [a] -> [[a]]
minhaInits = map reverse . scanl (flip (:)) []

Uma definição tão sucinta pode parece estranha e difícil de entender, mas tente analisar parte por parte que você perceberá seu funcionamento.

Ao contrário desta definição de minhaInits, que é bastante concisa e limpa, é perfeitamente possível escrever funções extremamente longas e confusas usando (.). Quando usado de forma consciente o estilo ponto livre -- isto é, sem explicitar os argumentos -- tem grande valor. Além disse, esta implementação é de "alto nível", no sentido em que não lidamos com detalhes específicos quanto ao tipo a ou usamos casamento de padrões ou recursão de forma explícita, pois as próprias funções de alta ordem já cuidam disso tudo.

Aplicação de funções

O operador ($) é um caso bastante curioso e extremamente útil. Você provavelmente já deve tê-lo visto em vários códigos Haskell, se andou praticando. Seu tipo é

($) :: (a -> b) -> a -> b

Ele recebe uma função como seu primeiro argumento e simplesmente aplica esta função ao seu segundo argumento. Portanto, (head $ "abc") == (head "abc").

Talvez você pense que ($) é completamente inútil, mas há dois pontos bastante interessantes. Primeiro, ($) tem prioridade de precedência bastante baixa, ao contrário de uma função comum que tem precedências mais altas. Parece confuso, mas, na prática, isso significa que podemos simplificar o uso de parênteses. Por exemplo:

Prelude> map (*2) (map (+1) [1..3])
[4,6,8]
Prelude> map (*2) $ map (+1) [1..3]
[4,6,8]

Além disso, como ($) é uma função que apenas aplica funções a um argumento, podemos usá-la para passar um mesmo argumento para uma lista de funções, por exemplo:

Prelude> map ($ 3) [(*2),(*7),(*10)]
[6,21,30]

uncurry and curry

Como o nome sugere, uncurry é uma função de desfaz curry, isto é, ela converte uma função de dois argumentos em uma função que recebe uma dupla como único argumento:

Prelude> :t uncurry
uncurry :: (a -> b -> c) -> (a, b) -> c
Prelude> let somaDupla = uncurry (+)
Prelude> :t somaDupla
somaDupla :: Num c => (c, c) -> c
Prelude> somaDupla (2,3)
5

Ela pode ser usada com ($) para aplicar uma função que estiver no primeiro elemento de uma dupla, ao segundo segundo elemento da dupla:

Prelude> uncurry ($) (reverse, "azul")
"luza"

Quanto a curry, ela faz o opost de uncurry, ou seja, recebe uma função que age sobre duplas e a torna aplicável a dois argumentos independentes:

Prelude> :t curry
curry :: ((a, b) -> c) -> a -> b -> c
Prelude> let soma = uncurry somaDupla
Prelude> :t soma
soma :: Num c => c -> c -> c
Prelude> soma 2 3
5

Já quem em Haskell todas as funções podem, por definição, ter curry, uncurry é muito mais comum, e curry bem menos usada.

id e const

Finalmente, apresentamos duas função que, apesar de não serem de alta ordem, são bastante comuns como argumento para funções de alta ordem. A função id é identidade, e const é constante. Cheque seus tipos no GHCi:

Prelude> :t id
id :: a -> a
Prelude> :t const
const :: a -> b -> a

A função identidade simplesmente repete o argumento de entrada como sendo a saída, enquanto que a função constante recebe dois argumentos, descarta o segundo e retorna o primeiro. Ela pode ser usada para criar uma função que sempre retorna um único valor:

Prelude> id 5
5
Prelude> id "oi"
"oi"
Prelude> const "inicio" "fim"
"inicio"
Prelude> let f = const 2
Prelude> f 1
2
Prelude> f 10
2

Ambas podem parecer inúteis por ora, mas quando começamos a lidar com funções de alta ordem, algumas vezes elas se tornam bastante necessárias, seja por precisamos não alterar algum valor, e portanto usamos id, ou por precisamos que um único valor seja usado sempre, quando usamos const.

Exercícios

Escreva a implementação de curry, uncurry, id e const Sem testar, descreva o que as seguintes funções fazem: uncurry const curry fst curry swap, sendo swap :: (a, b) -> (b, a) uma função de Data.Tuple que inverte a ordem dos elementos de uma dupla. Use foldr para implementar foldl. Dica: começo por revisar a seção sobre folds em Listas III. Há duas soluções: uma fácil e relativamente chata, e outra bastante interessante. Para a mais interessante, pense em como você comporia todas as funções numa lista.