Baixe Programação Funcional em Haskell e outras Notas de estudo em PDF para Informática, somente na Docsity! André Rauber Du Bois Programação Funcional com a Linguagem Haskell André Rauber Du Bois dubois@macs.hw.ac.uk André Rauber Du Bois 2 Índice CAPÍTULO 1 – Programação em Haskell__________________________________ 4 1.1 Expressões e Funções_________________________________________________ 4 1.2. Inteiros____________________________________________________________ 6 1.3 Booleanos _________________________________________________________ 8 1.4 Caracteres e Strings __________________________________________________ 9 1.5 Números em Ponto Flutuante __________________________________________ 11 1.6 Tuplas ____________________________________________________________ 12 1.7 Funções Recursivas _________________________________________________ 13 1.8 Exemplos _________________________________________________________ 15 CAPÍTULO 2 – Listas em Haskell _______________________________________ 18 2.1 Listas_____________________________________________________________ 18 2.2 Operadores ________________________________________________________ 19 2.3 Funções sobre Listas_________________________________________________ 20 2.4 List Comprehensions ________________________________________________ 24 2.5 Definições_________________________________________________________ 26 2.6 Outras Funções Úteis sobre Listas ______________________________________ 30 2.7 Listas Infinitas _____________________________________________________ 33 2.8 Erros _____________________________________________________________ 35 CAPÍTULO 3 – Conceitos Avançados ____________________________________ 37 3.1 Currying __________________________________________________________ 37 3.2 Composição de Funções______________________________________________ 39 3.3 Expressões Lambda _________________________________________________ 41 CAPÍTULO 4 – Classes de Tipo _________________________________________ 43 4.1 Classes de Tipo_____________________________________________________ 43 4.2 Classes Derivadas___________________________________________________ 45 4.3 Contexto __________________________________________________________ 46 4.4 Algumas Classes Importantes__________________________________________ 47 4.4.1 Enum ___________________________________________________________ 47 4.4.2 Read e Show _____________________________________________________ 48 4.4.3 Classes de Números________________________________________________ 48 André Rauber Du Bois 5 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 6 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 7 +, * Soma e multiplicação de inteiros ^ Potência: 2^4 é 16 - 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 Qualquer operador pode ser usado como função, e qualquer função pode ser usada como um operador, basta incluir o operador entre parênteses (), e a função entre crases ``. Ex: Haskell> (+) 2 3 5 Haskell> 10 `mod` 3 1 O programador pode definir os seus próprios operadores em scripts: Ex: Haskell> 10 &&& 3 3 -- script do meu primeiro operador (&&&) :: Int -> Int -> Int a &&& b | a < b = a | otherwise = b André Rauber Du Bois 10 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: Haskell > ‘\65’ ‘A’ 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 11 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: Haskell> “Haskell” == [‘H’, ‘a’, ‘s’, ‘k’, ‘e’, ‘l’, ‘l’] True 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; 231.6e-2 que significa 231.61 × 10-2, ou simplesmente 2.3161. O tipo Float além de aceitar os operadores (+, - , *, ^, = =, /=, <=,>=, <, >) vistos anteriormente, possui algumas funções próprias: André Rauber Du Bois 12 / 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 15 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 Aluno Nota 1 7.5 2 10 3 9 4 6.3 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 16 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 aluno 1 = 7.5 aluno 2 = 10 aluno 3 = 9 aluno 4 = 6.3 -- (...) André Rauber Du Bois 17 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 20 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 é: (:) :: t -> [t] -> [t] 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 (++): Haskell> [1, 2] ++ [3, 4] ++ [5, 6] [1, 2, 3, 4, 5, 6] Apenas listas de mesmo tipo podem ser concatenadas, por isso: (++) :: [t] -> [t] -> [t] 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 21 • 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. A definição da função seria: somaLista [] = 0 (1) somaLista (a:x) = a + somaLista x (2) Ex: Haskell> somaLista [1, 2, 3 ,4 ,5] 15 O comando é avaliado da seguinte maneira: somaLista [1, 2, 3, 4, 5] = 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 22 dobraLista :: [Int] -> [Int] dobraLista [] = [] dobraLista (a:x) = 2*a : dobraLista x Quais são os dois casos desta função? O caso básico é determinar a lista cujos elementos são o dobro dos elementos de uma lista vazia. A resposta seria []. O passo indutivo consiste em considerar uma lista não vazia. Como se faz isso? Calcula-se o dobro do head e coloca-se este elemento como o primeiro da lista cujos elementos são o dobro dos elementos do tail. Ex: Haskell > dobraLista [1, 2, 3] [2, 4, 6] As funções apresentadas até o momento trabalham apenas com listas de um tipo específico. Porém existem funções polimórficas que trabalham com listas de qualquer tipo. Um exemplo seria a função length, pré-definida da linguagem, que dá o número de elementos de uma lista: length :: [t] -> Int length [] = 0 length (a:x) = 1 + length x A lista vazia tem tamanho 0. A lista não vazia, possui sempre um elemento a mais que o seu tail. Esta definição serve para qualquer tipo de listas, tanto para números quanto para caracteres, etc, por isso usa-se a variável de tipo t na declaração da função. André Rauber Du Bois 25 No exemplo a função even devolve o valor booleano True se o seu argumento for um número par. Então esta list comprehention devolve apenas os valores pares da lista list. Nos geradores pode-se trabalhar com qualquer tipo de pattern. Ex: somaPares :: [(Int, Int)] -> [Int] somaPares lista = [ a+b | (a,b) <- lista] Ex: Haskell > somaPares [(2,3), (3,7), (4,5)] [5, 10, 9] Quando se trabalha com mais de um gerador, o primeiro valor da primeira lista é gerado e mantido enquanto se avalia os valores da lista seguinte, Ex: pares :: [t] -> [u] -> [(t,u)] pares n m = [(a,b) | a <- n , b <-m] Então: Haskell > pares [1,2,3] [4,5] [(1,4), (1,5), (2,4), (2,5), (3,4), (3,5)] Por exemplo, utilizando list Comprehensions e um predicado, pode-se criar um filtro para strings: remove :: Char -> [Char] -> [Char] remove carac str = [c | c <-str , c/= carac] André Rauber Du Bois 26 Exemplo: Haskell > remove ‘ ‘ “Este exemplo remove os espaços em branco!” “Esteexemploremoveosespaçosembranco!” Um exemplo mais prático: Tendo uma lista de tuplas, em que cada tupla tem-se o número do aluno, o nome do aluno e sua nota: baseDeDados :: [(Int, String, Float)] baseDeDados = [ (1, “André”, 10.0), (2, “Carlos”, 6.8), (3,”Maurício”, 7.0)] Pode-se transformar esta lista em uma lista de nomes de alunos: nomes :: [(Int, String, Float)] -> [String] nomes list = [pegaNome a | a <-list] where pegaNome (a,b,c) = b Na função nomes, foi usada a função pegaNome, que foi definida localmente através da palavra reservada where. Esta definição não serve para nenhuma outra função no script. Ela só funciona na função nomes. A função nomes poderia ter sido definida de uma maneira mais simples: nomes list = [b | (a,b,c) <-list] 2.5 Definições A maioria das definições sobre listas se encaixam em três casos: folding, que é a colocação de um operador entre os elementos de uma lista, filtering, que significa filtrar André Rauber Du Bois 27 alguns elementos e mapping que é a aplicação de funções a todos os elementos da lista. Os outros casos são combinações destes três, ou recursões primitivas. Existem funções pré-definidas em Haskell que servem para resolver estes casos. São as funções foldr1, map, e filter. Estas funções são todas polimórficas, ou seja, servem para listas de qualquer tipo e são high order functions. As high order functions são funções que recebem outras funções como argumento. • foldr1 Esta função coloca um operador entre os elementos de uma lista: foldr1 (⊕) [ x1, x2, ..., xn] = x1 ⊕ x2 ⊕ ... ⊕ xn A definição em Haskell é: foldr1 :: (t -> t -> t) -> [t] -> t foldr1 f [a] = a foldr1 f (a:b:x) = f a (foldr1 f (b:x)) A função tem como argumento um operador (ou melhor, uma função com dois argumentos), e uma lista. Ex: Haskell > foldr1 (&&) [True, False, True] False Haskell > foldr1 (++) [“Concatenar “,“uma “,“lista “,“de ”,“strings “,“em “,“uma “,“só.”] “Concatenar uma lista de strings em uma só.” Haskell > foldr1 (+) [1,2,3] 6 André Rauber Du Bois 30 Utilizando a baseDeDados definida anteriormente pode-se fazer uma função que de os nomes dos alunos com nota maior que 7. alunos :: [(Int, String, Float)] -> [String] alunos base = map pegaNome (filter nota base) where nota (a,b,c) = c>7 pegaNome (a,b,c) = b Então: Haskell > alunos baseDeDados [“André”] 2.6 Outras Funções Úteis sobre Listas Muitas funções de manipulação de listas necessitam tomar, ou retirar, alguns elementos de uma lista a partir do início. Para isto, a linguagem Haskell possui as seguintes funções: take :: Int -> [t] -> [t] drop :: Int -> [t] -> [t] A função take n gera uma lista com os n primeiros elementos da lista parâmetro: take _ [] = [] take 0 _ = [] take n (a:x) = a : take (n-1) x André Rauber Du Bois 31 Então: Haskell > take 3 [1, 2, 3, 4, 5, 6] [1, 2, 3] Haskell > take 0 [2, 4, 6, 8, 10] [] A função drop n gera uma lista sem os n primeiros elementos da lista parâmetro, sua definição é parecida com a da função take: drop 0 list = list drop _ [] = [] drop n (a:x) = drop (n-1) x Exemplo: Haskell > drop 3 [2, 4, 6, 8, 10] [8, 10] Haskell > drop 10 [2, 4, 6, 8, 10] [] Outras funções interessantes, que seguem o mesmo princípio, são as funções takeWhile e dropWhile, que tem como parâmetro, ao invés de um número, uma função de tipo (t -> Bool). Haskell > takeWhile par [2,4,5,7, 2] [2, 4] Haskell > dropWhile par [2,4,5,7, 2] [5, 7, 2] Definição da função takeWhile: André Rauber Du Bois 32 takeWhile :: (t -> Bool) -> [t] -> [t] takeWhile p [] = [] takeWhile p (a:x) | p a = a: takeWhile p x | otherwise = [] A dropWhile é definida de maneira semelhante. Outra função muito utilizada é a função zip, que transforma duas listas em uma lista de tuplas. zip (a:x) (b:y) = (a,b) : zip x y zip _ _ = [] Haskell > zip [1, 3, 5] [2, 4, 6] [(1,2), (3, 4), (5, 6)] Haskell > zip [1, 3, 5, 7, 9, 11] [2, 4, 6] [(1,2), (3, 4), (5, 6)] A lista gerada pela função zip sempre terá o mesmo número de elementos da menor lista passada como argumento. Existe uma função pré-definida da linguagem derivada da função zip, é a função zipWith: ZipWith :: (a -> b -> c) -> [a] -> [b] -> [c] Ela funciona da seguinte maneira: ZipWith op [x1, x2, x3, ...] [y1, y2, y3, ...] = [op x1 y1, op x2, y2, op x3 y3, ...] André Rauber Du Bois 35 valorEmUmaIteração func inic valor = take valor (iterate func ini) Então: Haskell > valorEmUmaIteração (*2) 1 3 [1, 2, 4] Existem outras maneiras de se descrever listas infinitas: [3 .. ] = [3, 4, 5, 6 ... [2, 4 .. ] = [2, 4, 6, 8 ... Pode–se definir então uma função que ache todas as potências de um número inteiro: pot :: Int -> [Int] pot n = [ n^y | y <- [0 ..] ] Tem–se então Haskell > pot 2 [ 1, 2, 4, 8 ^C {Interrupted} 2.8 Erros Se for passado para a função take um valor negativo, ela ira devolver uma mensagem de erro: André Rauber Du Bois 36 Haskell > take (-1) [1,2] Program error: negative argument. Existe uma função em Haskell chamada error :: String -> a que pára a avaliação de uma expressão caso ocorra um valor não desejado (⊥). A definição final da função take seria: take :: Int -> [a] -> [a] take 0 _ = [] take _ [] = [] take n (x:xs) | n>0 = x : take (n-1) xs take _ _ = error "negative argument" André Rauber Du Bois 37 CAPÍTULO 3 – Conceitos Avançados 3.1 Currying Em Haskell uma função de dois ou mais argumentos, pode aceitá-los um de cada vez. Isto se chama currying. Por exemplo: soma :: Int -> Int -> Int soma x y = x + y Esta função pega dois números inteiros como argumento e os soma: Haskell > soma 2 8 10 Se aplicarmos a função soma a apenas um argumento (soma 1), teremos uma função que aplicada a um argumento b, incrementa este valor (1+b). Pode-se definir então uma função incrementa da seguinte maneira: incrementa :: Int -> Int incrementa = soma 1 Ex: Haskell > incremeta 4 5 André Rauber Du Bois 40 removePontuacao :: String -> String removePontuacao str = remove ‘!’ (remove ‘.’ ( remove ‘,’ str) ) ) Então: Haskell > removePontuacao “Haskell. É muito bom, para manipular strings !!!” “Haskell É muito bom para manipular strings ” Existe um operador de composição de funções em Haskell (.), que ajuda a evitar o uso de vários parênteses nas definições. A definição de removePontuacao ficaria da seguinte maneira: removePontuacao = remove ‘!’ . remove ‘.’ . remove ‘,’ O operador de composição funciona como esta equação: f (g x) = (f . g) x e seu tipo é (.) :: (u -> v) -> (t -> u) -> (t -> v) Um exemplo interessante é a definição de iteracao, que tem como parâmetro uma função e o número de vezes que esta deve ser composta com ela mesma: iteracao :: (a->a) -> Int -> (a->a) iteracao f 1 = f iteracao f n = iteracao f (n-1) . f André Rauber Du Bois 41 Tem –se : Haskell> iteracao (+1) 5 1 6 3.3 Expressões Lambda 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 λx. 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: André Rauber Du Bois 42 (.) :: (u -> v) -> (t -> u) -> (t -> v) f . g = \x -> f (g x) André Rauber Du Bois 45 Com a função iguala é possível instanciar o tipo Endereco na classe Eq da seguinte maneira: instance Eq Endereco where (==) = iguala Depois de feita a instanciação é possível usar o operador (==) diretamente em valores do tipo Endereco: Haskell > (Rua "Abobora" (Apto 13 403)) == (Rua "Abobora" (Apto 13 403)) True Também pode-se usar o operador (/=), pois na classe ele é definido como: x /= y = not (x==y) Então: Haskell > (Rua "Azul" (Apto 1 403)) /= (Rua "Marrom" (Casa 10)) True 4.2 Classes Derivadas Uma classe pode ser derivada de outra. Dessa maneira além de ter as suas operações próprias, possui também as operações da super-classe. Um exemplo de classe derivada é a classe Ord. Ela é definida de uma maneira similar: class (Eq a) => Ord a where (<), (<=), (>=), (>) :: a -> a -> Bool max, min :: a -> a -> a André Rauber Du Bois 46 Para um tipo pertencer a esta classe, ele também tem que pertencer a classe Eq. Pode-se dizer também que a classe Ord herda as operações da classe Eq, o que tornaria a idéia mais parecida com a da orientação a objetos. Haskell também permite heranças múltiplas, pois uma classe pode ter mais de uma super-classe: Class (Eq t, Show t) => Minhaclasse t where ... 4.3 Contexto Considere a definição da função elem, que devolve um valor booleano dizendo se um elemento pertence a uma lista: elem x [] = False elem x (y:ys) = x == y || (elem x ys) Como foi visto até agora, o tipo desta função poderia ser polimórfico: elem :: a -> [a] -> Bool Mas analisando-se a definição da função, nota-se que ela só funciona se o tipo a puder ser igualado com o operador (==), pois toda a definição se baseia neste operador. Como o tipo a tem que estar instanciado na classe Eq, uma melhor definição de tipo para a função elem seria: elem :: (Eq a) => a -> [a] -> Bool Esta definição pode ser lida como “Para cada tipo a que pertencer a classe Eq, a função elem tem tipo a -> [a] -> Bool. André Rauber Du Bois 47 A expressão Eq a é chamada de contexto da função e não faz parte da expressão de tipo. O contexto de uma função pode ser omitido, porém é uma boa prática de programação utiliza-lo, pois facilita a compreensão da função. 4.4 Algumas Classes Importantes Além das classes Ord e Eq citadas anteriormente existem várias outras classes pré- definidas em Haskell. Aqui serão mostradas algumas das mais importantes: 4.4.1 Enum É a classe dos tipos que podem ser enumerados, podendo então gerar listas como Haskell > [2,4, .. 8] [2, 4, 6, 8] A lista [2,4, ..8] é descrita na função enumFromThenTo 2 4 8. Pode-se gerar listas desta maneira em qualquer tipo instanciado na classe Enum, como por exemplo Char, ou qualquer outro Tipo Algébrico definido pelo programador. As principais funções da classe Enum são: class (Ord a) => Enum a where enumFrom :: a -> [a] -- [n..] enumFromThen :: a -> a -> [a] -- [n,m..] enumFromTo :: a -> a -> [a] -- [n..m] enumFromThenTo :: a -> a -> a -> [a] -- [n,n'..m] André Rauber Du Bois 50 CAPÍTULO 5 – Tipos Algébricos 5.1 Tipos Algébricos Até agora foram apresentados vários tipos intrínsecos da linguagem, como valores booleanos, caracteres e números. Porém existem certos problemas computacionais que são mais difíceis de serem modelados com estes valores, como por exemplo os meses. Pode-se definir um tipo Meses da seguinte maneira: data Meses = Jan | Fev | Mar | Abr | Mai | Jun | Jul | Ago | Set | Out | Nov | Dez Este tipo é um enumerated type. Ele é formado por doze valores que são chamados de construtores (constructors) de tipo. Uma definição de tipo começa sempre com a palavra data, depois vem o nome do tipo (Meses), que deve começar com letra maiúscula (note que todos os tipos em Haskell começam com letra maiúscula), e seus construtores (que também começam com letra maiúscula). Os construtores são todos os valores que um tipo pode assumir. Um exemplo de tipo algébrico já conhecido é o tipo Bool: data Bool = True | False Pode-se criar um tipo que possua vários componentes: type Nome = String type Idade = Int data Pessoas = Pessoa Nome Idade As funções que manipulam os tipos algébricos podem ser definidas por pattern matching: André Rauber Du Bois 51 mostraPessoa :: Pessoas -> String mostraPessoa (Pessoa nom idade) = “Nome: “ ++ nom ++ “ Idade: “ ++ show idade Exemplo: Haskell > mostraPessoa (Pessoa “Éderson Araújo” 22) Nome: Éderson Araújo Idade: 22 Um tipo pode trabalhar com valores bem diferentes. Supondo que se queira trabalhar com figuras geométricas. O tipo pode assumir o valor de um círculo ou de um retângulo. Então: data Forma = Circulo Float | Retangulo Float Float O valor para o círculo poderia ser o raio, e para o retângulo poderia ser base e altura. Para se definir uma função que calcula a área de um objeto do tipo Forma pode-se trabalhar novamente com pattern matching: area :: Forma -> Float area (Circulo r) = pi * r * r area (Retangulo b a) = b * a Outro exemplo do mesmo princípio seria para se trabalhar com endereços. Algumas ruas tem nomes e outras são representadas por números. Ex: data Rua = Numero Int Residencia | Nome String Residencia André Rauber Du Bois 52 data Residencia = Casa Int | Apartamento Int Int Agora pode-se definir operações que formatam o endereço usando pattern matching em cima dos construtores. Quando um tipo é definido, algumas classes podem se instanciadas diretamente através da palavra reservada deriving: data Meses = Jan | Fev | Mar | Abr | Mai | Jun | Jul | Ago | Set | Out | Nov | Dez deriving (Eq, Show, Enum) Desta maneira, pode-se fazer coisas do tipo: Haskell > Jan Jan Haskell > Mar == Mar True Haskell > [Jan .. Set] [Jan,Fev,Mar,Abr,Mai,Jun,Jul,Ago,Set] 5.2 Tipos Recursivos Os tipos algébricos podem ser também recursivos. Um exemplo típico é o de construção de árvores: data Arvore = Null | Node Int Arvore Arvore André Rauber Du Bois 55 5.3 Tipos Algébricos Polimórficos Os tipos Algébricos podem ser tipos com definições polimórficas. Um exemplo simples, mas ilustrativo, seria a definição de um tipo Pares. Um par poderia ser tanto dois números, quanto dois caracteres ou dois valores booleanos. Temos: data Pares u = Par u u Um par seria par1 :: Pares Int par1 = Par 22 ou de qualquer outro tipo: Par [1,2] [2,3,4] :: Pares [Int] Par False True :: Pares Bool (...) A definição anterior dada para árvores trabalhava com números inteiros nos nodes. Pode-se modificar a definição para que a árvore contenha qualquer tipo de valor nos nodes. Então o tipo árvore seria: data Arvore t = Null | Node t (Arvore t) (Arvore t) As definições de procuraValor e ocorrencia, precisariam ser modificadas apenas na tipagem: André Rauber Du Bois 56 procuraValor :: Arvore t -> Int ->Bool ocorrencia :: Arvore t -> Int -> Int Já a função somaArvore só funciona para árvores de números inteiros. Por isso o tipo passa a ser: somaArvore :: Arvore Int -> Int André Rauber Du Bois 57 CAPÍTULO 6 – Abstract Data Types 6.1 Abstract Data Type (ADT) Supondo que se queira modelar uma base de dados para uma loja de bebidas. Poderia-se ter a seguinte definição. type Codigo = Int type Produto = String type Preco = Float type Base = [(Codigo, Produto, Preco)] base1 :: Base base1 = [ (1, “Guarana”, 0.70), (2, “Cerveja Bacana lata”, 0.50), (3, “Uísque Do Bom”, 22.0) ......] Teria-se então algumas definições em cima desta base. insereProduto :: Base -> (Codigo, Produto, Preco) -> Base retiraProduto :: Base -> Codigo -> Base preco :: Base -> Codigo -> Preco Se a base estiver ordenada pelo código do produto, fica muito mais fácil de se implementar as funções, pois todas fazem algum tipo de procura em cima da base. O único André Rauber Du Bois 60 uniao [] a = a uniao a [] = a uniao (a:x) (b:y) | a<b = a : uniao x (b:y) | a == b = a : uniao x y | otherwise = b : uniao (a:x) y inter [] a = [] inter a [] = [] inter (a:x) (b:y) | a<b = inter x (b:y) | a == b = a : inter x y | otherwise = inter (a:x) y dif [] a = [] dif a [] = a dif (a:x) (b:y) | a == b = dif x y | a < b = a : dif x (b:y) | otherwise = dif (a:x) y A subConj (devolve um valor booleano dizendo se um conjunto é ou não sub- conjunto de outro) é definida como as outras por pattern matching tendo três casos: • Um conjunto vazio é sub-conjunto de outro • Um conjunto não-vazio não é sub-conjunto de um conjunto vazio • O terceiro caso é quando nenhum dos conjuntos passados como parâmetro são vazios. Então são feitas chamadas recursivas da função aproveitando o fato dos elementos estarem em ordem. André Rauber Du Bois 61 subConj [] a = True subConj x [] = False subConj (a:x) (b:y) | a<b = False | a == b = subConj x y | a>b = subConj (a:x) y A função constConj transforma uma lista em um conjunto. Para isso se utiliza a função sort para ordenação dos elementos (função explicada anteriormente), e uma função eliminaRep, que retira os elementos repetidos da lista: constConj = eliminaRep . sort sort :: Ord t => [t] -> [t] sort [] = [] sort (a:x) = ins a (sort x) ins :: Ord t => t -> [t] -> [t] ins a [] = [a] ins a (b:y) | a <= b = a : (b:y) | otherwise = b : ins a y André Rauber Du Bois 62 eliminaRep :: (Ord t) => [t] -> [t] eliminaRep [] = [] eliminaRep [a] = [a] eliminaRep (a:b:x) | a == b = eliminaRep (b:x) | otherwise = a : eliminaRep (b:x) Exemplos: Haskell > constConj [5, 7, 4, 3, 89, 23, 2, 3, 3, 7, 4] [2, 3, 4, 5, 7, 23, 89] Haskell > uniao (constConj [4, 3, 1, 22, 4]) (constConj [4, 34, 1, 3]) [1, 3, 4, 22, 34] Haskell > inter (uniao (constConj [1,2,3]) (constConj [2,3,4,5])) (constConj [3,4,5]) [3, 4, 5] Algumas definições são feitas simplesmente igualando-se uma função a outra: conjIgual = (==) leqConj = (<=) filterConj = filter André Rauber Du Bois 65 conjInter :: Ord t => Conjunto (Conjunto t) -> Conjunto t vazio = [] unitario a = [a] membroConj [] a = False membroConj (a:x) b | a<b = membroConj x b | a == b = True | otherwise = False uniao [] a = a uniao a [] = a uniao (a:x) (b:y) | a<b = a : uniao x (b:y) | a == b = a : uniao x y | otherwise = b : uniao (a:x) y inter [] a = [] inter a [] = [] inter (a:x) (b:y) | a<b = inter x (b:y) | a == b = a : inter x y | otherwise = inter (a:x) y dif [] a = [] dif a [] = a dif (a:x) (b:y) | a == b = dif x y | a < b = a : dif x (b:y) | otherwise = dif (a:x) y André Rauber Du Bois 66 conjIgual = (==) subConj [] a = True subConj x [] = False subConj (a:x) (b:y) | a<b = False | a == b = subConj x y | a>b = subConj (a:x) y leqConj = (<=) constConj = eliminaRep . sort sort :: Ord t => [t] -> [t] sort [] = [] sort (a:x) = ins a (sort x) ins :: Ord t => t -> [t] -> [t] ins a [] = [a] ins a (b:y) | a <= b = a : (b:y) | otherwise = b : ins a y eliminaRep :: (Ord t) => [t] -> [t] eliminaRep [] = [] eliminaRep [a] = [a] eliminaRep (a:b:x) | a == b = eliminaRep (b:x) | otherwise = a : eliminaRep (b:x) André Rauber Du Bois 67 mostra = showList instance Eq t => Eq (Conjunto t) where (==) = conjIgual instance Ord t => Ord (Conjunto t) where (<=) = leqConj instance Show t => Show (Conjunto t) where showsPrec p = mostra mapConj f l = eliminaRep (map f l) filterConj = filter foldConj = foldr card = length conjUniao = foldConj uniao [] conjInter = foldConj inter [] André Rauber Du Bois 70 pois ela não devolve nenhum valor, simplesmente realiza uma série de ações de entrada e saída. 7.2 Arquivos Existem duas funções principais para se trabalhar com o sistema de arquivos: writeFile :: String -> String -> IO () readFile :: String -> IO String O funcionamento delas, pode ser facilmente demonstrado através de exemplos. Primeiro uma função para criar um arquivo contendo uma string digitada pelo usuário: main = do putStr ("Escreva uma linha e tecle ENTER: ") linha <- getLine nome <- criaArq linha putStr ("A linha \n" ++ linha ++ "\nesta no arquivo " ++ nome ++ "!") criaArq :: String -> IO String criaArq linha = do putStr ("Nome do Arquivo a ser criado: ") nome <- getLine writeFile nome linha return (nome) André Rauber Du Bois 71 A função principal pega uma linha e a usa como parâmetro para a função criaArq. Esta solicita o nome do arquivo a ser criado e o cria com a função writeFile, então devolve o nome do arquivo com a função return :: a -> IO a. A interação com o usuário ocorre da seguinte maneira: Haskell > main Escreva uma linha e tecle ENTER: Trabalhando com Arquivos Nome do Arquivo a ser criado: Haskell.txt A linha Trabalhando com Arquivos esta no arquivo Haskell.txt! Haskell > Pode-se fazer uma função que crie o arquivo Haskell2.txt com o conteúdo de Haskell.txt mais uma linha digitada pelo usuário: adiciona = do putStr ("Escreva uma linha para adicionar ao arquivo Haskell2.txt:\n") linha <- getLine arquivo <- readFile "Haskell.txt" writeFile "Haskell2.txt" (arquivo ++ "\n" ++ linha) putStr ("Linha adicionada!") A função readFile associa Haskell.txt a variável arquivo, isso é feito by-need, ou seja o conteúdo só é lido quando necessário, seguindo a estratégia da lazy evaluation. André Rauber Du Bois 72 7.3 Interações Infinitas Usando a recursão pode se trabalhar com entrada de dados ilimitada. Para ilustrar este conceito, segue um exemplo de função que lê vários nomes e os exibe em ordem alfabética: main = do nomes <- leNomes putStr (unlines (sort nomes)) leNomes = do putStr ("Escreva um nome: ") nome <- getLine if nome == "" then return [] else do nomes <- leNomes return ([nome] ++ nomes) sort [] = [] sort (a:b) = sort [x | x <- b, x<a] ++ [a] ++ sort [x | x <- b, x>= a] A função leNomes é chamada recursivamente até que receba uma string vazia. O controle é feito através da função (if then else), que funciona como em outras linguagens de programação. leNomes devolve uma lista de strings, onde cada elemento é um nome que foi digitado pelo usuário. Esta lista é ordenada na função principal pelo sort que utiliza um algoritmo diferente da função ordenacao vista anteriormente. O resultado é exibido depois de passar pela função André Rauber Du Bois 75 Exemplos: Haskell > push 1 pilhaVazia Stack [1] Haskell > pop (Stack [4,5,6]) 4 Esta implementação de pilha pode ser reutilizada por outros programas em Haskell. Para isso é necessário criar um módulo. O módulo Pilha seria construído da seguinte maneira: module Pilha ( Pilha (Stack), pilhaVazia, push, pop) where (...) Para se criar um módulo, utiliza-se a palavra reservada module, e em seguida o nome do módulo. Após o nome, lista-se todas as funções que se quer utilizar em outros programas. Logo depois vem a palavra where e as implementações. Quando um outro programa precisar utilizar o módulo pilha, no início do script deve-se utilizar a palavra reservada import . import Pilha ( Pilha (Stack), pilhaVazia, push, pop) Depois de import deve-se listar as funções que se deseja utilizar do módulo. Se a lista for omitida todas as funções estarão disponíveis: import Pilha. André Rauber Du Bois 76 7.2 Criando Um ADT Para tornar o tipo pilha um ADT, basta não incluir na lista de funções públicas o construtor do tipo: module Pilha ( Pilha , pilhaVazia, push, pop) where (...) Então: Haskell > pop (Stack [1,2]) ERROR: Undefined constructor function "Stack" Pode-se então criar uma função que transforme uma lista em pilha, no módulo pilha: listaEmPilha:: [t] -> Pilha t listaEmPilha x = Stack x e inclui-la na lista de funções: module Pilha ( Pilha , pilhaVazia, push, pop, listaEmPilha) where então: Haskell > pop (listaEmPilha [1,2]) 1