Quicksort em Haskell

Olá pessoal, tudo certo?!

O que você sabe sobre programação funcional? Se a resposta for pouco, ou nada, recomendo dar dar uma boa olhada nesse e em outros paradigmas. Acredito que esse passeio por “outros mundos”  conduz a aprendizados importantes que nos tornam desenvolvedores melhores.

No post de hoje, apresento uma solução para ordenação QuickSort em Haskell. Importante observar que não se trata de uma solução ótima (principalmente quando falamos sobre utilização de memória). Entretanto, dá uma boa idéia do quanto programação funcional é eficiente para expressar alguns tipos de idéia.

Não pretendo construir uma série “Vamos aprender Haskell”, mas pretendo ir mostrando, a partir de hoje, cenários práticos onde Haskell é “uma mão na roda”.

Afinal, o que é Haskell?

Haskel é uma linguagem puramente funcional. Ou, em uma descrição mais completa extraída do site oficial:

Haskell is an advanced purely-functional programming language. An open-source product of more than twenty years of cutting-edge research, it allows rapid development of robust, concise, correct software. With strong support for integration with other languages, built-in concurrency and parallelism, debuggers, profilers, rich libraries and an active community, Haskell makes it easier to produce flexible, maintainable, high-quality software.

Se você ainda não conhece Haskell, talvez goste da idéia de praticar um pouco com a linguagem nesse tutorial on-line.

Há outras boas opções de linguagens funcionais, entre elas o F# da Microsoft (especialidade do @rodrigovidal). Optei por Haskell pela familiaridade que já tenho com essa linguagem.

Algumas palavras sobre programação funcional

O centro da programação funcional são … funções. A definição de funções, para esse escopo, se aproxima bastante com aquela que aprendemos na escola.

Em programação funcional, não podemos mudar o valor de uma variável. Uma vez que esse valor tenha sido especificado ele não poderá ser modificado.

Em programação puramente funcional, não há efeitos colaterais. A única coisa que uma função pode fazer é calcular algo e retornar o resultado. Se uma função for chamada duas vezes, com os mesmos parâmetros, deverá trazer o mesmo resultado.

O @rodrigovidal escreveu um ótimo post falando sobre o paradigma.

Antes de começar, o que precisamos baixar?

Para brincar com Haskell, você precisa de um editor de textos e de um compilador.

O compilador Haskell mais popular é o Glasgow Haskell Compiler (GHC). Para obter esse compilador, acesse http://hackage.haskell.org/platform. Há versões para Windows, Mac e Linux.

Utilizando Haskell de forma interativa

O GHC é um compilador capaz de converter código Haskell em binário. Entretanto, para hoje, consideremos a utilização da versão interativa.

Para utilizar o Haskell de forma interativa:

1. abra o prompt de comando (ou terminal, caso esteja utilizando Linux ou MacOS);
2. vá para uma pasta onde estará salvando seus scripts em Haskell;
3. digite GHCi

Pronto!

Para carregar um arquivo de script haskell, digite :l <nome-do-arquivo> <enter>.

Para regarregar um arquivo de scripts que tenha sido modificado, digite :r <enter>

Para encerrar o interpretador de Haskell, digite :q <enter>

Sempre importante destacar que Haskell é case-sensitive.

Alguns exemplos bacanas em Haskell (aquecimento para o Quicksort)

Se desejássemos saber o resultado da soma de todos os números pares entre 0 e 100, em Haskell, escreveríamos algo assim:

sum [x | x <- [0..100], even x]

Vamos fazer uma rápida análise do que escrevemos aqui:

1. em Haskell, tudo é resultado da execução de uma função;
2. a função sum, presente no início da linha, realiza a soma de todos os elementos providos como parâmetro.
3. a notação dos colchetes poderia ser lida como “para todo x, tal que x esteja entre 0 e 100 e seja par”.

Podemos escrever nossas próprias funções. Observe:

let sumEvensBetween x y = sum [v | v <- [x..y], even v]

O que eu fiz? Defini uma função que recebe dois parâmetros e executa, com esses números, a mesma operação que haviamos definido acima para o intervalo 0 e 100.

O modificador let, só é necessário no GHCi. Não deverá ser utilizado em scripts escritos a parte.

Se duas funções possuírem o mesmo nome, será selecionada aquela que atende melhor o padrão.

Haskell e o projeto Euler

Por influência do @juanplopes, resolvi começar minha participação no projeto Euler. Aliás, ele está mantendo um repositório com soluções para os problemas usando Boo (a propósito, Vamos aprender Boo). Segundo descrição do próprio site:

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

Então, vi que o @rodrigovidal havia resolvido o primeiro problema usando F#. Ele escreveu um post explicando o processo. O problema consiste em:

Add all the natural numbers below one thousand that are multiples of 3 or 5.

Criei duas soluções em Haskell para esse problema. Ambas podem ser testadas facilmente no GHCi.

sum [x | x <- [1..999], x `mod` 3 == 0 || x `mod` 5 == 0]

ou ainda:

sum [3, 6..999] + sum [5, 10..999] - sum [15, 30..999] 

É, ou não é, intuitivo?!

O que é QuickSort?

Se você é desenvolvedor, não deveria estar fazendo essa pergunta, mas …

Trata-se de um algoritmo para ordenação de uma lista contendo elementos que podem ser colocados em uma determinada ordem (números, por exemplo).

Tudo começa com uma lista que desejamos ordenar (por exemplo [6, 4, 3, 1, 7, 4, 2]). Então:

• Seleciona-se nessa lista um elemento que servirá como “pivot”, ou divisor. Esse elemento pode ser selecionado arbitrariamente (o primeiro, por exemplo);
• Todos os elementos com valor menor que o pivot são rearranjados à esquerda (antes) na lista;
• Todos os elementos com valor maior que o pivot são rearranjados à direita (depois) na lista;
• Recursivamente, executamos o mesmo procedimento com a lista esquerda e com a lista direita.

Ao fim do processo, temos uma lista ordenada.

Implementação do QuickSort em Haskell

Recomendo que você comece salvando o seguinte código em um arquivo com extensão .hs (quicksort.hs, por exemplo) em uma pasta qualquer.

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x: xs) = 
	let smallerOrEqual = [a | a <- xs, a <= x]
	    larger = [ a | a <- xs, a > x ]
	in quicksort smallerOrEqual ++ [x] ++ quicksort larger

Logo após, abra o console de comando (ou terminal) e vá até a pasta onde salvou o arquivo. Lá, execute o GHCi e carrege o arquivo digitando :l quicksort.hs.

Pronto! Agora, execute alguns testes.

Repare como uma string é compreendida como uma lista de caracteres.

Na prática, definimos duas “sobrecargas” para a função Quicksort:

1. na primeira, defino que se for passado um parâmetro vazio, retorno vazio
2. na segunda, reconheço uma tupla com um head x e com o tail xs e faço “a mágica acontecer”;

A sintaxe do Haskell pode parecer intimidante, em um primeiro momento. Há quem diga que aprender uma linguagem funcional se assemelha a aprender a programar outra vez. Entretanto, como mostrarei em outros posts, esse conhecimento pode valer a pena.

Por hoje, era isso