Haskell
Alunos: Bruno Triani
Ricardo Adão
Aloisio Cardozo
Nomeada em homenagem ao lógico Haskell Brooks Curry, como
uma base para linguagens funcionais.
É baseada no lambda calculus.
Haskell é funcional (isto é, tudo é feito com chamadas de
funções), estática, implicitamente tipada (os tipos são checados
pelo compilador, porém não é necessário declará-los),
preguiçosa (nada é feito até que se precise).
Haskell B. Curry (1900 - 1982)
História do Haskell
O conceito de avaliação preguiçosa já estava difundido
no meio acadêmico desde o final da década de 1970.
Esforços nessa área incluíam técnicas de redução de grafo
e a possibilidade de uma mudança radical na arquitetura de
von Neumann.
Conferência Functional Programming Languages and
Computer Architecture (FPCA '87) - setembro de 1987
criação de um comitê com o objetivo de construir um
padrão aberto para tais linguagens.
História do Haskell
A primeira reunião do comitê - janeiro de 1988, metas da
linguagem: linguagem e fácil ensino, completamente
descrita através de uma sintaxe e semântica formal
disponível livremente.
Primeira versão 1 de abril de 1990; versão 1.1 agosto de
1991, a versão 1.2 em março de 1992, versão 1.3 maio
de 1996 versão 1.4 em abril de 1997.
Haskell 98, janeiro de 1999 - versão mínima, estável e
portável da linguagem e o biblioteca para ensino. Esse
padrão sofreu uma revisão em janeiro de 2003.
História do Haskell
A linguagem continua evoluindo, sendo as
implementações Hugs e GHC consideradas os
padrões.
A partir de 2006 começou o processo de definição
de um sucessor do padrão 98, conhecido
informalmente por Haskell′
("Haskell Prime").
O que é programação funcional?
C, Java, Pascal, Ada, e assim por diante, são linguagens
imperativas. São "imperativas" no sentido em que consistem
em uma seqüencia de comandos, que são executados
estritamente um após o outro. Haskell é uma linguagem
funcional. Uma linguagem funcional é uma única expressão,
que é executada avaliando essa expressão. Qualquer um que
já usou uma planilha eletrônica, tem experiência em
programação funcional. Em uma planilha, especificamos o
valor de cada célula, em função dos valores de outras células.
O foco está em "o quê" deve ser computado, e não "como"
deve ser computado. Por exemplo:
-nós não especificamos a ordem em que as planilhas devem
ser computadas, ao invés disso, nós temos garantia que a
planilha será calculada em uma ordem que respeite suas
dependências.
-nós não dizemos à planilha como alocar sua memória - melhor,
esperamos apresentar-nos com um plano aparentemente infinito de
células, e alocar na memória somente as células que estão realmente em
uso.
-na maioria das vezes, avaliamos o valor das células por uma
"expressão" (cujas partes podem ser avaliadas em qualquer ordem),
melhor que por uma "seqüência de comandos" que compute seu valor.
O cálculo lambda é uma coleção de diversos sistemas formais
baseados em uma notação para funções inventada por Alonzo Church
em 1936 com o intuito de capturar os aspectos mais básicos da maneira
pela qual operadores ou funções podem ser combinados para formar
outros operadores.
O cálculo lambda serve como uma ponte entre linguagens funcionais de
alto nível e suas implementavéis de baixo nível. Raízes para a
apresentação do cálculo lambda como uma linguagem intermediária: uma
linguagem extremamente simples, consistindo de somente algumas
poucas construções sintáticas e de uma semântica simples.
Uma implementação do cálculo lambda necessita
somente suportar algumas construções simples.
A sua semântica simples nos permite analisar
facilmente a correção de sua implementação.
Trata-se de uma linguagem expressiva, a qual é
suficientemente poderosa para expressar todos os
programas funcionais e, por conseguinte, todas as
funções computáveis. Isto significa que, se uma boa
implementação do cálculo lambda é disponível, podese implementar qualquer linguagem funcional através
da implementação de um compilador desta para o
cálculo lambda.
Estilo
Estilo Imperativo
Imperativo
programa: sequência de
comandos que transformam
variáveis
X
Estilo
Estilo Funcional
Funcional
programa: é uma funçao composta
por funções mais simples
base: expressões, funções
base: variáveis, comandos,
procedures
execução: baseada em
recursividade
execução: conceito de sequência
variáveis: mudanças de estado,
alteração por atribuição
nomes identificam valores
permanentes (const), transparência
referencial
estado: implícito, modificado por
atribuições
estado: explícito, modificado por
funções
componentes de primeira classe:
variáveis
componentes de primeira classe:
funções
Metalinguagem de Haskell:
Em haskell, a metalinguagem é encontrada no uso de comentários. Alguns
tokens léxicos encontrados são apresentados a seguir:
Comentár
ios:
Comentário
de bloco: é feito pelos delimitadores {- e -}.
Comentário de linha: o início do comentário é definido pelos sinais menos
duplo (--).
Definição de
condicionais:
Determinamos
condicionais para determinar qual o fluxo de execução
atende melhor as nossas necessidades. Nesse caso, o escopo é
definido pelo uso de delimitadores como o then:
if<condicao> then <comando>
else<comando2> | <condicao1>=<comando1>|
<condicao2>=<comando2>
Entrando no mundo do Haskell
Passo 1: Baixar e Instalar o compilador
- GHC Compilador e interpretador (GHCi).
(http://www.
haskell.org/ghc/)
- Hugs Unicamente interpretador. Portátil
e mais leve do que o
GHC.
(http://www.haskell.org/hugs/)
Passo 2 : Iniciar
1. Abra um terminal
2.
- Se você instalou o GHC, digite ghci(o nome do
executável
do interpretador GHC) no promt de comando.
- Se você instalou Hugs, digite hugs.
Passo 3: Escreva o primeiro programa
Prelude> “Hello, World!”
“Hello, World!”
O Haskell imprimiu o resultado.
>>> Você pode tentar uma variação para imprimir diretamente
a saída padrão:
Prelude> putStrLn “Hello World”
Hello World
Usando um compilador Haskell, você pode compilar o
código para
para um executável standalone . Crie um arquivo fonte
hello.hs
contendo:
main = putStrLn "Hello, World!"
E compile o arquivo com:
$ ghc -o hello hello.hs
>>> Você pode então correr o executável (./hello no Unix
hello.exe
e no Windows):
$ ./hello
Hello, World!
Expressões simples
Você pode digitar a maioria das expressões matemáticas diretamente no
ghci. Prelude> é o prompt padrão do GHCi.
Prelude> 3 * 5
15
Prelude> 4 ^ 2 - 1
15
Prelude> (1 - 5)^(3 * 2 - 4)
16
Strings estão em aspas duplas. Você pode concatená-las usando ++.
Prelude> "Hello"
"Hello"
Prelude> "Hello" ++ ", Haskell"
"Hello, Haskell"
As chamadas das funções são feitas colocando se os
argumentos diretamente depois da da função. Não
existem parênteses para a chamada:
Prelude> succ 5
6
Prelude> truncate 6.59
6
Prelude> round 6.59
7
Prelude> sqrt 2
1.4142135623730951
Prelude> not (5 < 3)
True
Prelude> gcd 21 14
7
I/O (Entrada / Saída)
Ações de I/O podem ser usadas para ler e escrever a partir do próprio
console. Algumas são descritas abaixo.
Prelude> putStrLn "Hello, Haskell"
Hello, Haskell
Prelude> putStr "No newline"
No newlinePrelude> print (5 + 4)
9
Prelude> print (1 < 2)
True
As funções putStr e putStrLn tem strings como saída para o terminal. A
função print gere saída seja qual for o tipo. (Se você usar print para uma
string, ela terá aspas duplas.) Se você precisar de múltiplas ações de I/O
numa única expressão, você pode usar o bloco do. As ações são separadas
por ponto e vírgula.
Prelude> do { putStr "2 + 2 = " ; print (2 + 2) }
2+2=4
Prelude> do { putStrLn "ABCDE" ; putStrLn "12345" }
ABCDE
12345
A leitura pode ser feita com o getLine (no qual retorna uma
String) ou readLn (no qual retorna qualquer tipo de valor que
você deseje). O símbolo <- é usado para atribuir um nome ao
resultado da ação I/O.
Prelude> do { n <- readLn ; print (n^2) }
4
16
(O 4 era a entrada. O 16 foi o resultado)
Existe também uma outra maneira de escrever blocos. Se você não
colocar chaves e ponto e virgula, a identação se torna relevante. Isto
não funciona tão bem no ghci, por isso é recomendado que ponha o
código num arquivo (ex.: teste.hs) e compile.
main = do putStrLn "What is 2 + 2?"
x <- readLn
if x == 4
then putStrLn "You're right!"
else putStrLn "You're wrong!"
Uma forte característica da linguagem Haskell é
sua “tipagem” (strongly typed), isto é, é sempre
possível determinar o tipo de uma determinada
entidade. Em contra-ponto podemos fazer uma
analogia com linguagens sem tipos, ou melhor,
linguagens onde todas entidades partilham de
um mesmo tipo, como é o caso de LISP.
Podemos citar os seguintes tipos base de
Haskell no slide seguinte:
Tipo unitário: é uma implementação do conjunto um, sendo assim,
todos os demais tipos derivam desse.
Tipo lógico (bool): valores lógicos, podendo assumir como valores:
true, false, otherwise (= true). Podem ser submetidos aos
seguintes operadores: && (conjunção); || (disjunção); not
(negação).
Tipo caracter (char): valores Unicode do nosso alfabeto, podendo
assumir como valores símbolos da tabela Unicode (16bits).
Tipo numérico: valores numéricos, inteiros (int, integer), e reais
(float, double).
Listas: conjunto das seqüências finitas, eventualmente vazias, de
elementos de um dado tipo. Dentre todos operadores podemos
citar: last – retorna último elemento de uma lista; init – retorna o
primeiro elemento de uma lista; ++ - realiza a concatenação entre
duas listas. Seqüências de caracteres (Strings): podem ser
considerados como uma lista de caracteres.
Utilizamos o comando type para setar o
interpretador a mostrar informações sobre o
tipo das expressões manipuladas no decorrer
da seção. A avaliação de uma expressão por
parte do interpretador é realizada normalmente
(esquerda para direita). Podendo o mesmo ser
setado para que informe dados estatísticos a
respeito das alterações realizadas (:set +s).
A definição de funções deve ser realizada em um novo arquivo, o
qual deverá possuir a extensão “.hs” através do comando load
<file> as funções declaradas são disponibilizadas.
A definição de uma função é realizada através da escrita de uma
equação, a qual irá determinar o comportamento da mesma. Devese obedecer a seguinte sintaxe:
<nome_da_funcao>
<argumento> = <expressão>
A linguagem Haskell não suporta mais de um argumento. Esse
problema pode ser resolvido agrupando seus argumentos em um
n-duplo:
<funcao> :: (Int, Int) -> Int
<funcao> <arg1, arg2> = <command>
Ao invés de usar equações para definir funções, pode-se
utilizar uma notação lambda, em que a função não precisa
ter um nome. Por exemplo, a função sucessor :: Int ->
Int sucessor x = x+1 poderia ser definida como lx. x+1 na
notação lambda, ou \x -> x + 1 em Haskell. Temos então
Haskell > (\x -> x + 1) 10 11. Da mesma maneira a função
soma poderia ter sido definida da seguinte maneira:
soma = \ x y -> x + y
O operador de composição de funções é definido utilizando
a sintaxe lambda:
(.) :: (u -> v) -> (t -> u) -> (t -> v)
f . g = \x -> f (g x)
Tipos Simples:
Até agora, nenhuma declaração de variável foi mencionada. Isto é
porque Haskell faz dedução de tipos. Você geralmente não tem que
declarar tipos a não ser que você queira. Se quiser declarar ponha ::
para tal. Veja abaixo:
Prelude> 5 :: Int
5
Prelude> 5 :: Double
5.0
Tipos (e “classes tipo”, veremos mais adiante) sempre iniciam com letras
maiúsculas em Haskell. Variáveis sempre iniciam com letras minúsculas
Isto é uma regra, não uma convenção da linguagem.
Você pode também perguntar ao ghci que tipo foi escolhido para
alguma coisa. Isto é útil porque geralmente você não precisa declarar
seus tipos.
Prelude> :t True
True :: Bool
Prelude> :t 'X'
'X' :: Char
Prelude> :t "Hello, Haskell"
"Hello, Haskell" :: [Char]
(Como é notado neste caso, [Char] é outra
maneira de dizer String.)
Um pouco mais interessante, agora com número.
Prelude> :t 42
42 :: (Num t) => t
Prelude> :t 42.0
42.0 :: (Fractional t) => t
Prelude> :t gcd 15 20
gcd 15 20 :: (Integral t) => t
Estes tipos usam “classes tipo”. Quer dizer:
42 pode ser usado como um tipo numérico qualquer. (Este é
o porque de anteriormente eu ter declarado 5 como Int ou
Double).
42.0 pode ser qualquer tipo fracionário, mas não um tipo
inteiro.
gcd 15 20 (no qual é uma chamada de função) pode ser
Existem cinco tipos numéricos no Haskell “prelude”
(a parte da biblioteca que existe sem ter que importar
nada):
Int é um inteiro com no máximo 30 bits de precisão.
Integer é um inteiro sem limitação de precisão.
Float precisão simples de ponto flutuante.
Double precisão mais aprimorada de ponto flutuante.
Rational tipo fracionário, sem nenhum erro de
arredondamento.
Todos os cinco são instancias da classe tipo Num.
Os dois primeiros são instancias do Integral, e os
outros três são instancias do Fractional.
Dados estruturados
Tipos básicos de dados podem ser combinados em duas maneiras:
listas, na qual colocamos [entre colchetes], e tuplas que ficam (entre
parênteses).
Listas são usadas para agrupar multiplos valores do mesmo tipo.
Prelude> [1, 2, 3]
[1,2,3]
Prelude> [1 .. 5]
[1,2,3,4,5]
Prelude> [1, 3 .. 10]
[1,3,5,7,9]
Prelude> [True, False, True]
[True,False,True]
Strings são apenas listas de caracteres.
Prelude> ['H', 'e', 'l', 'l', 'o']
"Hello"
O operador : (dois pontos), coloca um item no início da
lista.
Prelude> 'C' : ['H', 'e', 'l', 'l', 'o']
"Chello"
Tuplas mantem um numero fixo de valores, no qual
pode haver diferentes tipos.
Prelude> (1, True)
(1,True)
Prelude> zip [1 .. 5] ['a' .. 'e']
[(1,'a'),(2,'b'),(3,'c'),(4,'d'),(5,'e')]
O ultimo exemplo, é usado zip, uma função da
biblioteca que transforma duas listas em uma tupla.
Os tipos que provavelmente esperamos.
Prelude> :t ['a' .. 'c']
['a' .. 'c'] :: [Char]
Prelude> :t [('x', True), ('y', False)]
[('x', True), ('y', False)] :: [(Char, Bool)]
As listas são muitos usadas em Haskell. Abaixo algumas
funções úteis.
Prelude> [1 .. 5]
[1,2,3,4,5]
Prelude> map (+ 2) [1 .. 5]
[3,4,5,6,7]
Prelude> filter (> 2) [1 .. 5]
[3,4,5]
Prelude> fst (1, 2)
1
Prelude> snd (1, 2)
2
Prelude> map fst [(1, 2), (3, 4), (5, 6)]
Definições de funções
Como já demonstrado anteriormente, uma ação I/O, chamada main:
main = do putStrLn "What is 2 + 2?"
x <- readLn
if x == 4
then putStrLn "You're right!"
else putStrLn "You're wrong!"
Agora, temos uma função chamando outra função:
factorial n = if n == 0 then 1 else n * factorial (n - 1)
main = do putStrLn "What is 5! ?"
x <- readLn
if x == factorial 5
then putStrLn "You're right!"
else putStrLn "You're wrong!"
Compilando de novo com ghc-make Teste.hs. E,
$ ./Test
What is 5! ?
120
You're right!
Temos um função, podendo ser chamada como fatorial 5 sem
precisar usar parênteses Agora perguntamos ao ghci o tipo.
$ ghci Test.hs
<< GHCi banner >>
Ok, modules loaded: Main.
Prelude Main> :t factorial
factorial :: (Num a) => a -> a
Tipos de funções são escritas com um tipo de argumento, depois
->, depois o tipo do resultado. A função fatorial também pode ser
simplificada sendo escrita com analise de caso.
factorial 0 = 1
factorial n = n * factorial (n - 1)
Sintaxes convenientes
Algumas outras sintaxes que podem ser úteis.
secsToWeeks secs = let perMinute = 60
perHour = 60 * perMinute
perDay = 24 * perHour
perWeek = 7 * perDay
in secs / perWeek
A expressão let define nomes temporários.
classify age = case age of 0 -> "newborn"
1 -> "infant"
2 -> "toddler"
_ -> "senior citizen"
Quicksort in C
// To sort array a[] of size n: qsort(a,0,n-1)
void qsort(int a[], int lo, int hi) {
{
int h, l, p, t;
if (lo < hi) {
l = lo;
h = hi;
p = a[hi];
do {
while ((l < h) && (a[l] <= p))
l = l+1;
while ((h > l) && (a[h] >= p))
h = h-1;
if (l < h) {
t = a[l];
a[l] = a[h];
a[h] = t;
}
} while (l < h);
a[hi] = a[l];
a[l] = p;
qsort( a, lo, l-1 );
qsort( a, l+1, hi );
}
}
Quicksort in Haskell
qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
A primeira linha lê-se: "Quando você classifica uma lista vazia
( [] ), o resultado é uma outra lista vazia".
A segunda linha diz: "Para ordenar uma lista cujo primeiro
elemento é chamado x e o resto do que é chamado xs ,
classificar os elementos de xs , que são menos de x ,
classificar os elementos de xs , que são iguais ou superiores
a x , e concatenar ( + + ) os resultados, com x colada no
meio.
Programa Exemplo:
-- script tabela
-- banco de dados das notas:
aluno :: Int -> Float
aluno 1 = 7.5
aluno 2 = 10
aluno 3 = 9
aluno 4 = 6.3
-- (...)
tabela :: Int -> String
tabela n = cabeçalho ++ imprimeAlunos n ++
imprimeMedia n
cabeçalho :: String
cabeçalho = “Aluno Nota\n”
imprimeAlunos :: Int -> String
imprimeAlunos 1 = imprimeAluno 1
imprimeAlunos n = imprimeAlunos (n-1) ++ imprimeAluno n
imprimeAluno :: Int -> String
imprimeAluno n = show n ++ “ “ ++ show (aluno n) ++ “\n”
imprimeMedia :: Int -> String
imprimeMedia n = “\n” ++ “Média da Turma: “ ++ show
(media n)
soma :: Int -> Float
soma 1 = aluno 1
soma n = aluno n + soma (n-1)
media :: Int -> Float
media n = (soma n) / (fromInt n)
procuraValor :: Arvore -> Int ->Bool
procuraValor Null num = False
procuraValor (Node valor esq dir) num
| valor == num = True
| otherwise = False || (procuraValor esq num) ||
(procuraValor dir num)
Evolução
Características do Haskell incluem o suporte a funções recursivas e tipos de
dados, casamento de padrões, list comprehensions, guard statements e
avaliação preguiçosa, esta, um elo em comum entre os diversos grupos de
desenvolvimento da linguagem. A combinação destas características pode
fazer com que a construção de funções que seriam complexas em uma
linguagem procedimental de programação tornem-se uma tarefa quase
trivial em Haskell.
Segundo dados de 2002, é a linguagem funcional sobre a qual mais
pesquisa está sendo realizada. Muitas variantes tem sido desenvolvidas:
versões paralelizáveis do MIT e Glasgow, ambas chamadas Parallel Haskell,
outras versões paralelas e distribuidas chamadas Distributed Haskell
(anteriormente Goffin) e Eden, uma versão chamada Eager Haskell e várias
versões orientadas a objetos: Haskell++, O'Haskell e Mondrian.
Uma versão educacional do Haskell chamada Gofer foi desenvolvida por
Mark Jones. Ela é oferecida pelo HUGS. Existe também uma versão do
Haskell que permite orientação a aspectos (POA), chamada AspectH.
Haskell tem um amplo uso comercial, de aeronaves e defesa,
finanças, complementos web, empresas de design de hardware, etc.
ABN AMRO Amsterdã, Holanda
ABN AMRO é um banco internacional sediado em Amsterdã. É usado para medir
os riscos de investimentos dos portifólios.
AT&T
Haskell é usado na divisão de segurança para automatizar
processos de reclamações sobre abusos na internet.
www.haskell.org
www.haskell.edu/haskell
www.haskell.org/haskell-history.html
http://pt.wikipedia.org/wiki/Haskell_
(linguagem_de_programação)
http://www.haskell.
org/haskellwiki/Learn_Haskell_in_10_minutes
http://hackage.haskell.org/platform/
http://www.haskell.org/ghc/download_ghc_6_12_1.
html
http://www.macs.hw.ac.
uk/~dubois/ProgramacaoHaskell.pdf