Haskell/Funções de alta ordem: diferenças entre revisões

[edição verificada][revisão pendente]
Conteúdo apagado Conteúdo adicionado
mSem resumo de edição
m <source> -> <syntaxhighlight> (phab:T237267)
 
Linha 8:
Como exemplo concreto, considere o problema de ordenar uma lista. [[w:Quick sort|''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.
 
<sourcesyntaxhighlight lang="haskell">
-- Assinatura de tipo: qualquer lista cujos elementos pertençam à classe Ord podem ser ordenados
quickSort :: (Ord a) => [a] -> [a]
Linha 21:
maiores = filter (> x) xs
iguais = filter (== x) xs
</syntaxhighlight>
</source>
 
Deve-se observar que nosso <code>quickSort</code> é bem simples. Uma versão mais eficiente evitaria chamar <code>filter</code> três vezes, e também não usaria <code>(++)</code> 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.<ref>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.</ref> 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.
Linha 29:
Quase todos os tipos básico em Haskell pertecem à classe <code>Ord</code>, que trata de comparações de ordenação, assim com a classe <code>Eq</code> trata de testes de igualdade. <code>Ord</code> define qual ordem é "natural" para um certo tipo. Ela fornece a função chamada <code>compare</code> cujo tipo é
 
<sourcesyntaxhighlight lang="haskell">
compare :: (Ord a) => a -> a -> Ordering
</syntaxhighlight>
</source>
 
<code>compare</code> toma dois valores e os compara, retornando um valor do tipo <code>Ordering</code>, que pode ser
Linha 45:
Usando <code>quickSort</code>, ordenar qualquer lista com elementos <code>Ord</code> se torna bastante fácil. Suponha que você tenha uma lista de String e deseje ordena-la. Basta usar <code>quickSort</code> 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).
 
<sourcesyntaxhighlight lang="haskell">
dicionario = ["Eu", "gosto", "muito", "de", "sistemas", "Linux"]
</syntaxhighlight>
</source>
 
Escrever <code>quickSort dicionario</code> retorna:
Linha 60:
Para ordernarmos o dicionário corretamente, precisamos que <code>quickSort</code> seja insensível a capitalização. Para conseguirmos isso, primeiro vamos tornar evidente o uso de <code>compare</code>, como foi sugerido acima:
 
<sourcesyntaxhighlight lang="haskell">
quickSort compare (x : xs) = (quickSort compare menores) ++ (x : iguais) ++ (quickSort compare maiores)
where
Linha 66:
iguais = filter (\y -> y `compare` x == EQ) xs
maiores = filter (\y -> y `compare` x == GT) xs
</syntaxhighlight>
</source>
 
Isso deixa claro que podemos substituir <code>compare</code> por qualquer função cuja anotação de tipo seja <code>(Ord a) => a -> a -> Ordering</code>. Se trocarmos <code>compare</code> como argumento <code>c</code>, podemos escrever uma nova função <code>quickSort'</code>:
 
<sourcesyntaxhighlight lang="haskell">
quickSort' :: (Ord a) => (a -> a -> Ordering) -> [a] -> [a]
quickSort' _ [] = []
Linha 78:
iguais = filter (\y -> y `c` x == EQ) xs
maiores = filter (\y -> y `c` x == GT) xs
</syntaxhighlight>
</source>
 
A nova <code>quickSort'</code> pode ser usada de várias maneiras. Por exemplo, se quisermos inverter a ordem do resultado, bastaria fazer <code>reverse (quickSort dictionary)</code>. Ou, para inverter a ordem sem precisar percorrer toda a lista usando <code>reverse</code>, basta usar uma função especial com <code>quickSort'</code>:
 
<sourcesyntaxhighlight lang="haskell">
ordemComum x y = compare x y
ordemReversa x y = compare y x
</syntaxhighlight>
</source>
 
{{Nota|1= <code>Data.List</code> tem uma função <code>sort</code> que não usa ''quick sort'', mas um outro algoritmo chamado ''merge sort''. Há também uma função como <code>quickSort'</code> chamada <code>sortBy</code> que permite que escolhamos qual função de comparação deve ser usada.}}
Linha 151:
Por acaso, poderíamos ter usado <code>flip</code> para inverter a ordem de organização de <code>quickSort'</code> simplemente aplicando-a <code>compare</code>:
 
<sourcesyntaxhighlight lang="haskell">
ordemComum = compare
ordemInversa = flip compare
</syntaxhighlight>
</source>
 
=== Composição ===
Linha 160:
O operador de composição de funções <code>(.)</code> é outra função de alta ordem, cuja assinatura é:
 
<sourcesyntaxhighlight lang="haskell">(.) :: (b -> c) -> (a -> b) -> a -> c</sourcesyntaxhighlight>
 
<code>(.)</code> 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 <code>inits</code>, definida no módulo <code>Data.List</code>. A documentação diz que ela "retorna todos os segmentos iniciais do argumento, começando pelo mais curto", portanto:
Linha 172:
Podemos escrever <code>inits</code> numa única linha usando funções do Prelude <code>(.)</code>, <code>flip</code>, <code>scanl</code> e <code>map</code>:
 
<sourcesyntaxhighlight lang="haskell">
minhaInits :: [a] -> [[a]]
minhaInits = map reverse . scanl (flip (:)) []
</syntaxhighlight>
</source>
 
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.
Linha 185:
O operador <code>($)</code> é 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 é
 
<sourcesyntaxhighlight lang="haskell">
($) :: (a -> b) -> a -> b
</syntaxhighlight>
</source>
 
Ele recebe uma função como seu primeiro argumento e simplesmente aplica esta função ao seu segundo argumento. Portanto, <code>(head $ "abc") == (head "abc")</code>.