# Haskell/Funções de alta ordem

* Funções de alta ordem
* Básico
* Recursividade
* Listas II (listas infinitas, map)
* Listas III (folds, compreensão)
* Declaração de tipos
* Lambdas e operadores
* Casamento de padrões
* Estruturas de controle: case
* Funções de alta ordem
* Usando o GHCi
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.
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 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).
Escrever quickSort dicionario retorna:
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:
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':
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':
* 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:
Por acaso, poderíamos ter usado flip para inverter a ordem de organização de quickSort' simplemente aplicando-a compare:

### Composição

O operador de composição de funções (.) é outra função de alta ordem, cuja assinatura é:
(.) 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:
{{HaskellGHCi|1= 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:
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 é
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:
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:

### 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:
Ela pode ser usada com ($) para aplicar uma função que estiver no primeiro elemento de uma dupla, ao segundo segundo elemento da dupla:
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:
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:
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:
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.
* ↑ A versão original de pode sim ser feita em Haskell, mas ela exige algumas ferramentas mais avançadas que não serão discutidas aqui.
* ↑ Para relembrar, precedência tem o mesmo sentido que operações multiplicação e divisão devem ser realizadas antes das operações de soma e subtração, por exemplo.