Funcional

Programação Funcional Curso “Paradigmas e Ferramentas de Engenharia de Software”

Agradecimentos 

Prof. Graham Hutton (Univ. de Nottingham)  



Prof. Andrew Frank (TU – Wien)  



Parte do material dos slides Acesso à versão preliminar do livro “Programming in Haskell”

Motivação para uso de programação funcional Acesso ao código “lambdaGIS”

Dr. Grant Malcolm (University of Liverpool)  

Parte do material dos slides www.csc.liv.ac.uk/~grant/Teaching/COMP205/

O que é programação funcional? 

Estilo de programação baseado no uso de funções



Todas as expressões são baseadas em funções 



Funções podem ser argumentos de outras funções

Toda a programação é baseada na avaliação de expressões para gerar valores. 

Cada valor tem um tipo associado.

Linguagens Funcionais 

As operações básicas são definição de funções e a aplicação de funções.



Funções são entidades de 1a classe   



Podem ser passadas como parâmetro Retornadas como resultado Armazenadas em estruturas de dados.

Programas funcionais são diretos

Soma de 1 a 100 em C++ 

Operação baseada em atribuição de variáveis int total = 0; for (int i = 1; i <= 100; i++) total = total + i;





A mesma variável (total) muda de valor 100 vezes durante a operação (efeito colateral) Como programar sem efeitos colaterais?

Soma de 1 a 100 em Haskell 

Baseada na função sum e na idéia de lista implícita s1_100 :: Integer s1_100 = sum [1..100]



O método de programação é aplicação de funções

Soma de 1 a 100 em Haskell 

Consequências de abordagem funcional s1_100 = sum [1..100]



Uma vez estabelecido o valor de s1_100    

Tem um tipo definido (pode ser implícito) O valor não pode ser mudado O valor pode ser usado como argumento de funções Em termos de C++, é como se todos os valores fossem const

Um novo paradigma 

Será que dá para programar...



...sem “do loops”?



...sem efeitos colaterais?



...sem mudar o valor de variáveis?

Um Novo Paradigma: Todos os símbolos são constantes 



C++ if (myVar==37) myVar = 3; for (myVar=0; myVar<37; myVar++) Haskell  

Não há "variáveis" Há símbolos que podem ter um valor único

myVar = 37 myVar2 = modif (myVar) 

Semelhança com definições matemáticas

Um novo paradigma: I/O deve ser isolado 

I/O causa efeitos colaterais



Abordagem “pura” de programação funcional 



Uso do “mônadas”

Abordagem “impura” de programação funcional 

Uso de funções auxiliares (unsafePerformIO)

Expressões Em Haskell, construimos expressões a partir de: •

constantes

•

operadores

•

aplicação de funções

•

(parênteses)

Expressões Constantes: -3.459 True 'a' "hello" [1,2,4,9]

Aplicação de funções: even 47 twice (-2)

Operadores .

Composição de funções

*, /, ^

multip, divisão, potência

+,-

adição, subtração

:, ++

composição de listas, concatenação

==,/=,<=,...

igual, desigual, comparação

&&

E

||

OU

Definições Programador pode definir constantes e funções -- PI pi = 3.14159 -- area e circunferencia de circulo circumf r = 2 * pi * r area rad = pi * rad^2

Tipos em Haskell 

O que é um tipo? 



“A program variable can assume a range of values during the execution of a program. An upper bound of such a range is called a type of the variable” (Cardelli)

Tipo é uma restrição  Descreve os limites do resultado final de uma computação 

“The fundamental purpose of a type system is to prevent the occurrence of execution errors during the running of a program” (Cardelli).

Tipos Básicos

     

Bool Char Int Integer Float Double

Boleanos Caracteres Inteiros de 32-bits Inteiros de tam ilimitado Ponto flutuante Dupla precisão

Tipos em Haskell Toda expressão em Haskell deve ter um tipo associado Tipos podem ser explícitos ou inferidos sum :: Float -> Float -> Float sum x y = x + y sum2 :: Float -> Float sum2 y = sum 2 y circumf :: Float -> Float circumf r = 2 * pie * r area :: Double -> Double area r = pie * r ^ 2

Tuplas Haskell permite composição de tipos: (Integer,Integer) -- pares de inteiros (Integer,Char,Bool) -- etc.

Em geral, (A,B) representa um tipo cujo primeiro componente é do tipo A e o segundo é do tipo B.

Listas e Funções Simples em Haskell

Como é um Programa em Haskell? 

Conjunto de definições de funções

square :: Int -> Int -- assinatura square n = n*n -- computo double :: Int -> Int double n = 2*n dubSqr :: Int -> Int dubSqr n = square (double n)

Funções 

Uma função é um mapeamento de valores de um tipo em outro tipo not :: Bool → Bool isDigit :: Char → Bool add :: Int → Int → Int add x y = x + y

Aplicação de Funções em Haskell Matemática f (x) f (x,y) f (g(x)) f (x, g(y)) f (x) g(y) f(a,b) + c d 



f f f f f f

Haskell x xy (g x) x (g y) x*gy ab+c*d

Aplicação de funções tem máxima prioridade

Comportamento Situacional (“Pattern Matching”) Podemos especificar o comportamento de uma função descrevendo sua resposta a diferentes situações de entrada. Podemos ter múltiplas definições -- fatorial fat :: Integer -> Integer fat 0 = 1 fat n = fat (n-1) * n

Barras (“Guards”) 

Alternativas ao comportamento situacional



Barras são usadas para denotar alternativas na definição de funções



Uma barra é uma condição que pode ocorrer 



Define o resultado neste caso

Tudo que pode ser feito com “pattern matching” pode ser feito com barras

Barras (“Guards”) Uso de barras é alternativa ao comportamento situacional -- fatorial fat :: Integer -> Integer fat n | n < 0 = error “negativo” | n == 0 = 1 | otherwise = fat (n-1) * n

Listas em Haskell Uma lista é uma sequencia de valores ordenados Listas são homogêneas: todos os elementos da lista tem o mesmo tipo Listas são dinâmicas: não há restrição no tamanho de listas (incluindo listas infinitas)

Listas Três tipos de notação: •

construtores: 1 : 1 : 2 : 3 : 5 : 8 : []

•

“colchetes": [1, 1, 2, 3, 5, 8]

•

strings (apenas para listas de caracteres): ['h', 'e', 'l', 'l', 'o'] = "hello"

Funções em Listas 



Listas são o principal elemento de composição de objetos em Haskell Tem o mesmo papel de conjuntos em Matemática

zeroto :: Int -> [Int] zeroto n = [0..n] add1tofst :: [Int] -> [Int] add1tofst (x:xs) = (x+1:xs)

Funções em Listas Comprimento: Main> length [1, 1, 2, 3, 5, 8] 6 Main> length "" 0

Concatenação Main> [1, 1, 2, 3] ++ [5, 8] [1, 1, 2, 3, 5, 8] Main> [] ++ [1] ++ [2] [1,2]

Funções em Listas

Heads e tails Main> head [1, 2, 4] 1 Main> tail [1, 2, 4] [2,4] Main> head [] ERROR: ... Main> tail [1] []

Funções em Listas take 4 “aeroporto" “aero“ drop 2 ['i','n','t','e','n','t'] "tent" reverse 'p':'o':'o':'l':[] "loop" -- zip :: [a] -> [b] -> [(a,b)] zip [1,2,3,4,5] "cat" [(1,'c'),(2,'a'),(3,'t')]

Tipos Parametrizados 

Os tipos de uma função podem ser genéricos

-- zip :: [a] -> [b] -> [(a,b)] zip [1,2,3,4,5] "cat" [(1,'c'),(2,'a'),(3,'t')] -- length :: [a] -> Int length [1, 1, 2, 3, 5, 8] 6

Comportamento Situacional em Funções sobre Listas “Pattern matching” é muito útil em funções sobre listas (especialmente para definições recursivas) isempty :: [a] -> Bool isempty [] = True isempty anythingElse = False

head [] = error "head []" head (x:xs) = x

length [] = 0 length (x : xs) = 1 + length xs

Comportamento Situacional em Funções sobre Listas

Função zip – junta listas em tuplas: zip :: [a] -> [b] -> [(a,b)] zip [] ss = [] zip is [] = [] zip (i:is) (s:ss) = (i,s) : zip is ss

Mais “Pattern Matching”

Função unzip: desfaz o que “zip” faz unzip :: [(a,b)] -> ([a],[b]) unzip [] = [] unzip ((x,y) : ps) = (x:xs, y:ys) where (xs,ys) = unzip ps

Definições Recursivas

Um conceito básico em Haskell é o uso de recursã para definição de funções

length :: [a] -> Int length [] = 0 length (x : xs) = 1 + length xs

Recursão 



Sem loops explícitos, o fluxo em Haskell é usualmente expresso por recursão. Como garantir que recursão termine?  



Escolha uma “entidade” para focar o processo Garanta que a próxima chamada estará mais próxima de uma condição de término

Idéia:  

Decremente um valor para cada chamada Tome um valor de uma lista a cada chamada

Recursão Soma de todos os números de uma lista sumAll :: [Integer] -> Integer

A soma dos números de uma lista vazia sumAll [] = 0

Soma dos números de uma lista x : xs sumAll (x : xs) = x + sumAll xs

Recursão Concatenação de listas de caracteres concat :: [[Char]] -> [Char]

Concatenar uma lista vazia: concat [] = []

--- = “”

Concatenar uma lista a partir de um elemento: concat (s : ss) = s ++ concat ss

Avaliação de Funções Recursivas length [] = 0 length (x : xs) = 1 + length xs length (1 : 2 : 4 : []) ⇒

Avaliação de Funções Recursivas length [] = 0 length (x : xs) = 1 + length xs length (1 : 2 : 4 : []) ⇒ { x ← 1 , xs ← 2 : 4 : [] }

Avaliação de Funções Recursivas length [] = 0 length (x : xs) = 1 + length xs length (1 : 2 : 4 : []) ⇒ { x ← 1 , xs ← 2 : 4 : [] } 1 + length (2 : 4 : [])

Avaliação de Funções Recursivas length [] = 0 length (x : xs) = 1 + length xs length (1 : 2 : 4 : []) ⇒ { x ← 1 , xs ← 2 : 4 : [] } 1 + length (2 : 4 : []) ⇒ { x ← 2 , xs ← 4 : [] }

Avaliação de Funções Recursivas length [] = 0 length (x : xs) = 1 + length xs length (1 : 2 : 4 : []) ⇒ { x ← 1 , xs ← 2 : 4 : [] } 1 + length (2 : 4 : []) ⇒ { x ← 2 , xs ← 4 : [] } 1 + 1 + length (4 : []) ⇒

Avaliação de Funções Recursivas length [] = 0 length (x : xs) = 1 + length xs length (1 : 2 : 4 : []) ⇒ { x ← 1 , xs ← 2 : 4 : [] } 1 + length (2 : 4 : []) ⇒ { x ← 2 , xs ← 4 : [] } 1 + 1 + length (4 : []) ⇒ { x ← 4 , xs ← [] } 1 + 1 + 1 + length [] ⇒

Avaliação de Funções Recursivas length [] = 0 length (x : xs) = 1 + (length xs) length (1 : 2 : 4 : []) ⇒ { x ← 1 , xs ← 2 : 4 : [] } 1 + length (2 : 4 : []) ⇒ { x ← 2 , xs ← 4 : [] } 1 + 1 + length (4 : []) ⇒ { x ← 4 , xs ← [] } 1 + 1 + 1 + length [] ⇒ {}

Avaliação de Funções Recursivas length [] = 0 length (x : xs) = 1 + (length xs) length (1 : 2 : 4 : []) ⇒ { x ← 1 , xs ← 2 : 4 : [] } 1 + length (2 : 4 : []) ⇒ { x ← 2 , xs ← 4 : [] } 1 + 1 + length (4 : []) ⇒ { x ← 4 , xs ← [] } 1 + 1 + 1 + length [] ⇒ {} 1+1+1+0

Conjuntos matemáticos como Listas 

Um dos mais poderosos conceitos de Haskell é o percorrimento automático de uma lista



Definição de subconjuntos em Matemática { x | xε S ∧x>0} Definição de sublistas em Haskell [ x | x <- xs, x > 0 ]



Main> xs = [1,2,3,4,5,6] Main>[ 2*x | x <- xs ] [2,4,6,8,10,12].

Percorrimento de Listas Elementos do percorrimento de uma lista result = [ | <seletor>, ]

O seletor pode ser um padrão addAll :: [(Int,Int)] -> [Int] addAll ps = [ x+y | (x,y) <- ps ]

Podemos aplicar filtros na lista: Main> [ 2*x | x<-[1..10], even x, x<5 ] [4,8]

Meu Primeiro Programa em Haskell module Main where divs :: Int -> [ Int ] divs n = [x | x <-[1..n],mod n x == 0] isPrime :: Int -> Bool isPrime n | ( divs n == [1,n] ) = True | otherwise = False -- vejam a parte acima – acreditem no codigo abaixo -- maiores explicacoes no final do curso main = do args <- getArgs; num <- examine args; putStrLn (show (isPrime num)); examine :: [String] -> IO (Int) examine [num] = return (read num) examine _ = do putStrLn "Usage: isPrime num \n" exitWith (ExitFailure 1)

Definições Aninhadas Definições locais podem ser feitas com “where“: maxof2 :: Int -> Int -> Int maxof2 m n | m >= n = m |m Int -> Int -> Int maxof3 x y z = maxof2 u z where u = maxof2 x y

que é equivalente a: maxof3 x y z = maxof2 (maxof2 x y) z

Quicksort em Haskell qsort:: Ord a => [a] → [a] qsort []

= []

qsort (x:xs) = qsort [y | y ← xs, y <= x ] ++ [x] ++ qsort [z | z ← xs, z > x ]

Quicksort em Haskell qs [3,2,4,1,5] qs [2,1]

++ [3] ++ qs [4,5]

qs[1]++ [2]++qs[]++ [3]++ qs[]++ [4]++ qs[5] [1] ++ [2]++ [] ++ [3] ++ [] ++ [4] ++ [5] [1,2,3,4,5]

Sequência de Fibonnacci 

Leonardo de Pisa (Fibonacci=filius Bonacci) matemático e comerciante da idade média, escreveu em 1202 um livro denominado Liber Abacci.



Problema dos pares de coelhos (paria coniculorum): Quantos pares de coelhos podem ser gerados de um par de coelhos em um ano?  A cada mês ocorre a produção de um par e um par começa a produzir coelhos quando completa dois meses de vida. 

fonte: Ulysses Sodré e Sonia F.L.Toffoli

Sequência de Fibonnaci 

Como o par adulto produz um par novo a cada 30 dias, no início do segundo mês existirão dois pares de coelhos, sendo um par de adultos e outro de coelhos jovens, assim no início do mês 1 existirão 2 pares: 1 par adulto + 1 par recém nascido.

Sequência de Fibonacci 

No início do 5o. mês, 



No início do 6o. mês existirão cinco pares adultos sendo que cada um já produziu um novo par e três pares novos que completaram 1 mês, assim existirão 13 pares: 5 pares adultos + 3 par com 1 mês + 5 pares recém nascidos fib = {1, 1, 2, 3, 5, 8, 13, 21, 34, ...} fib(n+1) = fib(n-1) + fib(n) 

 

existirão três pares adultos sendo que cada um já produziu um novo par e dois pares novos que completaram 1 mês de vida, assim teremos 8 pares: 3 pares adultos + 2 pares(1 mês) + 3 pares recém nascidos.

Sequência de Fibonnaci

fib :: Int -> Int fib n | (n == 0) = 1 | (n == 1) = 1 | (n > 1 ) = fib (n-2) + fib (n-1)

Qual o problema com esta definição?

Sequência de Fibonnacci (versão 2) fib n = fib1 where (fib1, fib2) = fibs n -- (nth, (n+1)th) in Fib. seq. fibs :: Int -> (Int, Int) fibs 0 = (1,1) fibs n = (f2, f1 + f2) where (f1,f2) = fibs (n-1)

Tipos e Classes Parametrizadas

Tipos Polimórficos (Genéricos)   

Uma característica importante de Haskell é o uso de tipos polimórficos (genéricos) Muitas funções podem ser definidas em termos de tipos genéricos Convenção: usamos a, b, c para tipos genéricos

length :: [a] → Int length xs | xs == [] = 0 |otherwise = 1 + length (tail xs)

Exemplos de Funções Genéricas fst :: (a,b) → a head :: [a] → a take :: Int -> [a] -> [a] zip :: [a] -> [b] -> [(a,b)]

Sobrecarga de Operadores e Funções 



Um conceito muito útil em programação é a sobrecarga de operadores Mesmo operador, tipos diferentes Main> 1 + 2 3 Main> 1.1 + 2.2 3.3

Sobrecarga facilita a leitura do código Problema: como especificar a sobrecarga?

Especificação de Sobrecarga 

Idéia inicial – sobrecarga sem restrições

(+) :: a → a → a

Para qualquer tipo, (+) toma dois valores e retorna um Problema: como evitar erros como True + False, “a” + “b”,....

Restrições sobre Reuso de Operadores 

Restrição de classe (sobrecarga de tipos)

(+) :: Num a ⇒ a → a → a

Para qualquer tipo derivado da classe de tipos numéricos, (+) toma dois valores e retorna um

Classes em Haskell 

Uma classe é uma coleção de tipos que suportam certas operações (métodos) comuns



Uma classe define uma assinatura

class Eq a where (==) :: a -> a -> Bool (/=) :: a -> a -> Bool

Classes Básicas em Haskell 

Eq

- tipos com igualdade



Ord

– tipos ordenados



Show – tipos mostráveis



Read – tipos legíveis



Num

– tipos numéricos

Exemplos de Métodos Sobrecarregáveis (==) :: Eq a => a -> a -> Bool (<) :: Ord a => a -> a -> Bool show :: Show a => a -> String read :: Read a => String -> a (*) :: Num a => a -> a -> a

Classe Ord (Tipos ordenáveis) class (Eq a) => Ord a where (<) :: a -> a -> Bool (<=) :: a -> a -> Bool (>=) :: a -> a -> Bool (>) :: a -> a -> Bool max :: a -> a -> a min :: a -> a -> a

Classe Num (Tipos numéricos) class (Eq a, Show a) => Num a where (+), (-), (*) :: a -> a -> a negate :: a -> a abs, signum :: a -> a fromInteger :: Integer -> a

Definindo suas próprias classes data Box = Bx Float Float Float Float data LatLong = LL Float Float class Georeferenced a where box :: a -> Box center :: a -> LatLong

Instâncias de Classes data LatLong = LL Float Float instance Num LatLong where (+) (LL f1 f2) (LL s1 s2) = LL (f1 + s1) (f2 + s2) Instance Ord LatLong where (<=) (LL f1 f2) (LL s1 s2) = (f1 <= s1)

Cria uma instância de um método definido numa interface de uma classe genérica

O papel das classes em Haskell 

Sobrecarga  



Um único nome indica muitas funções (+) engloba adição de inteiros e de reais.

Parametrização Implícita 

 

Quando instanciamos um tipo nosso como derivado de uma classe, herdamos a assinatura definida por seus métodos Todos os (+) tem de ter assinatura a->a->a A instanciação pode ser parcial

Classes em Haskell x Herança em C++ 

Herança em C++ 



Compartilha interface e implementação (estruturas de dados) entre classe base e classe derivada

Classes e Instâncias em Haskell  

Compartilha apenas a assinatura de tipos genéricos entre classe e instância Equivalente a herdar de uma classes abstrata com “templates” em C++

Classe Num (Tipos numéricos) class (Eq a, Show a) => Num a where (+), (-), (*) :: a -> a -> a negate :: a -> a abs, signum :: a -> a fromInteger :: Integer -> a

template class Num { public: operator (+) (T&, T&); }

Propriedades de uma definição de classe class (Eq a) => Ord a where (<), (<=), (>=), (>) :: a -> a -> Bool max, min :: a -> a -> a



O nome da classe fica em maiúsculas



Uma classe pode depender de outra classe



Os métodos da classe devem ser instanciados por todos os tipos que desejarem compartilhar sua assinatura

Criando um novo tipo: Complex 

Idéia = Complex é uma instancia de Num 

Como instância de Num, deve primeiro ser uma instância de Eq e prover métodos para (+), (-), and (*).

data Complex = Cp Float Float cp_add (Cp x y) (Cp a b)= Cp (x+a) (y+b) cp_sub (Cp x y) (Cp a b)= Cp (x-a) (y-b) cp_mult (Cp x y) (Cp a b) = Cp (x*a - y*b) (x*b + a*y)

Instanciando o tipo Complex instance Eq(Complex) where (Cp x y) == (Cp a b) = x==a && y==b instance Show(Complex) where showsPrec = error "No show" showList = error "No show " instance Num(Complex) where x + y = cp_add x y x - y = cp_sub x y x * y = cp_mult x y

Funções como Argumentos de Outras Funções

Passando funções como Argumentos 



Uma característica poderosa de Haskell é funções podem ser argumentos de outras funções Estas funções são chamadas funções de segunda ordem

twice :: (a → a) → a → a twice f x = f (f x)

Map A função map aplica uma função a todos os elementos de uma lista map :: (a → b) → [a] → [b]

Main> map double [1,3,5,7] [2,6,10,14]

Map Map pode ser definido por recursão ou por percorrimento de listas map :: (a → b) → [a] → [b] map f [] = [] map f (x : xs) = (f x) : map f xs

map :: (a → b) → [a] → [b] map f xs = [f x | x ← xs]

Map Map pode incluir predicados mappred :: (a → b) →(a → Bool) →[a] → [b] mappred f p xs = [f x | x ← xs, p x ]

Usando Map incAll = map (plus 1) where plus m n = m + n lengths = map (length)

Note que plus :: Int -> Int -> Int, logo (plus 1) :: Int -> Int. Este tipo de uso de funções é chamado de avaliação parcial.

Avaliação Parcial Haskell distingue entre operadores and funções: Operadores tem noção infixa (e.g. 1 + 2), Funções usam notação prefixa (e.g. plus 1 2). Operadores podem ser convertidos em funções colocando-os entre parênteses: (+) m n = m + n. Haskell aceita operadores com avaliação parcial. E.g.: (+ m) n = m + n

Uso de Map com Avaliação Parcial

incAll = map (1 +) addNewlines = map (++ "\n") halveAll = map (/2) squareAll = map (^2) stringify = map (: [])

Comparação com C++ 

Em C++, o equivalente a um map é um funtor (objeto função) class func{ public: void operator() (int obj); } vector col; for_each(col.begin(), col.end(), func);

in, out :: [Int] func :: (Int → Int) out = map func in

Filter 

A função filter seleciona os elementos de uma lista que satisfazem a um predicado

filter :: (a → Bool) → [a] → [a]

Main> filter even [1..10] [2,4,6,8,10]

Filter 

Pode ser definido como percorrimento de listas ou por recursão filter :: (a → Bool) → [a] → [a] filter p xs = [x | x ← xs, p x]

filter p [] = [] filter p (x : xs) |px = x : filter p xs | otherwise = filter p xs

Padrões de Recursão em Listas 

Um grande número de funções em listas podem ser definidas a partir de um padrão simples de recursão

f [] =v f (x:xs) = x ⊕ f xs

A lista vazia recebe para um valor final, e uma lista não vazia é mapeada para um operador ⊕ que combina o primeiro elemento com a aplicação da função no resto da lista

Padrões de Recursão em Listas sum [] =0 sum (x:xs) = x + sum xs

product [] =1 product (x:xs) = x * product xs

and [] = True and (x:xs) = x && and xs

Função Foldr 

A função foldr (“fold right”) encapsula este padrão de recursão em listas, com a função ⊕ e o valor v como argumentos

sum

= foldr (+) 0

product = foldr (*) 1 and

= foldr (&&) True

Definição de Foldr

foldr::(a -> b -> b) -> b -> [a] -> b foldr f v []

=v

foldr f v (x:xs) = f x (foldr f v xs)

Exemplos Escreva um função produto que multiplica todos os elementos de uma lista E.g., product [2,5,26,14] = 2*5*26*14 = 3640 product :: [Int] -> Int product [] = 1 product (n : ns) = n * product ns

product :: [Int] -> Int product = foldr (*) 1

Exemplo Escreva um função flatten que transforma uma lista de listas numa única lista flatten [[2,5], [], [26,14]] = [2,5,26,14] flatten ["mir", "and", "a"] = "miranda" flatten :: [[a]] -> [a] flatten [] = [] flatten (l : ls) = l ++ flatten ls flatten :: [[a]] -> [a] flatten = foldr [] ++

Mais exemplos de foldr reverse :: [a] -> [a] reverse = foldr swap [] where swap h rl = rl ++ [h]

reverse (1 : (2 : [])) ⇒ swap 1 (swap 2 []) ⇒ (swap 2 []) ++ [1] ⇒ ([] ++ [2]) ++ [1]

Reverse pode ser mais eficiente reverse = rev [] where rev l [] = l rev l (x:xs) = rev (x:l) xs

Reverse pode ser mais eficiente reverse = rev [] where rev l [] = l rev l (x:xs) = rev (x:l) xs

rev [] (1 : (2 : [])) ⇒ rev (1:[]) (2 : [])

Reverse pode ser mais eficiente reverse = rev [] where rev l [] = l rev l (x:xs) = rev (x:l) xs

rev [] (1 : (2 : [])) ⇒ rev (1:[]) (2 : []) ⇒ rev (2:(1:[])) []

Reverse pode ser mais eficiente reverse = rev [] where rev l [] = l rev l (x:xs) = rev (x:l) xs

rev [] (1 : (2 : [])) ⇒ rev (1:[]) (2 : []) ⇒ rev (2:(1:[])) [] ⇒ 2 : (1 : [])

Função foldl (“fold left”) Funções como rev são ditas acumuladores (o resultado é calculado cumululativamente). Elas são usualmente mais eficientes, e podem ser escritas com a função foldl: foldl :: (b -> a -> b) -> b -> [a] -> b foldl f e [] = e foldl f e (x : xs) = foldl f (f e x) xs

Usando foldl

rev = foldl swap [] where swap accList h = h : accList flatten = foldl (++) [] product = foldl (*) 1

Composição de Funções compose :: (b -> c) -> (a -> b) -> a -> c compose f g x = f (g x)

O operador . implementa compose em Haskell (f . g) x = f (g x)

makeLines :: [[char]] -> [char] makeLines = flatten . (map (++ "\n"))

Uso de Funções como Argumentos 

O poder do uso de funções como argumentos em Haskell deriva do sistema de checagem de tipos 



Em C, podemos escrever um “quicksort” que aceite um ponteiro para uma função como argumento. No entanto, não temos como saber se a função apontada tem a assinatura correta

Um “quicksort” genérico em Haskell

qsortF :: (a -> a-> Bool) -> [a] -> [a]

A função usada no “quicksort” genérico deve ter uma assinatura compatível com o tipo da lista a ser ordenada

Quick Sort Genérico qsortF :: (a -> a -> Bool) -> [a] -> [a] qsortF f [] = [] qsortF f (x:xs) = qsortF f [y | y<-xs, f y x] ++ [x] ++ qsortF f [y | y<-xs, not (f y x)] -- Função de comparação na ordem lexicográfica inversa tailComp :: String -> String -> Bool tailComp s t = reverse s < reverse t -- List of sample words myWords = ["foo", "bar", "baz", "fubar", "bat"] -- tOrd is ["foo","bar","fubar","bat","baz"] tOrd = qsortF tailComp myWords -- hOrd is ["bar","bat","baz","foo","fubar"] hOrd = qsortF (<) myWords

Usando notação “Lambda” 

Passar funções para outras funções é apenas parte do poder de Haskell



As funções também podem agir como “fábricas”, e produzir novas funções como resultados 

Poderiamos produzir uma nova função de comparação e passa-la como argumento de “quicksortF”

Usando notação “Lambda” 

Um meio de criar uma função é a notação lambda. 

A notação lambda é uma descrição genérica de uma função

λ x → x*x

Haskell usa o caracter “\” (que parece um pouco com λ ) sumSquares :: [Int] -> Int sumSquares xs = foldr (+) 0 ( map (\x -> x*x) xs )

Usando notação “Lambda”

square :: Int -> Int square n = n*n sumSquares :: [Int] -> Int sumSquares xs = foldr (+) 0 ( map (\x -> x*x) xs ) -- ( map square xs)

Usando notação “Lambda” Uma função em Haskell que expressa a derivada de outra função

slope :: (Double→Double)→ (Double→Double) slope f = (\x →(f(x+dta x) - f(x-dta x))/(2*dta x)) where dta x = x / 10000

Tipos Definidos pelo Usuário

Declaração de Novos Tipos de Dados Podemos definir novos tipos usando Data: data CardinalPoint = North | East | South | West

O compilador trata este valores como valores do novo tipo: Main> :t East East :: CardinalPoint Main> East ERROR - cannot find "show" function ...

Herdando Propriedades de Classes Genéricas data CardinalPoint = North | East | South | West deriving (Eq, Show)

Main> East East Main> East == West False

Tipos Enumeráveis Tipos definidos com constantes são enumeráveis

data Colours = Red | Orange | Yellow | Green | Blue | Purple -- Bool é tipo enumerável nativo: --- data Bool = True | False

Construtores Como em C++, definimos tipos não-enumeráveis associando-os a um construtor e seus parâmetros // C++ class Point { public: Point (Double& x, Double& y) private: Double _x, _y; }

-- Haskell data Point = Point (Double,Double) deriving (Show)

Construtores Para criar instâncias do tipo, temos de usar o construtor -- Haskell data Point = Pt (Double,Double) deriving (Show) Main> Pt (3.4, 6.5) Pt (3.4, 6.5) Main> :t Pt (3.4, 6.5) Pt (3.4, 6.5) :: Point main> :t Pt Pt :: (Double, Double) -> Point

Construtores Construtores podem ser usados em funções: data Point = Point (Double, Double) deriving (Show) getX :: Point -> Double getX (Point (x,y)) = x

Main> getX (Point (3.4, 6.5)) 3.4

Lembrete: Herança em C++ class Shape{ public: float area() = 0; }; class Circle : public Shape { public: Circle (float& radius); float area() {/*...*/} private: float radius; }; class Rect : public Shape { public: Rect (float& x, float& y); float area() {/*...*/} private: float x, y; }; Shape* s = new Circle (2.3); float a = area (Shape);

Herança em Haskell data Shape = Circle Float | Rect Float Float area :: Shape → Float area (Circle r) = pi* r^2 area (Rect x y) = x * y

Não existe especialização em Haskell, mas apenas generalização Generalização é expressa nas funções e dispersa pelo código

Tipos Podem Incluir Parâmetros Genéricos Tipos podem ser definidos com parâmetros genéricos: data ThingAtPoint a = TAP (a,Point) deriving Show Main> :t TAP(0::Int, Pt(2,4)) ... :: ThingAtPoint Int Main> :t TAP("begin", Pt(2,4)) ... :: ThingAtPoint [Char]

Tipos Genéricos Todos os parâmetros de um tipo podem ser genéricos data ThingAndList a b = TL a [b] deriving Show getList :: ThingAndList a b -> [b] getList (TL t l) = l

Main> getList (TL 7 "prosper") prosper

Funções Polimórficas Construtores com parâmetros genéricos permitem funções polimórficas: data IntList a = IL Int [a] deriving Show mapList :: (a -> b) -> IntList a -> IntList b mapList f (IL n l) = IL n (map f l)

Main> mapList ord (IL 7 "abc") IL 7 [97,98,99]

Sumário 

Programadores podem definir tipos com especificação de construtores



Estes tipos são distintos dos demais (nomes de construtores não podem ser reutilizados)



Definições podem usar tipos parametrizados

Tipos Recursivos Haskell admite tipos recursivos: data Nat = Zero | Succ Nat

Nat é um novo tipo com construtores Zero :: Nat e Succ :: Nat → Nat

Tipos Recursivos data Nat = Zero | Succ Nat

Um valor do tipo Nat é Zero, ou da forma Succ n onde n :: Nat (sequência infinita de valores) Zero Succ Zero Succ (Succ Zero)

Tipos Recursivos data Nat = Zero | Succ Nat

Pensemos em Nat como os números naturais criados pelos axiomas de Peano Succ (Succ (Succ Zero)) ---corresponde ao número 3

Tipos Recursivos – Comparação com C++ data Nat = Zero | Succ Nat

Em C++ representamos tipos recursivos com ponteiros struct Nat { Int zero; Nat* succ; }

A representação em Haskell é mais abstrata

Uso de Tipos Recursivos Podemos expressar a conversão entre Nat e Int nat2int :: Nat -> Int nat2int Zero =0 nat2int (Succ n) = 1 + nat2int n int2nat int2nat 0 int2nat n

:: Int -> Nat = Zero = Succ (int2nat (n-1))

Tipos Recursivos

Exemplos de tipos recursivos: data Nat = Zero | Succ Nat data List a = Nil | Cons a (List a) data BTree a = Leaf a | Fork (BTree a) (BTree a)

Exemplo de B-Tree de Inteiros Fork Leaf

Fork

2

Fork

Leaf

Leaf

Leaf

1

5

9

Como é construída esta árvore?

Exemplo de B-Tree de Inteiros Fork Leaf

Fork

2

Fork

Leaf

Leaf

Leaf

1

5

9

Fork(Leaf 2)(Fork(Fork Leaf 1 Leaf 5) Leaf 9)

Funções Recursivas em B-Trees data BTree a = Leaf a | Fork (BTree a) (BTree a) sumAll :: BTree Int -> Int sumAll (Leaf n) = n sumAll (Fork t1 t2) = (sumAll t1)+(sumAll t2) leaves :: BTree a -> [a] leaves (Leaf x) = [x] leaves (Fork t1 t2) = (leaves t1)++(leaves t2)

Funções Recursivas em B-Trees data BTree a = Leaf a | Fork (BTree a) (BTree a) bTree_Map :: (a -> b) -> (BTree a) -> (BTree b) bTree_Map f (Leaf x) = Leaf (f x) bTree_Map f (Fork t1 t2) = Fork (bTree_Map f t1) (bTree_Map f t2)

Expressões Aritméticas + Val

*

2

+ Value 1

Val Value 5

9

Expressões Aritméticas data Expr = Val Int | Add Expr Expr | Mul Expr Expr

Add (Val 1) (Mul (Add Val 2 Val 5) Val 9) -- 1 + (2+5)*9

Funções sobre Expressões Aritméticas eval

:: Expr -> Int

eval (Val n) = n eval (Add x y) = x + y eval (Mul x y) = x * y

Avaliação Preguiçosa e Listas Infinitas

Avaliação Preguiçosa (“Lazy evaluation”) 

Em C++, a avaliação de expressões é estrita e imediata 



Em Haskell, a avaliação é preguiçosa 



Se escrevemos x = y + z , o compilador avalia a expressão imediatamente

Expressões são avaliadas apenas se necessário

Consequências de avaliação preguiçosa  

Podemos trabalhar com listas infinitas Apenas aquelas partes da lista que são necessárias para a avaliação da expressão serão calculadas explicitamente

Listas Infinitas Haskell tem uma notação implícita para listas: Main> [0..7] [0,1,2,3,4,5,6,7]

O limite superior pode ser omitido: Main> [1..] [1,2,3,4,5,6,7, ... ... 2918,2919,291<<not enough heap space -- task abandoned>>

Listas Infinita Listas infinitas como [1..] podem ser usadas em programas que usam apenas parte delas: Main> head (tail (tail (tail [1..]))) 4 Main> reverse [1..] Error – insuficient space

Este estilo de programação é uma combinação de "geradores e seletores" • [1..] é um gerador • head.tail.tail.tail é um seletor

Um Seletor A função takeWhile retorna o maior segmento inicial de uma lista que satisfaz uma propriedade p: takeWhile :: (a -> Bool) -> [a] -> [a] takeWhile p [] = [] takeWhile p (x : xs) |px = x : takeWhile p xs | otherwise = []

Main> takeWhile (<10) [1, 2, 13, 3] [1,2] Main> takeWhile (<10) [1..] [1,2,3,4,5,6,7,8,9]

Recursão Infinita

A expressão [n..] pode ser implementado por uma função que gera uma recursão infinita: natsfrom :: num -> [num] natsfrom n = n : natsfrom (n+1)

Esta função pode ser chamada da forma usual Main> natsfrom 0 [0,1,2,3,....

Crivo de Eratóstenes

Um número é primo se é divisível por 1 e por ele mesmo O crivo • • •

Começe em 2 Delete todos os múltiplos do primeiro numéro do restante da lista Repita

Crivo de Eratóstenes -- Crivo de Eratóstenes primes = crivo [2 .. ] -- este é o crivo crivo(x:xs) = x: crivo [y | y <- xs, rem y x /=0] -- “n é membro de uma lista ordenada?” isMemberOrd (x:xs) n | x < n = isMemberOrd xs n | x == n = True | otherwise = False isPrime n = isMemberOrd primes n

Escrevendo Programas (incluindo I/O) Material adaptado de Simon Peyton-Jones e Graham Hutton

O problema

Um programa em Haskell consiste num conjunto de funções, sem efeitos colaterais

Tensão

O objetivo de executar qqer programa é ter algum efeito colateral

A Solução Escrever programas interativos em Haskell usando tipos que fazem distinção entre expressões funcionais “puras” de ações “impuras” que podem envolver efeitos colaterais

IO a

O tipo das ações de IO que retornam um valor do tipo a

IO Char

IO ()

O tipo das ações de IO que retornam um caracter

O tipo das ações que não tem valor de retorno

I/O em Haskell

Um valor do tipo (IO t) é uma ação que, quando realizada, pode fazer alguma forma de IO antes de devolver um resultado do tipo t.

IO em Haskell: O tipo (IO a) Um valor do tipo (IO t) é uma ação que, quando realizada, pode fazer alguma forma de IO antes de devolver um resultado do tipo t. type IO a = World -> (a, World) result::a World in

IO a

World out

O conceito de ação Um valor do tipo (IO t) é uma ação que, quando realizada, pode fazer alguma forma de IO antes de devolver um resultado do tipo t. type IO a = World -> (a, World)  Uma ação é um valor de primeira ordem  Avaliar uma ação não tem efeito colateral  Realizar a ação tem um efeito

Ações Primitivas A biblioteca padrão fornece um número de ações básicas: 

A ação getChar lê um caracter do teclado, ecoa na tela e retorna um caracter como resultado:

getChar :: IO Char

Ações Primitivas 

A ação putChar c escreve um caracter na tela, sem valor de retorno:

putChar :: Char → IO () 

A ação return v retorna um valor v, sem realizar qualquer interação:

return :: a → IO a

Seqüência de Ações Uma seqüência de ações pode ser combinadas com o comando do. Por exemplo: getTwo :: IO (Char,Char) getTwo

= do x ← getChar y ← getChar return (x,y)

Sequencia de Ações 

Cada ação deve começar precisamente na mesma coluna da anterior (regra do leioute).



Os valores de retorno das ações intermediárias são descartados por default, mas podem ser aproveitados usando o operador ← .



O valor retornado pela última ação é o valor associado ao tipo de retorno da ação composta.

Outras Ações em Haskell 

Ler uma palavra do teclado: getLine :: IO [Char] getLine = do { x ← getChar if x == '\n' then return [] else do { xs ← getLine return (x:xs) } }

Ações em Haskell 

Escrever uma palavra na tela: putStr :: String → IO () putStr [] = return () putStr (x:xs) = do putChar x putStr xs



Escrever uma palavra e pular uma linha: putStrLn :: String → IO () putStrLn xs = do putStr xs putChar '\n'

Exemplo Uma ação que recebe uma linha e apresenta seu comprimento: strlen :: IO () strlen = do putStr "Enter a string: " xs ← getLine putStr "The string has " putStr (show (length xs)) putStrLn " characters"

Examplos 

Uma função que recebe uma listas de questões e vai recolhendo respostas para uma lista quest :: [String] -> IO [String] quest [] = return [] quest (q:qs) = do r <- dialogo q rs <- quest qs return (r:rs)

dialogo :: String -> IO String dialogo s = do putStr s r <- getLine return r

Funções de IO em Haskell getChar getLine

:: IO Char :: IO String

putChar :: Char -> IO() putString :: String -> IO() putStrLn :: String -> IO() print :: Show a => a -> IO ()

Ler e escrever do “standard input”

Funções de IO em Haskell

writeFile :: FilePath -> String -> IO() appendFile :: FilePath -> String -> IO() readFile :: FilePath -> IO String type FilePath = String

Ler e escrever de arquivos de texto

IO Básico em Haskell Char

getChar

getChar :: IO Char putChar :: Char → IO () main :: IO () main = putChar ‘x’

()

Char

putChar

O “main” é do tipo IO ()

O combinador (>>=) (>>=) :: IO a → (a → IO b) → IO b () Char

getChar

 Conectamos duas ações echo :: IO () echo = getChar >>= putChar

putChar

O combinador >>= echoDup :: IO () echoDup = getChar >>= (\c → putChar c >>= (\() → putChar c))

Os parênteses são opcionais

O combinador (>>) echoDup :: IO () echoDup = getChar >>= \c -> putChar c >> putChar c

(>>) :: IO a → IO b → IO b m >> n = m >>= (\x → n)

O combinador return getTwoChars :: IO (Char,Char) getTwoChars = getChar >>= \c1 -> getChar >>= \c2 -> return (c1,c2)

return :: a → IO a

return

Conveniência de notação (uso de “do”) getTwoChars :: IO (Char,Char) getTwoChars = do { c1 <- getChar ; c2 <- getChar ; return (c1,c2) }

“do” é uma conveniência de notação que engloba os combinadores (>>=) e (>>)

Conveniência de notação (uso de “do”) “do” é uma conveniência de notação que engloba os combinadores (>>==) e (>>) do {x←e; s} =

e >>= \x → do { s }

do {e; s}

=

e >> do { s }

do { e }

=

e

(>>=) :: IO a → (a → IO b) → IO b (>>) :: IO a → IO b → IO b

GetLine getLine :: IO [Char] getLine = do { c <- getChar; if c == ‘\n’ then return [] else do { cs <- getLine; return (c:cs) } } Vejam o uso recursivo de “do”

Estruturas de controle (“loops”) Valores do tipo (IO t) são valores de primeira classe que podem ser combinados para formar “loops” forever :: IO () -> IO () forever a = a >> forever a repeatN :: Int -> IO () -> IO () repeatN 0 a = return () repeatN n a = a >> repeatN (n-1) a

Loops em Haskell O combinador (>>) nos permite escrever laços em Haskell (>>) :: IO a → IO b → IO b m >> n = m >>= (\x → n) for :: [a] -> (a -> IO b) -> IO () for [] fa = return () for (x:xs) fa = fa x >> for xs fa

for [1..10] (\x -> putStr (show x))

Loops

Uma lista de ações de IO

sequence :: [IO a] -> IO [a] sequence [] = return [] sequence (a:as) = do { r ← a;

Uma ação de IO que retona uma lista de a

rs ← sequence as; return (r:rs) }

for :: [a] → (a → IO b) → IO () for xs fa = sequence (map fa xs) >> return ()

Mônadas 

Na época da Renascença, Giordano Bruno (1548-1600) inventou a expressão mônada. Segundo este autor, as mônadas são os elementos das coisas.



A alma humana é uma mônada e Deus é ao mesmo tempo a mônada mínima e máxima, porque tudo vem dele (LEIBNIZ – 1714/1991 p. 123).



A mônada é uma "substância simples" composta de um "aggregatum" das coisas simples. Ela não podem ser dividida.

(fonte: Luís Carlos Lopes, UFF)

Mônadas Na programação funcional, conceito de mônada é usado para sintetizar a ideia de ações. Uma ação é vista como algo que se passa dentro de uma caixa preta e da qual conseguimos apenas ver os resultados. class Monad m where return :: a → m a (>>==) :: m a → (a → m b) → m b -- bind (>>) :: m a → m b → m b -- seq fail :: String → m a

Mônadas class Monad m where return :: a → m a (>>==) :: m a → (a → m b) → m b -- bind (>>) :: m a → m b → m b -- seq fail :: String → m a -- definicoes basicas p >> q = p >>= \_ → q fail s = error s

Monads 

Uma mônada consiste de:  

Um construtor de tipos M duas funções

>>= :: M a → (a → M b) → M b return :: a → M a 

(mais algumas regras)

Regras para mônadas return x >>= f m

=

fx

>>= return = m

m1 >>= (λ x.m2 >>= (λ y.m3)) = (m1 >>= (λ x.m2)) >>= (λ y.m3)

Estas regras indicam que a monada tem a propriedade da comutatividade e a uma operação “neutra”

Como saimos do controle do IO? return :: a → IO a return gera um tipo (IO a) a partir de um tipo a (isto é usado no final de um “do loop” para terminar uma sequencia de comandos returnInv :: IO a → a porque isto viola as regras de programação funcional? ...muda o estado do programa

Como saimos do controle do IO? returnInv :: IO a → a Podemos viver sem esta função? Será que todas as interações tem de ficar dentro de um loop de IO?

Como saimos do controle do IO? returnInv :: IO a → a Podemos viver sem esta função? Será que todas as interações tem de ficar dentro de um loop de IO? Não... Temos uma saída... “what the devil has produced to tempt the poor functional programmer” unsafePerformIO:: IO a → a

Organização de Programas

Leiaute 

Ao contrário de quase todas as linguagens de programação, o Haskell não necessita de marcas para delimitar as diversas declarações que constituem um programa.



Em Haskell a identação do texto (isto é, a forma como o texto de uma definição está disposto), tem um significado bem preciso.

Leiaute 

Se uma linha começa mais à frente do que começou a linha anterior, então ela deve ser considerada como a continuação da linha anterior.



Se uma linha começa na mesma coluna que a anterior, então elas são consideradas definições independentes.



Se uma linha começa mais atrás do que a anterior, então essa linha não pretence à mesma lista de definições.

Modulos 

Um programa Haskell está organizado em módulos.  

Cada módulo é uma colecção de funções e tipos de dados, definidos num ambiente fechado. Um módulo pode exportar todas ou só algumas das suas definições. (...)

module Nome (nomes_a_exportar) where ... definições ... 

Um módulo constitui um componente de software e dá a possibilidade de gerar bibliotecas de funções que podem ser reutilizadas em diversos programas Haskell.