Programação Haskell

Programação Haskell

(Parte 1 de 3)

André Rauber Du Bois

Programação Funcional com a Linguagem Haskell

André Rauber Du Bois dubois@macs.hw.ac.uk

André Rauber Du Bois

CAPÍTULO 1 – Programação em Haskell4
1.1 Expressões e Funções4
1.2. Inteiros6
1.4 Caracteres e Strings9
1.5 Números em Ponto Flutuante11
1.6 Tuplas12
CAPÍTULO 2 – Listas em Haskell18
2.1 Listas18
2.3 Funções sobre Listas20
2.5 Definições26
2.6 Outras Funções Úteis sobre Listas30
CAPÍTULO 3 – Conceitos Avançados37
3.2 Composição de Funções39
CAPÍTULO 4 – Classes de Tipo43
4.1 Classes de Tipo43
4.2 Classes Derivadas45
4.4 Algumas Classes Importantes47
4.4.2 Read e Show48

André Rauber Du Bois

CAPÍTULO 5 – Tipos Algébricos50
5.3 Tipos Algébricos Polimórficos55
CAPÍTULO 6 – Abstract Data Types57
6.1 Abstract Data Type (ADT)57
6.2 Exemplo de ADT (Conjuntos)58
CAPÍTULO 7 – IO68
7.1 Interação com o Usuário68
7.2 Arquivos70
CAPÍTULO 7 – Construção de Módulos74

André Rauber Du Bois

CAPÍTULO 1 – Programação em Haskell

1.1 Expressões e Funções

A idéia principal da linguagem Haskell é baseada na avaliação de expressões. A implementação da linguagem avalia (simplifica) a expressão passada pelo programador até sua forma normal. Por exemplo:

Haskell >”Alô Mundo!!” “Alô Mundo!!”

Neste exemplo foi passada para o interpretador Haskell a string (seqüência de caracteres) “Alô Mundo!!”. O sistema respondeu com a mesma seqüência de caracteres, pois esta expressão não pode mais ser avaliada, já encontra-se normalizada. Pode-se utilizar comandos mais complexos:

Haskell> 4 + 3 7 ou

Um comando em Haskell é uma fórmula escrita na sintaxe da linguagem. Em Haskell existem várias funções pré-definidas que podem ser usadas para a construção de expressões:

Haskell> reverse “Alô Mundo!!” “!!odnuM ôlA”

André Rauber Du Bois

A função reverse inverte a ordem dos caracteres em uma string. Apesar de existirem várias funções pré-definidas, a grande idéia da programação funcional é que o usuário defina as suas próprias funções. As funções do usuário são definidas em scripts. Um script contém definições de funções associando nomes com valores e tipos. Em scripts da linguagem Haskell também existem comentários que facilitam uma leitura posterior. Tudo o que for escrito depois de dois travessões (--) é considerado comentário e não é interpretado. Segue um exemplo de script:

-- -- exemplo.hs

-- Neste script apresentam-se algumas definições simples idade :: Int -- Um valor inteiro constante idade = 17 maiorDeIdade :: Bool -- Usa a definição de idade maiorDeIdade = (idade>=18) quadrado :: Int -> Int -- função que eleva um número ao quadrado quadrado x = x * x mini :: Int -> Int -> Int -- função que mostra o menor valor entre dois inteiros mini a b | a <= b = a

| otherwise = b

André Rauber Du Bois

A primeira linha de uma definição é a declaração de tipo. A notação ‘::’ pode ser lida como ‘possui tipo’. Então idade tem tipo Int, que em Haskell é o tipo dos números inteiros. A linha seguinte atribui o valor 17 para idade.

Na definição seguinte é introduzido o tipo Booleano, que pode ter dois valores,

True ou False. No caso, maiorDeIdade tem o valor False pois 17 (valor de idade) é menor do que 18. Na definição de maiorDeIdade foi utilizada a definição de idade. Em Haskell uma definição pode usar qualquer outra definição do mesmo script.

Em scripts encontra-se também definições de funções. A função quadrado no exemplo, é uma função que vai do tipo Int para o tipo Int. A função através de seu argumento calcula uma resposta utilizando uma equação (x * x) que está no lado direito da definição. Por exemplo, se passarmos para o interpretador a função quadrado e como argumento utilizarmos o valor 2 teremos:

Haskell> quadrado 2 4

A função mini devolve o menor valor entre os seus dois argumentos, que são valores do tipo Int. Para se obter a resposta, testam-se os valores para se decidir qual é o menor. Para isso são usados guards que são expressões booleanas iniciadas por uma barra |. No exemplo, se o valor de a é menor ou igual que b a resposta é a, senão passa-se para o próximo guard. Temos então a expressão otherwise, que sempre possui a resposta se todos os outros guards falharem. Ex:

Haskell > mini 2 3 2 Outros detalhes sobre scripts, serão apresentados no decorrer do texto.

1.2. Inteiros

O tipo Int é o tipo dos números inteiros em Haskell. Este tipo possui alguns operadores e funções:

André Rauber Du Bois

+, * Soma e multiplicação de inteiros

- Serve para mudar o sinal de um inteiro ou para fazer a subtração

Tabela 1. Operadores do Tipo Int div Divisão de números inteiros; div 10 3 é 3 mod O resto de uma divisão de inteiros; mod 10 3 é 1 abs Valor absoluto de um inteiro (remove o sinal).

negate Muda o sinal de um inteiro.

Tabela 2. Funções do Tipo Int

como um operador, basta incluir o operador entre parênteses (), e a função entre crases

Qualquer operador pode ser usado como função, e qualquer função pode ser usada Ex:

Haskell> 10 mod 3 1 O programador pode definir os seus próprios operadores em scripts:

Ex:

-- script do meu primeiro operador (&&&) :: Int -> Int -> Int a &&& b | a < b = a

| otherwise = b

André Rauber Du Bois

Pode-se trabalhar com ordenação e igualdade com os números inteiros, assim como com todos os tipos básicos. As funções de ordenação e igualdade tem como argumento dois números inteiros e devolvem um valor do tipo Bool:

> Maior que

>= Maior ou igual

== Igual

/= Diferente

<= Menor ou igual

< Menor

Tabela 3. Ordenação e Igualdade

Ex:

Haskell> 29 > 15 True

1.3 Booleanos

O tipo Bool é o tipo dos valores booleanos True (Verdadeiro) ou False (Falso). Os operadores booleanos são:

not negação

Tabela 4. Operadores Booleanos

Exemplo de definição utilizando Booleanos:

André Rauber Du Bois

O ou exclusivo poderia ser definido utilizando patterns ao invés de uma fórmula:

ouEx True x = not x ouEx False x = x

Este tipo de definição utiliza mais de uma equação. No exemplo, na primeira linha da definição, se for passado um valor True e um outro valor qualquer, a resposta será a negação deste valor. Se não ocorrer este caso, passa-se para a segunda linha em que se passa como argumento um valor False e um outro valor qualquer, que será a resposta.

1.4 Caracteres e Strings

O tipo Char é o tipo composto de caracteres, dígitos e caracteres especiais, como nova linha, tabulação, etc. Caracteres individuais são escritos entre aspas simples: ‘a’ é o caracter a e ‘7’ é o caracter sete. Alguns caracteres especiais são representados da seguinte maneira:

‘\t’ Tabulação

‘\n’ Nova linha

‘\’ ’ Aspas simples (‘)

Tabela 5. Caracteres Especiais

-- ou exclusivo ouEx :: Bool -> Bool -> Bool ouEx x y = (x || y) && not (x && y)

André Rauber Du Bois

Os caracteres são ordenados internamente pela tabela ASCII. Por isso:

Haskell> ‘a’ < ‘z’ True

Haskell> ‘A’< ‘a’ True

Pode-se utilizar a barra para representar o caracter por seu número:

Existem funções que transformam um número em caracter, e um caracter em número inteiro, baseando-se na tabela ASCII. Respectivamente:

chr :: Int -> Char ord :: Char -> Int

Listas de caracteres pertencem ao tipo String, e podem ser representados entre aspas duplas:

“Alô Mundo!!” “Haskell”

Ex:

Haskell> “Haskell é\nLegal !!” “Haskell é Legal”

André Rauber Du Bois

Listas podem ser concatenadas usando o operador (++). Ex:

Haskell > “Preciso de” ++ “\nfrases “ ++ “melhores” “Preciso de frases melhores”

A linguagem Haskell permite que se de sinônimos aos nomes de tipos. Exemplo: type String = [Char]

Isto quer dizer que o tipo String é um sinônimo de uma lista de caracteres. Ex:

O assunto listas será analisado mais profundamente no decorrer do texto.

1.5 Números em Ponto Flutuante

Existe em Haskell o tipo Float, que trabalha com números fracionários que são representados em ponto flutuante. Pode-se escrever os números com casas decimais ou utilizando notação científica; aceitar os operadores (+, - , *, , = =, /=, <=,>=, <, >) vistos anteriormente, possui algumas funções próprias:

André Rauber Du Bois

/ Float -> Float -> Float Divisão

** Float -> Float -> Float Exponenciação, x ** x = xy

Cos, sin, tan Float -> Float Coseno, seno e tangente log Float -> Float Logaritmo base e logBase Float -> Float -> Float Logaritmo em qualquer base (primeiro argumento é a base) read String -> Float Converte uma string representando um real, em seu valor show Float -> String Converte um número para uma string sqrt Float -> Float Raiz quadrada fromInt Int -> Float Converte um Int para um Float pi Float Constante Pi

Tabela 6. Funções do tipo Float

1.6 Tuplas

Uma tupla em Haskell é uma agregação de um ou mais componentes. Estes componentes podem ser de tipos diferentes. As tuplas são representadas em scripts por listas de componentes separados por vírgula, entre parênteses. O tipo de uma tupla parece uma tupla, mas possui tipos como componentes. Ex:

-- script com tuplas Type Nome = String -- Sinônimo para String (Nome) Type Idade = Int -- Sinônimo para Int (Idade) verIdade :: (Nome, Idade) -> Idade -- Função que se passa uma tupla verIdade (a,b) = b -- (Nome, Idade), e devolve a idade

André Rauber Du Bois

Então:

Haskell > verIdade (“André”, 21) 21

1.7 Funções Recursivas

Uma função recursiva é uma função que chama a ela mesma. Grande parte das definições em Haskell serão recursivas, principalmente as que necessitam de algum tipo de repetição. Uma definição recursiva clássica é a do fatorial de um número inteiro positivo: O fatorial de um número inteiro positivo pode ser dividido em dois casos:

• O fatorial de 0 será sempre 1;

• E o fatorial de um número n>0, será 1 * 2 *...* (n-1) * n

Então:

fatorial 0 = 1(regra 1)
fatorial n = n * fatorial (n-1)(regra 2)

fatorial :: Int -> Int

Exemplo de avaliação:

= 3 * (fatorial 2)(2)
= 3 * 2 * (fatorial 1)(2)
= 3 * 2 * 1 * (fatorial 0)(2)
= 3 * 2 * 1 * 1(1)

fatorial 3 = 6 Multiplicação

André Rauber Du Bois

Introduz-se agora um exemplo mais prático de definição recursiva. Seja a função aluno :: Int -> Float, que possui como argumento o número da chamada de um aluno (que pode variar de 1 até n), e fornece a nota do aluno na última prova como resultado.

Como se calcularia a média de notas da turma?

Para se resolver este problema, o ideal é dividi-lo em partes menores. Poderíamos primeiro pensar em uma função soma :: Int -> Float, que soma a nota de todos os alunos. Esta função teria dois casos:

• soma 1 seria a nota do aluno 1, ou simplesmente (aluno 1);

aluno 1 + aluno 2 ++ aluno (n-1) + aluno n

• soma n seria Tem-se então:

soma :: Int -> Float soma 1 = aluno 1 soma n = aluno n + soma (n-1)

Definida a função soma, pode-se definir a função média de maneira simples:

media :: Int -> Float media n = (soma n) / (fromInt n)

Na segunda linha da definição tem-se que usar a função fromInt para transformar o valor n que tem tipo Int, em Float, pois o tipo do operador de divisão é (/) :: Float -> Float -> Float.

André Rauber Du Bois

1.8 Exemplos

Nesta parte do texto analisa-se um exemplo mais extenso, usando as funções aluno e media explicadas anteriormente. O objetivo é criar uma função que gere uma tabela mostrando o número de todos os alunos e suas respectivas notas. No final da tabela deve aparecer a média das notas. Exemplo:

Haskell > tabela 4

Média da Turma: 8.2

Pode–se resolver o problema utilizando uma abordagem top-down. A tabela pode ser pensada como sendo uma grande string. Então tabela :: Int -> String

A função tabela tem como argumento um número inteiro (número de alunos), e devolve uma string (a tabela). A definição dessa função seria:

tabela n = cabeçalho ++ imprimeAlunos n ++ imprimeMedia n A função cabeçalho tem uma definição direta:

cabeçalho :: String cabeçalho = “Aluno Nota\n”

André Rauber Du Bois

Para se imprimir as notas, deve–se imprimir um aluno por linha. Isto pode ser definido recursivamente utilizando uma outra função imprimeAluno :: Int -> String Dessa maneira teremos:

imprimeAlunos :: Int -> String imprimeAlunos 1 = imprimeAluno 1 imprimeAlunos n = imprimeAlunos (n-1) ++ imprimeAluno n

Para a definição das funções imprimeAluno e imprimeMedia é necessário o uso da função pré-definida show, que transforma um número de qualquer tipo em string:

imprimeAluno :: Int -> String imprimeAluno n = show n ++ “ “ ++ show (aluno n) ++ “\n” imprimeMedia :: Int -> String imprimeMedia n = “\n” ++ “Média da Turma: “ ++ show (media n)

Foram usadas as funções aluno e media definidas anteriormente. Agora apresenta-se o script completo para a função tabela:

-- script tabela

-- banco de dados das notas: aluno :: Int -> Float

André Rauber Du Bois

A ordem em que as definições aparecem em um script não é importante. É importante ressaltar que os nomes das funções sempre começam com letras minúsculas, e os tipos com letras maiúsculas.

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)

André Rauber Du Bois

CAPÍTULO 2 – Listas em Haskell 2.1 Listas

Em Haskell pode-se trabalhar com listas de vários tipos diferentes. Para qualquer tipo t, pode-se criar uma lista com elementos do tipo t, que será do tipo [t]. Exemplo:

[False, True, True] :: [Bool]

Pode-se trabalhar também com listas de listas, listas de tuplas e listas de funções (desde que as funções tenham o mesmo tipo):

Um outro caso são as listas vazias, [], que não possuem elementos e podem ser de qualquer tipo:

A ordem e o número de ocorrência dos elementos é significante. Uma lista [3,4] é diferente de uma lista [4,3], e uma lista [1] é diferente de uma lista [1,1]. Existem outras maneiras de descrever listas:

• [ab] é a lista [a, a+1, ..., b]. Ex:

André Rauber Du Bois

Haskell > [42]
• [a, bc] é a lista de elementos de a até c passo b – a. Ex:
Haskell > [2,410]
Haskell > [1,310]

O último elemento da lista é o maior da seqüência e deve ser menor ou igual a c.

2.2 Operadores

O operador (:) é o operador de construção de listas. Toda a lista é construída através deste operador, de elementos e de uma lista.

Este operador serve para todo o tipo de listas:

André Rauber Du Bois

O que se observa é que este operador trabalha com um elemento e uma lista que devem ser do mesmo tipo. Na verdade este é um operador polimórfico e seu tipo é:

Onde t é uma variável de tipo que pode ser substituída por qualquer tipo (Int, Char, etc...). O conceito de polimorfismo será esclarecido em maior profundidade no decorrer do texto. Outro operador para listas é o de concatenação (++):

Apenas listas de mesmo tipo podem ser concatenadas, por isso:

Aqui se usa a letra t como variável de tipo. Porém pode-se usar qualquer letra minúscula.

2.3 Funções sobre Listas

Na maioria das definições sobre listas irá se usar a recursão para se percorrer todos os elementos. Uma função simples seria a função para somar todos os elementos de uma lista de números inteiros:

somaLista :: [Int] -> Int

Para esta função existem dois casos: • Caso Básico: Somar os elementos de uma lista vazia [] que irá resultar em 0, e

André Rauber Du Bois

• Passo Indutivo: Somar os elementos de uma lista não vazia. Em uma lista não vazia existe sempre o elemento head (o primeiro elemento), e o tail da lista, que é a lista que sobra sem o elemento head. Por exemplo, a lista [1, 2, 3] tem head 1 e tail [2,3]. Uma lista com head a e tail x é escrita (a:x). Então a soma dos elementos de uma lista não vazia (a:x) é dada somando a à soma dos elementos de x.

somaLista [] = 0(1)
somaLista (a:x) = a + somaLista x(2)

A definição da função seria: Ex:

O comando é avaliado da seguinte maneira:

= 1 + somaLista [2, 3, 4, 5](2)
= 1 + ( 2 + somaLista [3, 4, 5])(2)
= 1 + (2 + ( 3 + somaLista [4, 5]))(2)
= 1 + (2 + ( 3 + ( 4 + somaLista [5])))(2)
= 1 + (2 + ( 3 + ( 4 + ( 5 + somaLista []))))(2)
= 1 + (2 + ( 3 + ( 4 + ( 5 + 0))))(1)
= 15(+)

Uma função que teria uma definição muito parecida com a definição de somaLista, seria a função para determinar a lista cujos elementos são o dobro dos elementos de uma lista:

André Rauber Du Bois dobraLista :: [Int] -> [Int] dobraLista [] = [] dobraLista (a:x) = 2*a : dobraLista x

(Parte 1 de 3)

Comentários