Haskell/Soluções

Básico

editar
Exercícios
  1. Explique como GHCi avaliaria quadruplicar 5}.
  2. Defina uma função que subtraia 12 da metade de seu argumento.
  1. quadruplicar x = dobrar (dobrar x)
    quadruplicar 5 = dobrar (dobrar 5)
    quadruplicar 5 = dobrar 10
    quadruplicar 5 = 20
    
  2. subtrairMetade x = x / 2 - 12
    
Exercícios
  1. Escreva uma função para calcular o volume de uma caixa.
  2. Aproximadamente, de quantas pedras as famosas pirâmides de Gizé feitas? Dica: você vai precisar estimar o volume da pirâmide e o volume de cada bloco de pedra.
  1. volumeCaixa b a l = b * a * l
    

  2. Uma possível solução para o problema da pirâmide seria: calcular o volume da pirâmide como se ela fosse ideal e dividir tal valor pelo volume estimado de um bloco de pedra. Por exemplo, no GHCi:
Prelude> let volumeCaixa b a l = b * a * l
Prelude> let volumePiramBaseQuadrada b h = (b ^ 2) * h / 3
Prelude> (volumePiramBaseQuadrada 230.4 146.5) / (volumeCaixa 1 1 1)
2592276.48
Exercícios
  1. Escreva uma função que calcule o volume de um cilindro. O volume de um cilindro é a área da base, que é um círculo, multiplicada pela altura. Como você já programou a função da área de um círculo neste capítulo, você pode reutilizá-la aqui.
  1. area r = pi * r ^ 2
    volumeCil r h = h * area r
    
Exercício

  1. Use :type seguido de um valor como "H" no GHCi. Perceba que usamos aspas duplas aqui. O que acontece? Por quê?
  2. Use :type seguido de um valor como 'Olá, mundo' no GHCi. Perceba que usamos aspas simples aqui. O que acontece? Por quê?

  1. O tipo é [Char]. Trata-se de um string de um elemento só.
  2. GHCi retorna um erro. Aspas simples são usadas para delimitar um único caractere, sendo que Olá, mundo é um string, ou seja, uma cadeia com mais de um caractere.


Exercícios

Tente deduzir quais as anotações de tipos das seguintes funções. Se alguma delas envolver números, suponha que sejam do tipo Int.

  1. negativo: uma função que recebe um Int e retorna seu oposto (sinal invertido). Ex: negativo 4 = -4; negativo (-2) = 2.
  2. (||): a função lógica "ou". Ela recebe dois booleanos e compara se pelo menos um deles é verdadeiro. Se sim, retorna verdadeiro, se não, falso.
  3. diasNoMes: uma função que calcula a quantidade de dias num determinado mês. Ela recebe uma valor para indicar se o ano é bissexto ou não, e o número do mês, de 1 a 12.
  4. f x y = not x || y
  5. g x = (2*x - 1)^2
  1. negativo :: Int -> Int
    
  2. (||) :: Bool -> Bool
    
  3. diasNoMes :: Bool -> Int -> Int
    
  4. f :: Int -> Int -> Bool
    
  5. g :: Int -> Int
    

Criando listas

editar
Exercício

  1. 3:[True,False] é um código válido em Haskell? Por quê?
  2. Escreva uma função chamada cons8 que recebe uma lista como argumento e adiciona 8 ao seu início. Teste os seguintes exemplos:
    1. cons8 []
    2. cons8 [1,2,3]
    3. cons8 [True,False]
    4. let foo = cons8 [1,2,3]
      cons8 foo
  3. Adapte cons8 para que ela adicione 8 ao fim da lista. (Dica: lembre-se que usamos (++) para concatenar duas listas de caracteres anteriormente.)
  4. Escreva uma função de dois argumentos, uma lista e um elemento, e que adiciona o elemento à lista. Comece com:
let meuCons lista elemento =

  1. Não. Todos os elementos de uma lista devem ser do mesmo tipo. Em 3:[rue,False] tenta-se adicionar um número a uma lista de Bools, o que não é permitido.
  2. cons8 lista = 8:lista
    
  3. cons8' lista = lista ++ [8]
    
  4. let meuCons lista elemento = elemento : lista

Lista de listas

editar
Exercícios
  1. Quais das seguintes linhas são códigos válidos e quais não são? Reescreva-as usando a notação de cons.
    1. [1,2,3,[]]
    2. [1,[2,3],4]
    3. [[1,2,3],[]]
  2. Quais das seguintes linhas são códigos válidos e quais não são? Reescreva-as usando a notação de colchetes.
    1. []:[[1,2,3],[4,5,6]]
    2. []:[]
    3. []:[]:[]
    4. [1]:[]:[]
    5. ["hi"]:[1]:[]
  3. Em Haskell, é possível termos uma lista de listas de listas? Por quê?
  4. Diga por que este código é inválido:
    1. [[1,2],3,[4,5]]
  1. Apenas o item 3 é válido.
    1. 1:2:3:[]:[]. 1, 2 e 3 são números, enquanto [] é uma lista.
    2. 1:(2:3:[]):4:[]. O mesmo caso de antes
    3. (1:2:3:[]):[]:[]. É válido porque 1:2:3:[] é uma lista de números e [] é uma lista vazia (de qualquer tipo).
  2. Apenas o item 5 é inválido.
    1. [[],[1,2,3],[4,5,6]]. [1,2,3] e [4,5,6] são listas de números, portanto, temos uma lista de listas de números. Assim sendo, pode-se adicionar uma lista vazia a uma lista de listas.
    2. [[]]. Não é uma lista vazia!. Na verdade, é uma lista que contem um único elemento, o qual é uma lista vazia.
    3. [[],[]]. Uma lista contendo duas lista, as quais estão vazias.
    4. [[1],[]]. O mesmo que o caso anterior. Entretanto, uma das duas listas vazias agora contem um elemento. Mesmo assim, continua sendo uma lista de listas.
    5. [["hi"], [1]]. ["hi"] é uma lista de Chars, enquanto [1] é uma lista de Strings, enquanto [1] é uma lista de números.
  3. Sim, é possível. Podemos criar lista em quantos níveis quisermos em Haskell, desde que todos os elementos tenham todos a menas quantidade de níveis. Eis um exemplo: [[[1],[2],[3]],[[4],[5],[6]],[[7],[8],[9]]].
  4. Não é válido porque 3 é um número apenas, enquanto que [1,2] e [4,5]] são listas de números. Uma lista válida seria [[1,2],[3],[4,5]].

N-uplas

editar
Exercícios
  1. Escreva uma tripla cujo primeiro valor seja 4, o segundo seja "ola", e o terceiro seja True.
  2. Quais dos seguntes são n-uplas válidas?
    1. (4, 4)
    2. (4, "ola")
    3. (True, "bla", "foo")
    4. ()
  3. Listas podem ser criadas ao se adicionar um novo elemento a uma outra lista. Entretanto, não existe uma operação similar para manipular n-uplas.
    1. Qual o motivo disto?
    2. Suponha que haja, sim, uma operação semelhante. O que você teria ao "adicionar" um elemento a uma n-upla?


  1. (4, "ola", True)
  2. Todos os itens são válidos. Diferente de uma lista, uma n-upla não tem restrições quanto ao tipo de seus elementos.
  3. É uma restrição da própria linguagem. É possível que os desenvolvedores de Haskell quisessem limitar o uso de n-uplas para que tivessem comprimento pequeno, mantendo as listas como a principal estrutura para armazenar grande volume de dados.
  4. Uma nova n-upla, cujo tipo seria diferente do tipo original.


N-uplas dentro de n-uplas e outras combinações

editar
Exercícios
  1. Quais das seguintes linhas de código são válidas em Haskell? Por quê?
    • 1:(2,3)
    • (2,4):(2,3)
    • (2,4):[]
    • [(2,4),(5,5),('a','b')]
    • ([2,4],[2,2])
  1. Apenas o terceiro e o último item são válidos.
    • A operação de cons não funciona com duplas.
    • O mesmo problema que o caso de antes.
    • É válido pois aqui adiciona-se uma dupla a uma lista vazia.
    • A lista é inválida porque seus elementos não são do mesmo tipo: (2,4) e (5,5) são duplas de números, enquanto que ('a','b') é uma dupla de Char.
    • É válido porque é uma dupla de listas. E a listas são válidas porque em cada uma delas, todos os elementos são do mesmo tipo.

Outros problemas

editar
Exercícios
  1. Crie uma combinação de fst e snd para extrair o valor 4 da segunte n-upla: (("Ola", 4), True)
  2. A notação geralmente usada para representar um tabuleiro de xadrez é diferente da que usamos aqui: a linhas são enumeradas de 1 a 8, e as colunas são nomeadas de A a H, sendo que o nome das colunas vem primeiro. Mesmo assim, ainda seria possível criar uma dupla para representar uma casa específica, como ('A', 4), por exemplo? Qual importante diferença entre listas e n-uplas este caso ilustra?
  3. Escreva uma função que retorne a cabeça e a cauda de uma lista como sendo o primeiro e segundo elemento de uma dupla.
  4. Use head e tail para escrever uma função que retorne o quinto elemento de uma lista. A seguir, comente sobre ela, apontando incômodos e problemas que você tenha percebido.
  1. Uma possível solução seria: snd (fst (("Ola", 4), True)).
  2. Sim, pois uma dupla permite que seus elementos sejam de qualquer tipo, ao contrário de uma lista que exige que todos os elementos sejam do mesmo tipo.
  3. cabecaCauda lista = (head lista, tail lista)
    
  4. quintoElemento lista = head (tail (tail (tail (tail lista))))
    
Para criar a função quintoElemento precisamos repetir tail quatro vezes. Toda essa repetição deixa o código mais propenso a erros e mais difícil de ler.


Tipos polimórficos

editar
Exercícios

Sugira uma assinatura de tipo para as seguintes funções:

  1. A solução do terceiro exercício da seção anterior: "uma função que retorne a cabeça e a cauda de uma lista como sendo o primeiro e segundo elemento de uma dupla".
  2. A solução do quarto exercício da seção anterior: "uma função que retorne o quinto elemento de uma lista".
  3. h x y z = chr (x - 2) (lembre-se que discutimos sobre chr no capítulo anteior).
  1. cabecaCauda :: [a] -> (a, [a])
    
  2. quintoElemento :: [a] -> a
    
  3. h :: Int -> a -> b -> Char -- y e z não são usados, portanto, seus tipos não importam e nem precisam ser iguais
    
Exercício

Por que as expressões dentro de then e else contidas num mesmo if devem possuir o mesmo tipo?

Numa expressão if, é dentro de then e else que são definidos os possíveis resultados finais. Em Haskell, toda expressão deve ter um tipo fixo, imutável. Como não sabemos qual caso será avaliado, se then ou se else, ambos devem possuir o mesmo tipo final para satisfazer o prerequisito de imutabilidade de tipos de Haskell.

Exercício

Reescreva a função pts usando guardas.

pts :: Int -> Int
pts x
  | x == 1    = 10
  | x == 2    = 6
  | x == 3    = 4
  | x == 4    = 3
  | x == 5    = 2
  | x == 6    = 1
  | otherwise = 0
Exercício

A versão de casamento de padrões de pts e esta última versão mista são ligeiramente diferentes. Você consegue ver a diferença? Conseguiria reescrever a versão mista para que as duas retornem os mesmos resultados sempre? Dica: compare a definição matemática e a implementação em Haskell e preste atenção a condição implícita da definição matemática.

A condição implícita de   é que   deve ser maior que ou igual a 1 sempre: não há posição 0 ou posições negativas.

A diferença acontece quando o argumento de pts é menor que 1. Na versão com casamento de padrões, se o argumento for -1, por exemplo, o padrão casado será o último (_) e o resultado seria 0. Na versão mista, entraríamos no padrão com guardas, a primeira guarda seria verdadeira (pois (-1) <= 6 é verdadeiro), e o resultado final seria 7 - (-1), que é 8, um resultado errado.

Uma possível solução seria escrever:

pts :: Int -> Int
pts 1 = 10
pts 2 = 6
pts x
    | x < 1 || x > 7 = 0
    | otherwise      = 7 - x
Exercício

Escreva uma função quarto que extraia o quarto elemento de uma 10-upla.

quarto :: (a,b,c,d,e,f,g,h,i,j) -> d
quarto (_,_,_,x,_,_,_,_,_,_) = x
Exercício

No capítulo Tipos básicos, mencionamos a função abrirJanela de forma simplificada. Se pensarmos que toda ação realizada com o mundo externo é marcada por IO, qual deveria ser o tipo de abrirJanela?

Como abrir uma janela implica numa ação com consequências no ambiente externo, a saída de abrirJanela deve ser IO:

abrirJanela :: JanelaTitulo -> JanelaTamanho -> IO Janela
Exercício

Explique por que não se pode usar putStrLn sem ter aplicado show nos seguintes exemplos:

  1. (putStrLn . show) 2
  2. (putStrLn . show) (2 > 3)

A função putStrLn recebe apenas argumentos do tipo String. Em ambos os casos, 2 e (2 > 3) não são String. Eles são um Num e um Bool, respectivamente. A função show converte ambos numa representação do tipo String que pode então ser usada como argumento de putStrLn.

Exercício

Escreva um programa que peça para o usuário digitar a base e a altura de um triângulo e que calcule sua área. Ele deve apresentar o resultado na tela. Um exemplo seria:

A base?
3.3
A altura?
5.4
A área do triângulo é 8.91.
Você deve vai precisar usar as funções read e show para converter o texto do usário em número, e depois o resultado numérico em texto.

main :: IO ()
main =
  do putStrLn "A base?"
     base <- getLine
     putStrLn "A altura?"
     altura <- getLine
     putStrLn ("A área do triângulo é " ++ show (area base altura) ++ ".")
       where area b a = (read b :: Float) * (read a :: Float) / 2
Exercício

Escreva um programa que pergunta o nome do usuário. Se o nome for Carlos ou Pedro, o programa responde que Haskell é uma ótima linguagem de programação. Se for Maria, o programa responde que Haskell pode ser aprendido por qualquer um. Se for qualquer outra resposta, o programa responde que não conhece o usuário. Escreva pelo menos uma solução usando if ... then ... else ....

main :: IO ()
main =
  do putStrLn "Olá! Qual o seu nome?"
     nome <- getLine
     if nome == "Carlos" || nome == "Pedro"
        then putStrLn "Haskell é uma ótima linguagem de programação, não é mesmo?"
        else if nome == "Maria"
                then putStrLn "Acredito que Haskell pode ser aprendido por qualquer pessoa!"
                else putStrLn "Desculpe-me, não te conheço."

Uma possível solução usando casamento de padrões:

main :: IO ()
main =
  do putStrLn "Olá! Qual o seu nome?"
     nome <- getLine
     putStrLn (resposta nome)
       where otimaLinguagem    = "Haskell é uma ótima linguagem de programação, não é mesmo?"
             resposta "Carlos" = otimaLinguagem
             resposta "Pedro"  = otimaLinguagem
             resposta "Maria"  = "Acredito que Haskell pode ser aprendido por qualquer pessoa!"
             resposta _        = "Desculpe-me, não te conheço."

Introdutório

editar

Recursividade numérica

editar
Exercício

  1. O que acontece se calcularmos fatorial (-1)?
  2. Como já vimos antes, a ordem dos padrões é importante quando definimos uma função. Se fizéssemos
    fatorial n = n * fatorial (n - 1)
    fatorial 0 = 1
    
    e tentássemos calcular fatorial 6, o que aconteceria?
  3. O fatorial duplo de um número é a multiplicação dos sucessores intercalados, partindo de 1 (ou 2) até o argumento. Por exemplo: o fatorial duplo de 8 é 8 × 6 × 4 × 2 = 384; o fatorial duplo de 7 é 7 × 5 × 3 × 1 = 105. Defina uma função fatorialDuplo em Haskell que faça esta conta.

  1. O compilador começaria a avaliar
    (-1) * fatorial (-2)
    (-1) * (-2) * fatorial (-3)
    (-1) * (-2) * (-3) * fatorial (-4)
    e assim por diante. Como a definição de fatorial não possui nenhum caso que impeça essa expansão, o compilador começaria o processo mas nunca consegueria terminá-lo corretamente.
  2. O compilador avaliaria corretamente até 6 * 5 * 4 * 3 * 2 * 1 * fatorial 0. Neste ponto, ele deveria encerrar a recursividade, mas como um argumento 0 satisfaz a condição do primeiro caso, o caso base nunca seria avaliado e a expansão do fatorial continuaria pelos números negativos. O resultado seria o mesmo que o do exercício anterior.
  3. fatorialDuplo 1 = 1
    fatorialDuplo 2 = 2
    fatorialDuplo n = n * fatorialDuplo (n - 2)
    
Exercício

  1. Defina uma função recursiva chamada potencia tal que o resultado de potencia x y seja x elevado à potência y.
  2. Lhe é dada a função maisUm x = x + 1. Sem usar (+) novamente, e usando apenas maisUm e (-), defina a função recursiva adicao tal que adicao x y resulte na soma de x e y. Considere apenas números inteiros não-negativos.
  3. Escreva a função log2 que calcula o logaritmo de seu argumento na base 2. Por exemplo: log2 1024 = 10, log2 1 = 0, log2 11 = 3. Dica: use números inteiros, e use div x y (uma função nativa de Haskell) para calcular o quociente da divisão de x por y.

  1. potencia _ 0 = 1
    potencia x y = x * potencia x (y - 1)
    
  2. adicao x 0 = x
    adicao x y = adicao (maisUm x) (y - 1)
    
  3. log2 1 = 0
    log2 x = 1 + log2 (div x 2)
    

Recrusividade usando listas

editar
Exercício

Escrevas as seguintes funções de forma recursiva. Note que todas elas já possuem uma versão nativa no Prelude. Você pode usar dois casos base, caso ache necessário, apesar de que todos podem ser resolvidos com apenas um.

  1. replicar :: Int -> a -> [a], que recebe um contador n e um elemento, e retorna uma lista contendo n elementos iguais aos da entrada. Ex.: replicar 3 2 = [2,2,2]. A versão do Prelude chama-se replicate.
  2. (!!!) :: [a] -> Int -> a, que recebe uma lista e um índice de posição, e retorna o elemento contido em tal posição dentro da lista. O primeiro elemento da lista está na posição 0. Ex.: "abcde" !!! 2 = 'c'. A versão do Prelude chama-se (!!).
  3. ziper :: [a] -> [b] -> [(a,b)], que age como um ziper entre duas listas, isto é, pega um elemento de cada lista, forma uma dupla, e retorna uma lista de duplas. Ex.: ziper [1,2,3,4] "abc" = [(1, 'a'), (2, 'b'), (3, 'c')]. Perceba que a ação é interrompida quando o limite da lista mais curta é atingido. A versão do Prelude chama-se zip.
  4. Redefina length usando uma função interna auxiliar e um parâmetro acumulador.

  1. replicar :: Int -> a -> [a]
    replicar 0 _ = []
    replicar n x = x : replicar (n - 1) x
    
  2. (!!!) :: [a] -> Int -> a
    (x:xs) !!! 0 = x
    (x:xs) !!! n = xs !!! (n - 1)
    
  3. ziper :: [a] -> [b] -> [(a,b)]
    ziper []     _      = []
    ziper _      []     = []
    ziper (x:xs) (y:ys) = (x,y) : ziper xs ys
    
  4. minhaLength :: [t] -> Int
    minhaLength l = go l 0
      where go []     n = n
            go (x:xs) n = go xs (n+1)
    

Listas infinitas

editar
Exercício

Defina a função recursiva repetir :: a -> [a] que cria listas infinitas. O Prelude possui a repeat que realiza a mesma tarefa.

repetir :: a -> [a]
repetir x = x : repetir x


Generalizando

editar
Exercício

Escreva as seguintes funções e teste-as no GHCi. Não se esqueça das assinaturas de tipo.

  1. tomarInt retorna os primeiro n elementos de uma lista. Exemplo: tomarInt 4 [11,21,31,41,51,61] = [11,21,31,41].
  2. eliminarInt elemina os n primeiros elementos de uma lista e retorna o restante. Exemplo: eliminaInt 3 [11,21,31,41,51] = [41,51].
  3. somaInt retorna a soma dos elementos de uma lista.
  4. scanSoma soma os elementos de uma lista e retorna uma lista com valores acumulados. Exemplo: scanSoma [2,3,4,5] = [2,5,9,14].
  5. difs retorna a diferença entre elementos adjacentes de uma lista. Exemplo: difs [3,5,6,8] = [2,1,2].
Dica: possíveis soluções destes exercícios usam funções auxiliares. Outra possibilidade é usar casamento de padrões com listas de pelo menos dois elemtnso usando (x:y:ys). As três primeiras funções estão no Prelude e se chamam take, drop e sum.

  1. tomarInt :: Int -> [a] -> [a]
    tomarInt _ []     = []
    tomarInt 0 _      = []
    tomarInt n (x:xs) = x : tomarInt (n - 1) xs
    
  2. eliminarInt :: Int -> [a] -> [a]
    eliminarInt _ []     = []
    eliminarInt 0 xs     = xs
    eliminarInt n (x:xs) = eliminar (n - 1) xs
    
  3. somarInt :: [Int] -> Int
    somarInt []     = 0
    somarInt (x:xs) = x + somarInt xs
    
  4. scanSoma :: [Int] -> [Int]
    scanSoma []       = []
    scanSoma (x:[])   = x : []
    scanSoma (x:y:ys) = x : scanSoma ((x + y) : ys)
    
    -- Usando função auxiliar
    scanSoma' ls = aux 0 ls
      where aux :: Int -> [Int] -> [Int]
            aux tot []     = []
            aux tot (x:xs) = tot' : aux tot' xs
              where tot' = x + tot
    
  5. difs :: [Int] -> [Int]
    difs []       = []
    difs (x:[])   = []
    difs (x:y:ys) = (y - x) : difs (y:ys)
    
    -- Usando função auxiliar
    difs' :: [Int] -> [Int]
    difs' (x:xs) = aux (x:xs) xs
      where aux _      []     = []
            aux (a:as) (b:bs) = (b - a) : aux as bs
    
Exercícios
  1. Defina as seguintes funções recursivas, e depois escreva uma definição usando foldr ou foldl:
    • eListas :: [Bool] -> Bool, que retorna True se uma lista de Bools contiver apenas True, ou False, caso contrário.
    • ouListas :: [Bool] -> Bool, que retorna True se pelo menos um elemento de uma lista de Bools for verdadeiro, ou False, caso contrário.
  2. Defina as seguintes funções usando foldl1 ou foldr1:
    • maximo :: Ord a => [a] -> a, que retorna o elemento de maior valor de uma lista. Use a função max :: Ord a => a -> a -> a, que retorna seu argumento de maior valor.
    • minimo :: Ord a => [a] -> a, que retorna o elemento de menor valor de uma lista. Use a função min :: Ord a => a -> a -> a, que retorna seu argumento de menor valor.
  3. Use uma função fold (qual?) para definir inverter :: [a] -> [a], a qual inverte a ordem dos elementos de uma lista.
As funções do Prelude and, or, maximum e minimum correspondem às quatro primeiras funções destes exercícios, respectivamente.
  1. -- Versão recursiva
    eListas :: [Bool] -> Bool
    eListas []     = True
    eListas (x:xs) = x && eListas xs
    
    -- Usando foldr
    eListas' :: [Bool] -> Bool
    eListas' ls = foldr (&&) True ls
    
    -- Versão recursiva
    ouListas [Bool] -> Bool
    ouListas []     = False
    ouListas (x:xs) = x || ouListas xs
    
    -- Usando foldr
    ouListas' :: [Bool] -> Bool
    ouListas' ls = foldr (||) False ls
    
  2. maximo :: Ord a => [a] -> a
    maximo = foldl1 max
    
    minimo :: Ord a => [a] -> a
    minimo = foldl1 min
    
  3. inverter :: [a] -> [a]
    inverter ls = foldl consInvertido [] ls
      where consInvertido xs x = x : xs
    
Exercícios
  1. Escreva sua própria definição de scanr: primeiro, use recusrividade, e depois use foldr. Faça o mesmo para scanl.
  2. Defina a função fatLista :: Integer -> [Integer], que retorna uma lista dos fatoriais de 1 até o valor de seu argumento. Por exemplo: fatLista 4 = [1,2,6,24].
  1. -- Versão recursiva
    scanR :: (a -> b -> b) -> b -> [a] -> [b]
    scanR f acum []     = [acum]
    scanR f acum (x:xs) = f x (head ant) : ant
      where ant = scanR f acum xs
    
    -- Usando foldr
    scanR' :: (a -> b -> b) -> b -> [a] -> [b]
    scanR' f acum []     = [acum]
    scanR' f acum (x:xs) = foldr f acum (x:xs) : scanR' f acum xs
    
    ---------------------------------
    --Versão recursiva
    scanL :: (b -> a -> b) -> b -> [a] -> [b]
    scanL f acum []     = [acum]
    scanL f acum (x:xs) = acum : scanL f (f acum x) xs
    
    -- Usando foldl
    scanL' :: (b -> a -> b) -> b -> [a] -> [b]
    scanL' f acum [] = [acum]
    scanL' f acum ls = (scanL' f acum (init ls)) ++ [foldl f acum ls]
    
    Vale notar que a scanL' (usando foldl) é menos eficiente que scanL (versão recursiva).
  2. fatLista :: Int -> [Int]
    fatLista n = scanl (*) 1 [2..n]
    

Compreensão de listas

editar
Exercícios
  1. Escreva a função retornaDivisiveis :: Int -> [Int] -> [Int] que filtra uma lista de inteiros e retorna apenas os elementos que são divisíveis pelo seu primeiro argumento. Dica: x é divisível por n se mod x n == 0.
  2. Escreva a função selecionaCaudas :: [[Int]] -> [[Int]] usando compreensão de listas. Ela deve retornar a cauda das listas cujas cabeças são maiores que 5, e deve eliminar listas vazias:
    selecionaCaudas [[7,6,3],[],[6,4,2],[9,4,3],[5,5,5]] = [[6,3],[4,2],[4,3]]
  3. A ordem das condições altera o resultado da função? Descubra usando as funções que você acabou de escrever.
  4. Vimos que compreensão de listas são combinações de filter e map, mas agora você deve fazer o caminho inverso: defina mapear e filtrar usando compreensão de listas.
  5. Reescreva fstComSndPar usando filter e map em vez de compreensão de listas.
  1. retornaDivisiveis :: Int -> [Int] -> [Int]
    retornaDivisiveis n xs = [x | x <- xs, mod x n == 0]
    
  2. selecionaCaudas :: [[Int]] -> [[Int]]
    selecionaCaudas ls = [xs | (x:xs) <- ls, x > 5]
    
  3. Sim, a ordem importa. Todas as condições devem ser satisfeitas na ordem em que aparecem na compreensão: se tivermos cinco condições e segunda for falsa, a terceira, a quarta e a quinta não serão avaliadas.
  4. mapear :: (a -> b) -> [a] -> [b]
    mapear f xs = [f x | x <- xs]
    
    filtrar :: (a -> Bool) -> [a] -> [a]
    filtrar f xs = [x | x <- xs, f x]
    
  5. fstComSndPar :: [(Int, Int)] -> [Int]
    fstComSndPar ls = (map fst . filter faux) ls
      where faux (x,y) = ePar y
    
Exercícios

Observe a função mostrarData. Ela existe apenas para deixar mais clara a definição mostrarAniversario. Note que são passados três argumentos a ela: um ano, um mês e um dia, representados por Ints. Sabemos que não faz sentido passar os argumentos fora de ordem pois são parte de uma data única. Poderíamos, portanto, criar um tipo Data para armazenar apenas datas e evitar confusões:

  • Declare um tipo Data que armazene três Ints para representar ano, mês e dia.
  • Reescreva o tipo Aniversario usando Data.
  • Reescreva as funções mostrarData e mostrarAniversario usando as novas declarações de Data e Aniversario.
  • Redefina joaoRomao e romaoCasamento.
data Data = Data Int Int Int                    -- ano, mês, dia
data Aniversario = Nascimento String Data       -- nome, data
                 | Casamento String String Data -- nome 1, nome 2, Data

mostrarData :: Data -> String
mostrarData (Data a d m) = show a ++ "-" ++ show m ++ "-" ++ show d

mostrarAniversario :: Aniversario -> String
mostrarAniversario (Nascimento n d) =
    n ++ " nasceu em " ++ mostrarData d
mostrarAniversario (Casamento n1 n2 d) =
    n1 ++ " casou-se com " ++ n2 ++ " em " ++ mostrarData d

joaoRomao :: Aniversario
joaoRomao = Nascimento "João Romão" (Data 1968 7 3)

romaoCasamento :: Aniversario
romaoCasamento = Casamento "João Romão" "Maria Romão" (Data 1987 3 4)


Exercícios
Reescreva a declarção de Aniversario usando o sinônimo Nome, e mantendo o uso de Data.
type Nome = String
data Data = Data Int Int Int                -- ano, mês, dia
data Aniversario = Nascimento Nome Data     -- nome, data
                 | Casamento Nome Nome Data -- nome 1, nome 2, Data


Exercícios
  1. Reescreva a função mostrarData usando a declaração de Data na forma de registro e usando suas funções de acesso.
  2. Trantado-se de registros e dentro de um mesmo módulo, por que dois campos, de dois tipos diferentes, não podem ter o mesmo nome?
  1. data Data = Data {ano :: Int, mes :: Int, dia :: Int}
    
    mostrarData :: Data -> String
    mostrarData d = show (ano d) ++ "-" ++ show (mes d) ++ "-" ++ show (dia d)
    
  2. Cada campo torna-se uma função de acesso. Sendo estas funções realacionadas as tipos distintos, suas assinaturas de tipos serão diferentes para cada caso. Entretanto, Haskell não permite que uma função tenha mais que uma assinatura de tipo. Em outras palavras, é impossível ter campo1 :: Dado1 -> Int e campo1 :: Dado2 -> Int no mesmo lugar, por exemplo.
Exercícios

Reescreva as seguintes expressões usando lambdas:

  • map f xs where f x = x * 2 + 3
  • let f x y = read x + y in foldr f 1 xs
  • map (\x -> x * 2 + 3) xs
    
  • foldr (\x y -> read x + y) 1 xs
    
Exercício

  1. Seções são açúcar sintático para expressões lambdas. Reescreva as seguintes seções na forma de lambdas determine seus tipos:
    1. (4+)
    2. (1 `elem`)
    3. (`notElem` "abc")
  2. Teste as seguintes linhas no GHCi:
norma3D  x y z = sqrt (x^2 + y^2 + z^2)
norma3D' a b   = a `norma3D` b
Se a notação infixa só pode ser usada com funções de dois argumentos, por que a definição de norma3D' é válida? Os resultados de norma3D e norma3D' serão sempre iguais? Dica: observe os tipos de cada uma das funções e lembre-se de currying.

    1. (\x  -> 4 + x)           :: (Num a) => a -> a
      
    2. (\xs -> elem 1 xs)       :: [a] -> Bool
      
    3. (\c  -> notElem c "abc") :: Char -> Bool
      
  1. A função norma3D possui três argumentos, portanto seu tipo é da forma a -> a -> a -> a. Como temos o efeito de currying, podemos considerar que norma3D tem dois argumentos se pensarmos seu tipo como sendo a -> a -> (a -> a), isto é, uma função de dois argumentos que retorna uma função de um argumento. Assim sendo, se usarmos a notação de ponto livre, isto é, omitindo o terceiro argumento, forçamos o currying e podemos usar a notação infixa. Portanto, nomra3D' a b é, repetindo, uma função de dois argumentos que retorna uma função de um argumento, sendo que podemos usá-la com três argumentos, pois (f m) n == f m n. Também é fácil ver que os resultados serão sempre iguais se expandirmos a aplicação de norma3D':
(norma3D' a b) c
(a `norma3D` b) c
(norma3D a b) c
norma3D a b c
Exercícios
Teste a primeira versão de h no GHCi. O que acontece? Dê um exemplo em que ela retorne False.

Qualquer valor aplicado a h sempre retorna True. A definição de h é:

h :: Int -> Bool
h k = True
h _ = False

No primeiro caso, o padrão definido como k casa com qualquer valor de entrada. Portanto, o primeiro caso será sempre verdadeiro, o que faz com que h sempre retorne True. Assim sendo, não há nenhum valor que faça h retornar False.