# Exercícios MT1

Exercícios de Haskell, com escolha múltipla, respostas guardadas neste navegador e testes de programação.

Página: https://resumos.rgo.pt/cadeiras/pfl/exercicios-mt1/

## Expressões, tipos e funções

Combinar dois geradores

Qual o resultado de executar o seguinte código?

```
[(x,y) | x <- "abc", y <- [1,2]]
```

Solução

Cada letra do primeiro gerador combina com os dois números, nessa ordem.

*   **a. `[('a',1), ('b',1), ('c',1), ('a',2), ('b',1), ('c',2)]`.** Esta alternativa não corresponde ao pedido. Cada letra do primeiro gerador combina com os dois números, nessa ordem.
*   **b. `[('a',1), ('b',2), ('a',1), ('b',2), ('a',1), ('b',2)]`.** Esta alternativa não corresponde ao pedido. Cada letra do primeiro gerador combina com os dois números, nessa ordem.
*   **c. `[('c',1), ('c',2), ('b',1), ('b',2), ('a',1), ('a',2)]`.** Esta alternativa não corresponde ao pedido. Cada letra do primeiro gerador combina com os dois números, nessa ordem.
*   **d. `[('a',1), ('a',2), ('b',1), ('b',2), ('c',1), ('c',2)]`.** Cada letra do primeiro gerador combina com os dois números, nessa ordem.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#geradores-e-condi%C3%A7%C3%B5es)

Tipo de uma comparação mapeada

Qual dos tipos é válido para a seguinte expressão?

```
(map (>0))
```

Solução

O tipo principal é (Num a, Ord a) => \[a\] -> \[Bool\]. Int é uma especialização válida.

*   **a. `[Int] -> [Bool]`.** O tipo principal é (Num a, Ord a) => \[a\] -> \[Bool\]. Int é uma especialização válida.
*   **b. `[Char] -> [Bool]`.** Esta alternativa não corresponde ao pedido. O tipo principal é (Num a, Ord a) => \[a\] -> \[Bool\]. Int é uma especialização válida.
*   **c. `(Num a) => [a] -> Bool`.** Esta alternativa não corresponde ao pedido. O tipo principal é (Num a, Ord a) => \[a\] -> \[Bool\]. Int é uma especialização válida.
*   **d. `(Num a) => [a] -> [Bool]`.** Esta alternativa não corresponde ao pedido. O tipo principal é (Num a, Ord a) => \[a\] -> \[Bool\]. Int é uma especialização válida.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/polimorfismo-classes/#opera%C3%A7%C3%B5es-acrescentam-restri%C3%A7%C3%B5es)

Tipo do último elemento

Qual o tipo inferido pelo ghci para a seguinte função?

```
last [x] = x
last (x:xs) = last xs
```

Solução

O resultado tem o tipo dos elementos. A função é parcial para a lista vazia.

*   **a. `[a] -> b`.** Esta alternativa não corresponde ao pedido. O resultado tem o tipo dos elementos. A função é parcial para a lista vazia.
*   **b. `[a] -> a`.** O resultado tem o tipo dos elementos. A função é parcial para a lista vazia.
*   **c. `(Num a) => [a] -> a`.** Esta alternativa não corresponde ao pedido. O resultado tem o tipo dos elementos. A função é parcial para a lista vazia.
*   **d. `[Int] -> Int`.** Esta alternativa não corresponde ao pedido. O resultado tem o tipo dos elementos. A função é parcial para a lista vazia.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Somar com foldr e valor inicial

Qual o resultado de executar o seguinte código?

```
foldr (+) 7 [1,2,3]
```

Solução

A redução é 1 + (2 + (3 + 7)) = 13.

*   **a. `[13]`.** Esta alternativa não corresponde ao pedido. A redução é 1 + (2 + (3 + 7)) = 13.
*   **b. `6`.** Esta alternativa não corresponde ao pedido. A redução é 1 + (2 + (3 + 7)) = 13.
*   **c. `7`.** Esta alternativa não corresponde ao pedido. A redução é 1 + (2 + (3 + 7)) = 13.
*   **d. `13`.** A redução é 1 + (2 + (3 + 7)) = 13.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/funcoes-ordem-superior/#map-filter-e-foldr)

Sinónimos e novos tipos

Considere as três afirmações seguintes sobre as diferenças entre `type` e `data`: A - Apenas `data` permite definições recursivas de tipos. B - Apenas `data` permite definições usando variáveis de tipo (type variables). C - Apenas `data` define novos padrões para pattern matching. Qual/Quais destas afirmações estão corretas?

Solução

type aceita variáveis, mas não sinónimos recursivos. data introduz construtores para padrões.

*   **a. Apenas B e C.** Esta alternativa não corresponde ao pedido. type aceita variáveis, mas não sinónimos recursivos. data introduz construtores para padrões.
*   **b. A, B e C.** Esta alternativa não corresponde ao pedido. type aceita variáveis, mas não sinónimos recursivos. data introduz construtores para padrões.
*   **c. Apenas A e B.** Esta alternativa não corresponde ao pedido. type aceita variáveis, mas não sinónimos recursivos. data introduz construtores para padrões.
*   **d. Apenas A e C.** type aceita variáveis, mas não sinónimos recursivos. data introduz construtores para padrões.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/tipos-algebricos-recursao/#data-e-padr%C3%B5es)

Cabeça de uma lista de listas

Qual dos tipos é válido para a seguinte expressão?

```
head [[1], [2,3], [4,5,6]]
```

Solução

O resultado é uma lista numérica; \[Int\] é uma especialização válida.

*   **a. `[Int]`.** O resultado é uma lista numérica; \[Int\] é uma especialização válida.
*   **b. `[a]`.** Esta alternativa não corresponde ao pedido. O resultado é uma lista numérica; \[Int\] é uma especialização válida.
*   **c. `[Char]`.** Esta alternativa não corresponde ao pedido. O resultado é uma lista numérica; \[Int\] é uma especialização válida.
*   **d. `[String]`.** Esta alternativa não corresponde ao pedido. O resultado é uma lista numérica; \[Int\] é uma especialização válida.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/polimorfismo-classes/#n%C3%BAmeros-e-convers%C3%B5es)

Remover a cabeça de uma lista invertida

Qual o resultado de executar o seguinte código?

```
tail (reverse [1,2,3])
```

Solução

reverse produz \[3,2,1\], e tail remove o primeiro elemento.

*   **a. `[2,3]`.** Esta alternativa não corresponde ao pedido. reverse produz \[3,2,1\], e tail remove o primeiro elemento.
*   **b. `[2,1]`.** reverse produz \[3,2,1\], e tail remove o primeiro elemento.
*   **c. `[1,2]`.** Esta alternativa não corresponde ao pedido. reverse produz \[3,2,1\], e tail remove o primeiro elemento.
*   **d. `1`.** Esta alternativa não corresponde ao pedido. reverse produz \[3,2,1\], e tail remove o primeiro elemento.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Filtrar pares pelo produto

Qual o resultado de executar o seguinte código?

```
[(x,y) | (x,y) <- [(1,2),(2,3)], x*y==6]
```

Solução

Só o par (2,3) satisfaz o predicado, e o resultado é uma lista.

*   **a. `[(2,3)]`.** Só o par (2,3) satisfaz o predicado, e o resultado é uma lista.
*   **b. `[2,3]`.** Esta alternativa não corresponde ao pedido. Só o par (2,3) satisfaz o predicado, e o resultado é uma lista.
*   **c. `[(3,3)]`.** Esta alternativa não corresponde ao pedido. Só o par (2,3) satisfaz o predicado, e o resultado é uma lista.
*   **d. `(2,3)`.** Esta alternativa não corresponde ao pedido. Só o par (2,3) satisfaz o predicado, e o resultado é uma lista.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#geradores-e-condi%C3%A7%C3%B5es)

Repetir uma lista infinita

Qual o resultado de executar o seguinte código?

```
cycle (cycle [1,2,3])
```

Nota: `cycle` é uma função do Prelúdio-padrão que produz uma lista infinita em que a lista de input é repetida um número infinito de vezes. Exemplo: `cycle [1,2,3] = [1,2,3,1,2,3, …]`

Solução

A lista interior é infinita, por isso a repetição exterior nunca chega ao seu fim.

*   **a. `[1,1,1,1,1,1 …]`.** Esta alternativa não corresponde ao pedido. A lista interior é infinita, por isso a repetição exterior nunca chega ao seu fim.
*   **b. O cálculo da expressão gera um erro..** Esta alternativa não corresponde ao pedido. A lista interior é infinita, por isso a repetição exterior nunca chega ao seu fim.
*   **c. `[1,2,3,1,2,3, …]`.** A lista interior é infinita, por isso a repetição exterior nunca chega ao seu fim.
*   **d. `[1,1,2,2,3,3,1,1,2,2,3,3, …]`.** Esta alternativa não corresponde ao pedido. A lista interior é infinita, por isso a repetição exterior nunca chega ao seu fim.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/funcoes-ordem-superior/#listas-infinitas-e-pregui%C3%A7a)

Emparelhar elementos consecutivos

Qual o resultado de executar o seguinte código?

```
head (zip [1..10] (tail [1..10]))
```

Solução

zip emparelha os primeiros elementos, 1 e 2.

*   **a. `(1,10)`.** Esta alternativa não corresponde ao pedido. zip emparelha os primeiros elementos, 1 e 2.
*   **b. `(1,1)`.** Esta alternativa não corresponde ao pedido. zip emparelha os primeiros elementos, 1 e 2.
*   **c. `(2,1)`.** Esta alternativa não corresponde ao pedido. zip emparelha os primeiros elementos, 1 e 2.
*   **d. `(1,2)`.** zip emparelha os primeiros elementos, 1 e 2.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#relacionar-posi%C3%A7%C3%B5es-com-zip)

Árvores com valores nos nós

Qual das seguintes alternativas define um tipo de árvores binárias com anotações apenas nos nós?

Solução

Folha não tem anotação; No tem um valor e duas subárvores.

*   **a. `data Arv a = Folha | No a (Arv a) (Arv a)`.** Folha não tem anotação; No tem um valor e duas subárvores.
*   **b. `data Arv a = Folha a | No a (Arv a) (Arv a)`.** Esta alternativa não corresponde ao pedido. Folha não tem anotação; No tem um valor e duas subárvores.
*   **c. `data Arv a = Folha a | No (Arv a) (Arv a)`.** Esta alternativa não corresponde ao pedido. Folha não tem anotação; No tem um valor e duas subárvores.
*   **d. `data Arv = Folha | No Arv Arv`.** Esta alternativa não corresponde ao pedido. Folha não tem anotação; No tem um valor e duas subárvores.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/tipos-algebricos-recursao/#data-e-padr%C3%B5es)

Remover um carácter de uma string

Qual o resultado de executar o seguinte código?

```
filter (/='a') "abba"
```

Solução

O predicado conserva os caracteres diferentes de a.

*   **a. `"ab"`.** Esta alternativa não corresponde ao pedido. O predicado conserva os caracteres diferentes de a.
*   **b. `""`.** Esta alternativa não corresponde ao pedido. O predicado conserva os caracteres diferentes de a.
*   **c. `"bb"`.** O predicado conserva os caracteres diferentes de a.
*   **d. `"aa"`.** Esta alternativa não corresponde ao pedido. O predicado conserva os caracteres diferentes de a.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/funcoes-ordem-superior/#map-filter-e-foldr)

## Listas, avaliação e efeitos

Tipo de um par ordenado

Qual é o tipo da função seguinte?

```
orderedPair (a, b)
   | a <= b = (a, b)
   | otherwise = (b, a)
```

Solução

A comparação exige Ord e ambos os elementos têm o mesmo tipo.

*   **a. `(Num a, Num b) => (a, b) -> (b, a)`.** Esta alternativa não corresponde ao pedido. A comparação exige Ord e ambos os elementos têm o mesmo tipo.
*   **b. `(Ord a) => (a, a) -> (a, a)`.** A comparação exige Ord e ambos os elementos têm o mesmo tipo.
*   **c. `(Num a, Num b) => (a, b) -> (a, b)`.** Esta alternativa não corresponde ao pedido. A comparação exige Ord e ambos os elementos têm o mesmo tipo.
*   **d. `(Ord a, Ord b) => (a, b) -> (b, a)`.** Esta alternativa não corresponde ao pedido. A comparação exige Ord e ambos os elementos têm o mesmo tipo.
*   **e. `(Num a, Ord a, Num b, Ord b) => (a, b) -> (b, a)`.** Esta alternativa não corresponde ao pedido. A comparação exige Ord e ambos os elementos têm o mesmo tipo.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/polimorfismo-classes/#opera%C3%A7%C3%B5es-acrescentam-restri%C3%A7%C3%B5es)

Contar valores positivos por composição

Qual é o resultado da expressão?

```
(length . (filter (> 0))) [1, 2, -3, 4, -5]
```

Solução

filter conserva 1, 2 e 4; length conta três.

*   **a. `0`.** Esta alternativa não corresponde ao pedido. filter conserva 1, 2 e 4; length conta três.
*   **b. The evaluation of the expression produces an error..** Esta alternativa não corresponde ao pedido. filter conserva 1, 2 e 4; length conta três.
*   **c. `3`.** filter conserva 1, 2 e 4; length conta três.
*   **d. `1`.** Esta alternativa não corresponde ao pedido. filter conserva 1, 2 e 4; length conta três.
*   **e. `2`.** Esta alternativa não corresponde ao pedido. filter conserva 1, 2 e 4; length conta três.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/funcoes-ordem-superior/#map-filter-e-foldr)

Lista de funções sobre listas

Qual é o tipo da expressão?

```
[(++) [], map (+1)]
```

Solução

Ambas as funções transformam listas do mesmo tipo numérico, pelo uso de (+1).

*   **a. `[[a] -> [a]]`.** Esta alternativa não corresponde ao pedido. Ambas as funções transformam listas do mesmo tipo numérico, pelo uso de (+1).
*   **b. `(Num a) => [a]`.** Esta alternativa não corresponde ao pedido. Ambas as funções transformam listas do mesmo tipo numérico, pelo uso de (+1).
*   **c. `(Num a, Num b) => [[a] -> [b]]`.** Esta alternativa não corresponde ao pedido. Ambas as funções transformam listas do mesmo tipo numérico, pelo uso de (+1).
*   **d. `[[a] -> [b]]`.** Esta alternativa não corresponde ao pedido. Ambas as funções transformam listas do mesmo tipo numérico, pelo uso de (+1).
*   **e. `(Num a) => [[a] -> [a]]`.** Ambas as funções transformam listas do mesmo tipo numérico, pelo uso de (+1).

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/polimorfismo-classes/#opera%C3%A7%C3%B5es-acrescentam-restri%C3%A7%C3%B5es)

Tipo de uma função sobre triplos

Qual é o tipo da função?

```
fun (x, y, _) = (y, x, y)
fun (_, y, x) = (y, x, y)
```

Solução

A segunda equação é inacessível, mas também é verificada: a primeira e a terceira posições têm de ter o mesmo tipo.

*   **a. `(a, a, a) -> (a, a, a)`.** Esta alternativa não corresponde ao pedido. A segunda equação é inacessível, mas também é verificada: a primeira e a terceira posições têm de ter o mesmo tipo.
*   **b. `(a, b, c) -> (a, b, c)`.** Esta alternativa não corresponde ao pedido. A segunda equação é inacessível, mas também é verificada: a primeira e a terceira posições têm de ter o mesmo tipo.
*   **c. `(a, b, a) -> (b, a, b)`.** A segunda equação é inacessível, mas também é verificada: a primeira e a terceira posições têm de ter o mesmo tipo.
*   **d. `(a, b, c) -> (d, e, f)`.** Esta alternativa não corresponde ao pedido. A segunda equação é inacessível, mas também é verificada: a primeira e a terceira posições têm de ter o mesmo tipo.
*   **e. `(a, a, a) -> (b, b, b)`.** Esta alternativa não corresponde ao pedido. A segunda equação é inacessível, mas também é verificada: a primeira e a terceira posições têm de ter o mesmo tipo.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/polimorfismo-classes/#deduzir-um-tipo-passo-a-passo)

Combinar letras e números

Qual é o resultado da expressão?

```
[(a, b) | a <- "abc", b <- [1, 2], a <= 'd']
```

Solução

A condição é verdadeira para as três letras e o segundo gerador varia primeiro.

*   **a. `[('a',1), ('b',1), ('c',1), ('a',2), ('b',2), ('c',2)]`.** Esta alternativa não corresponde ao pedido. A condição é verdadeira para as três letras e o segundo gerador varia primeiro.
*   **b. `[('a',1), ('a',2), ('b',1), ('b',2), ('c',1), ('c',2)]`.** A condição é verdadeira para as três letras e o segundo gerador varia primeiro.
*   **c. The evaluation of the expression produces an error..** Esta alternativa não corresponde ao pedido. A condição é verdadeira para as três letras e o segundo gerador varia primeiro.
*   **d. `[('a',1), ('b',1), ('c',1)]`.** Esta alternativa não corresponde ao pedido. A condição é verdadeira para as três letras e o segundo gerador varia primeiro.
*   **e. `[]`.** Esta alternativa não corresponde ao pedido. A condição é verdadeira para as três letras e o segundo gerador varia primeiro.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#geradores-e-condi%C3%A7%C3%B5es)

Dividir com foldl

Qual é o resultado da expressão?

```
foldl (/) 200 [1, 2, 4]
```

Solução

A associação à esquerda dá ((200 / 1) / 2) / 4 = 25.0.

*   **a. 50.0.** Esta alternativa não corresponde ao pedido. A associação à esquerda dá ((200 / 1) / 2) / 4 = 25.0.
*   **b. The evaluation of the expression produces an error..** Esta alternativa não corresponde ao pedido. A associação à esquerda dá ((200 / 1) / 2) / 4 = 25.0.
*   **c. 25.0.** A associação à esquerda dá ((200 / 1) / 2) / 4 = 25.0.
*   **d. 100.0.** Esta alternativa não corresponde ao pedido. A associação à esquerda dá ((200 / 1) / 2) / 4 = 25.0.
*   **e. 1.0e-2.** Esta alternativa não corresponde ao pedido. A associação à esquerda dá ((200 / 1) / 2) / 4 = 25.0.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/funcoes-ordem-superior/#foldr-contra-foldl)

Resultados das funções do Prelude

Qual das funções do Prelude não devolve necessariamente uma lista?

Solução

(!!) seleciona um elemento, cujo tipo não tem de ser uma lista.

*   **a. `(++)`.** Esta alternativa não corresponde ao pedido. (!!) seleciona um elemento, cujo tipo não tem de ser uma lista.
*   **b. `(:)`.** Esta alternativa não corresponde ao pedido. (!!) seleciona um elemento, cujo tipo não tem de ser uma lista.
*   **c. zip.** Esta alternativa não corresponde ao pedido. (!!) seleciona um elemento, cujo tipo não tem de ser uma lista.
*   **d. init.** Esta alternativa não corresponde ao pedido. (!!) seleciona um elemento, cujo tipo não tem de ser uma lista.
*   **e. `(!!)`.** (!!) seleciona um elemento, cujo tipo não tem de ser uma lista.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Variáveis de tipo, recursão e instâncias

Considera as seguintes afirmações sobre type e data. Quais estão corretas?

A - `type` does not allow the use of type variables, unlike `data`. B - `type` does not allow recursive type definitions. C - It is possible to define an instance of Eq using `data`.

Solução

type aceita variáveis, mas não sinónimos recursivos. data permite definir uma instância de Eq.

*   **a. Only B and C..** type aceita variáveis, mas não sinónimos recursivos. data permite definir uma instância de Eq.
*   **b. Only A and B..** Esta alternativa não corresponde ao pedido. type aceita variáveis, mas não sinónimos recursivos. data permite definir uma instância de Eq.
*   **c. Only A and C..** Esta alternativa não corresponde ao pedido. type aceita variáveis, mas não sinónimos recursivos. data permite definir uma instância de Eq.
*   **d. Only B..** Esta alternativa não corresponde ao pedido. type aceita variáveis, mas não sinónimos recursivos. data permite definir uma instância de Eq.
*   **e. A, B and C..** Esta alternativa não corresponde ao pedido. type aceita variáveis, mas não sinónimos recursivos. data permite definir uma instância de Eq.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/tipos-algebricos-recursao/#data-e-padr%C3%B5es)

Reconhecer mónadas

Entre Maybe, State e IO, quais são mónadas?

Solução

Maybe, IO e State são mónadas, com o parâmetro de estado de State fixado.

*   **a. Maybe, State and IO..** Maybe, IO e State são mónadas, com o parâmetro de estado de State fixado.
*   **b. Only Maybe and IO..** Esta alternativa não corresponde ao pedido. Maybe, IO e State são mónadas, com o parâmetro de estado de State fixado.
*   **c. Only State and IO..** Esta alternativa não corresponde ao pedido. Maybe, IO e State são mónadas, com o parâmetro de estado de State fixado.
*   **d. Only IO..** Esta alternativa não corresponde ao pedido. Maybe, IO e State são mónadas, com o parâmetro de estado de State fixado.
*   **e. None of these types is a monad..** Esta alternativa não corresponde ao pedido. Maybe, IO e State são mónadas, com o parâmetro de estado de State fixado.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/entrada-saida-parsers/#sequenciar-a%C3%A7%C3%B5es-sem-confundir-valores)

Tipo de uma saudação com IO

Qual é o tipo da função seguinte?

```
howdy name = putStrLn ("howdy " ++ name ++ "!")
```

Solução

putStrLn devolve uma ação IO (), pelo que a função recebe String e devolve IO ().

*   **a. String -> IO ().** putStrLn devolve uma ação IO (), pelo que a função recebe String e devolve IO ().
*   **b. String -> String.** Esta alternativa não corresponde ao pedido. putStrLn devolve uma ação IO (), pelo que a função recebe String e devolve IO ().
*   **c. IO ().** Esta alternativa não corresponde ao pedido. putStrLn devolve uma ação IO (), pelo que a função recebe String e devolve IO ().
*   **d. IO (String).** Esta alternativa não corresponde ao pedido. putStrLn devolve uma ação IO (), pelo que a função recebe String e devolve IO ().
*   **e. String -> IO (String).** Esta alternativa não corresponde ao pedido. putStrLn devolve uma ação IO (), pelo que a função recebe String e devolve IO ().

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/entrada-saida-parsers/#io-com-do)

Avaliação preguiçosa e listas infinitas

A avaliação preguiçosa de Haskell permite o quê?

Solução

A avaliação preguiçosa permite obter resultados finitos sem avaliar uma estrutura infinita inteira.

*   **a. the automatic inference of the functions’ type..** Esta alternativa não corresponde ao pedido. A avaliação preguiçosa permite obter resultados finitos sem avaliar uma estrutura infinita inteira.
*   **b. the optimization of the memory consumption of a program, in exchange for an increased execution time..** Esta alternativa não corresponde ao pedido. A avaliação preguiçosa permite obter resultados finitos sem avaliar uma estrutura infinita inteira.
*   **c. the definition of polymorphic functions..** Esta alternativa não corresponde ao pedido. A avaliação preguiçosa permite obter resultados finitos sem avaliar uma estrutura infinita inteira.
*   **d. certain computations with infinite data structures to be finite..** A avaliação preguiçosa permite obter resultados finitos sem avaliar uma estrutura infinita inteira.
*   **e. the definition of higher-order functions..** Esta alternativa não corresponde ao pedido. A avaliação preguiçosa permite obter resultados finitos sem avaliar uma estrutura infinita inteira.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/funcoes-ordem-superior/#o-que-a-pregui%C3%A7a-permite)

Representar um dendrograma

Um dendrograma é uma árvore binária cujos caminhos chegam a strings. Cada nó não folha indica a distância horizontal igual aos dois filhos. Qual é a definição mais adequada?

5533dogcatoctopus

Cada nó interno guarda uma distância comum aos seus dois filhos.

Solução

Cada folha guarda uma String e cada nó guarda duas subárvores e uma distância comum.

*   **a. `data Dendrogram = Leaf String | Node Int Int Dendrogram`.** Esta alternativa não corresponde ao pedido. Cada folha guarda uma String e cada nó guarda duas subárvores e uma distância comum.
*   **b. `(Integral a) => data Dendrogram = Leaf (String, a) | Node Dendrogram Dendrogram`.** Esta alternativa não corresponde ao pedido. Cada folha guarda uma String e cada nó guarda duas subárvores e uma distância comum.
*   **c. `data Dendrogram = Leaf (String, Int) | Node Dendrogram Dendrogram`.** Esta alternativa não corresponde ao pedido. Cada folha guarda uma String e cada nó guarda duas subárvores e uma distância comum.
*   **d. `(Integral a) => data Dendrogram = Leaf String | Node Dendrogram a a Dendrogram`.** Esta alternativa não corresponde ao pedido. Cada folha guarda uma String e cada nó guarda duas subárvores e uma distância comum.
*   **e. `data Dendrogram = Leaf String | Node Dendrogram Int Dendrogram`.** Cada folha guarda uma String e cada nó guarda duas subárvores e uma distância comum.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/tipos-algebricos-recursao/#data-e-padr%C3%B5es)

## Composição e avaliação

Custo da concatenação de listas

Ordena por tempo de avaliação, começando pela mais rápida. Para tornar a comparação determinada, considera apenas o custo de percorrer o argumento esquerdo de `(++)` para produzir a lista inteira, sem contar a construção das listas.

```
a = [1 .. 100000] ++ (take 1000 [1 .. 100000])
b = (take 1000 [1 .. 100000]) ++ [1 .. 100000]
c = (takeWhile (>1000) [1 .. 100000]) ++ [1 .. 100000]
```

Solução

O argumento esquerdo de (++) tem zero elementos em c, 1000 em b e 100000 em a. No modelo indicado, a ordem é c < b < a.

*   **a. `a = b = c`.** No modelo pedido, (++) percorre a lista à esquerda: c começa com \[\], b com 1000 elementos e a com 100000. O tempo real depende do contexto de avaliação.
*   **b. `b < c < a`.** No modelo pedido, (++) percorre a lista à esquerda: c começa com \[\], b com 1000 elementos e a com 100000. O tempo real depende do contexto de avaliação.
*   **c. `c < a = b`.** No modelo pedido, (++) percorre a lista à esquerda: c começa com \[\], b com 1000 elementos e a com 100000. O tempo real depende do contexto de avaliação.
*   **d. `c < b < a`.** No modelo pedido, (++) percorre a lista à esquerda: c começa com \[\], b com 1000 elementos e a com 100000. O tempo real depende do contexto de avaliação.
*   **e. `c < a < b`.** No modelo pedido, (++) percorre a lista à esquerda: c começa com \[\], b com 1000 elementos e a com 100000. O tempo real depende do contexto de avaliação.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/funcoes-ordem-superior/#map-filter-e-foldr)

Intercalar caracteres com zip e concat

Qual é o resultado?

```
concat [[a,b] | (a,b) <- zip ['a' ..] "abcde"]
```

Solução

zip termina com a segunda lista; concat junta os pares de caracteres numa string.

*   **a. `["abcde,"abcde,"abcde","abcde","abcde"]`.** Esta alternativa não corresponde ao pedido. zip termina com a segunda lista; concat junta os pares de caracteres numa string.
*   **b. `["aa","bb","cc","dd","ee"]`.** Esta alternativa não corresponde ao pedido. zip termina com a segunda lista; concat junta os pares de caracteres numa string.
*   **c. `[('a','a'),('b','b'),('c','c'),('d','d'),('e','e')]`.** Esta alternativa não corresponde ao pedido. zip termina com a segunda lista; concat junta os pares de caracteres numa string.
*   **d. `"abcdeabcde"`.** Esta alternativa não corresponde ao pedido. zip termina com a segunda lista; concat junta os pares de caracteres numa string.
*   **e. `"aabbccddee"`.** zip termina com a segunda lista; concat junta os pares de caracteres numa string.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/funcoes-ordem-superior/#map-filter-e-foldr)

Multiplicar sequências com zipWith

Qual é o resultado?

```
zipWith (*) [1 ..] [3,1 .. -5]
```

Solução

A segunda lista é \[3,1,-1,-3,-5\], e zipWith termina no seu fim.

*   **a. `[3,2,-3,-12,-25]`.** A segunda lista é \[3,1,-1,-3,-5\], e zipWith termina no seu fim.
*   **b. Nenhuma das outras opções..** Esta alternativa não corresponde ao pedido. A segunda lista é \[3,1,-1,-3,-5\], e zipWith termina no seu fim.
*   **c. `[]`.** Esta alternativa não corresponde ao pedido. A segunda lista é \[3,1,-1,-3,-5\], e zipWith termina no seu fim.
*   **d. Uma lista infinita.** Esta alternativa não corresponde ao pedido. A segunda lista é \[3,1,-1,-3,-5\], e zipWith termina no seu fim.
*   **e. `[-3,-2,3,12,25]`.** Esta alternativa não corresponde ao pedido. A segunda lista é \[3,1,-1,-3,-5\], e zipWith termina no seu fim.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/funcoes-ordem-superior/#map-filter-e-foldr)

Reconhecer uma propriedade sobre listas

Que expressão tem o tipo (Eq a) => \[a\] -> Bool?

Solução

Comparar a lista com a sua inversa exige Eq e produz Bool.

*   **a. `(\(_:t) -> tail t)`.** Esta alternativa não corresponde ao pedido. Comparar a lista com a sua inversa exige Eq e produz Bool.
*   **b. map (<3).** Esta alternativa não corresponde ao pedido. Comparar a lista com a sua inversa exige Eq e produz Bool.
*   **c. filter (==3).** Esta alternativa não corresponde ao pedido. Comparar a lista com a sua inversa exige Eq e produz Bool.
*   **d. tail.** Esta alternativa não corresponde ao pedido. Comparar a lista com a sua inversa exige Eq e produz Bool.
*   **e. `(\l -> reverse l == l)`.** Comparar a lista com a sua inversa exige Eq e produz Bool.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/funcoes-ordem-superior/#map-filter-e-foldr)

Tipo de uma comparação de quocientes

Qual é o tipo de myFun?

```
myFun x y = (x / y) < 1
```

Solução

O tipo principal é (Fractional a, Ord a) => a -> a -> Bool, que não figura nas opções.

*   **a. `(Num a, Ord a) => a -> a -> Bool`.** Esta alternativa não corresponde ao pedido. O tipo principal é (Fractional a, Ord a) => a -> a -> Bool, que não figura nas opções.
*   **b. Nenhuma das outras opções..** O tipo principal é (Fractional a, Ord a) => a -> a -> Bool, que não figura nas opções.
*   **c. `(Floating a) => a -> a -> Bool`.** Esta alternativa não corresponde ao pedido. O tipo principal é (Fractional a, Ord a) => a -> a -> Bool, que não figura nas opções.
*   **d. `(Floating a, Ord a) => a -> b -> Bool`.** Esta alternativa não corresponde ao pedido. O tipo principal é (Fractional a, Ord a) => a -> a -> Bool, que não figura nas opções.
*   **e. `(Fractional a, Ord a) => a -> b -> Bool`.** Esta alternativa não corresponde ao pedido. O tipo principal é (Fractional a, Ord a) => a -> a -> Bool, que não figura nas opções.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/funcoes-ordem-superior/#map-filter-e-foldr)

Produto de positivos com Maybe

Qual das afirmações é falsa? A opção a contém o lapso `Integral` em vez do tipo `Integer`; para responder, aplica a errata indicada.

```
f [] = Just 1
f (h:t)
  | h > 0 = case f t of Just d -> Just (h*d)
                        _ -> Nothing
  | otherwise = Nothing
```

Solução

A primeira guarda falha para 0 e o resultado imediato é Nothing. Integral é uma classe, não um tipo concreto.

*   **a. Os elementos podem ter tipo Int, Integral e Float, entre outros tipos válidos. \[Errata: lê Integer no lugar de Integral.\].** Esta alternativa não corresponde ao pedido. A primeira guarda falha para 0 e o resultado imediato é Nothing. Integral é uma classe, não um tipo concreto.
*   **b. Se uma entrada devolver Nothing, a sua inversa também devolve Nothing..** Esta alternativa não corresponde ao pedido. A primeira guarda falha para 0 e o resultado imediato é Nothing. Integral é uma classe, não um tipo concreto.
*   **c. O tipo é (Num a, Ord a) => \[a\] -> Maybe a..** Esta alternativa não corresponde ao pedido. A primeira guarda falha para 0 e o resultado imediato é Nothing. Integral é uma classe, não um tipo concreto.
*   **d. f \[0 ..\] termina e devolve Just 0..** A primeira guarda falha para 0 e o resultado imediato é Nothing. Integral é uma classe, não um tipo concreto.
*   **e. f \[1,2,3,4\] devolve Just 24..** Esta alternativa não corresponde ao pedido. A primeira guarda falha para 0 e o resultado imediato é Nothing. Integral é uma classe, não um tipo concreto.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/funcoes-ordem-superior/#map-filter-e-foldr)

Reconhecer uma função definida com foldr

Qual a função do Prelude equivalente?

```
mysteryFunc = foldr (++) []
```

Solução

foldr (++) \[\] concatena as listas pela ordem original.

*   **a. reverse.** Esta alternativa não corresponde ao pedido. foldr (++) \[\] concatena as listas pela ordem original.
*   **b. `(:)`.** Esta alternativa não corresponde ao pedido. foldr (++) \[\] concatena as listas pela ordem original.
*   **c. concat.** foldr (++) \[\] concatena as listas pela ordem original.
*   **d. length.** Esta alternativa não corresponde ao pedido. foldr (++) \[\] concatena as listas pela ordem original.
*   **e. tail.** Esta alternativa não corresponde ao pedido. foldr (++) \[\] concatena as listas pela ordem original.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/funcoes-ordem-superior/#map-filter-e-foldr)

Tipo de uma função de ordem superior

Qual é o tipo da função?

```
fun f g x y = f (g x y) (f x x)
```

Solução

f x x força f a receber e devolver a; g recebe a e b e devolve a.

*   **a. `(a -> a -> b) -> (a -> a -> a) -> a -> b -> a`.** Esta alternativa não corresponde ao pedido. f x x força f a receber e devolver a; g recebe a e b e devolve a.
*   **b. `(a -> a -> c) -> (a -> b -> a) -> a -> b -> c`.** Esta alternativa não corresponde ao pedido. f x x força f a receber e devolver a; g recebe a e b e devolve a.
*   **c. `(a -> a -> a) -> (a -> b -> a) -> a -> b -> a`.** f x x força f a receber e devolver a; g recebe a e b e devolve a.
*   **d. Nenhuma das outras opções..** Esta alternativa não corresponde ao pedido. f x x força f a receber e devolver a; g recebe a e b e devolve a.
*   **e. `(a -> a -> b) -> (a -> b -> a) -> a -> b -> b`.** Esta alternativa não corresponde ao pedido. f x x força f a receber e devolver a; g recebe a e b e devolve a.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/funcoes-ordem-superior/#map-filter-e-foldr)

Compor transformações antes de foldl

Qual é o resultado?

```
foldl (-) 2 (map ((+1).(*2)) [3,2,1])
```

Solução

map produz \[7,5,3\]; a redução é ((2-7)-5)-3 = -13.

*   **a. -13.** map produz \[7,5,3\]; a redução é ((2-7)-5)-3 = -13.
*   **b. `4`.** Esta alternativa não corresponde ao pedido. map produz \[7,5,3\]; a redução é ((2-7)-5)-3 = -13.
*   **c. Nenhuma das outras opções..** Esta alternativa não corresponde ao pedido. map produz \[7,5,3\]; a redução é ((2-7)-5)-3 = -13.
*   **d. `3`.** Esta alternativa não corresponde ao pedido. map produz \[7,5,3\]; a redução é ((2-7)-5)-3 = -13.
*   **e. -16.** Esta alternativa não corresponde ao pedido. map produz \[7,5,3\]; a redução é ((2-7)-5)-3 = -13.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/funcoes-ordem-superior/#map-filter-e-foldr)

Leitura recursiva de caracteres

O que faz `g`? As cinco opções originais descrevem impressão, mas o código só devolve um valor. A opção f foi acrescentada para permitir uma resposta tecnicamente correta.

```
g = gAux []

gAux a = do
  x <- getChar
  if (x == '\n')
    then return a
    else gAux (x:a)
```

Solução

O código lê até à mudança de linha e devolve a linha invertida em IO String. Não contém uma ação de impressão.

*   **a. Lê um carácter e imprime-o depois de lhe acrescentar uma mudança de linha..** getChar lê até à mudança de linha; (x:a) acumula em ordem inversa e return devolve a string em IO. Não há putStr nem putStrLn.
*   **b. Lê várias linhas e imprime-as em ordem inversa..** getChar lê até à mudança de linha; (x:a) acumula em ordem inversa e return devolve a string em IO. Não há putStr nem putStrLn.
*   **c. Lê uma linha e imprime-a exatamente como foi escrita..** getChar lê até à mudança de linha; (x:a) acumula em ordem inversa e return devolve a string em IO. Não há putStr nem putStrLn.
*   **d. Lê uma linha e imprime-a em ordem inversa..** getChar lê até à mudança de linha; (x:a) acumula em ordem inversa e return devolve a string em IO. Não há putStr nem putStrLn.
*   **e. Lê várias linhas e imprime-as exatamente como foram escritas..** getChar lê até à mudança de linha; (x:a) acumula em ordem inversa e return devolve a string em IO. Não há putStr nem putStrLn.
*   **f. Lê uma linha e devolve-a invertida, sem a imprimir..** getChar lê até à mudança de linha; (x:a) acumula em ordem inversa e return devolve a string em IO. Não há putStr nem putStrLn.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/funcoes-ordem-superior/#map-filter-e-foldr)

## Ligas, percursos e árvores

Não uses funções de biblioteca nem importes módulos, salvo indicação explícita. Podes usar as funções fornecidas no código inicial. Os testes verificam o resultado, não o método.

Determinar o vencedor de uma partida

You cannot use library functions or import modules, unless clearly stated otherwise.

Uma liga é uma sequência de jornadas. Cada equipa joga uma partida por jornada; cada partida contém as equipas da casa e visitante e os respetivos golos. Por exemplo, `(("Porto","Benfica"),(5,0))` representa uma vitória do Porto por 5–0. As definições e os exemplos da liga estão no código inicial.

Implement `winner :: Match -> String`, which, given a match, returns the name of the match's winner or "draw" in case both teams scored the same number of goals.

Examples:

```
ghci> winner (("Porto","Benfica"),(5,0))
"Porto"
ghci> winner (("Porto","Sporting"),(2,2))
"draw"
```

```haskell
type Match = ((String,String), (Int,Int))
type MatchDay = [Match]
type League = [MatchDay]
myLeague :: League
myLeague = [[(("Porto","Sporting"),(2,2)),(("Benfica","Vitoria SC"),(4,0))],
  [(("Porto","Benfica"),(5,0)),(("Vitoria SC","Sporting"),(3,2))],
  [(("Vitoria SC","Porto"),(1,2)),(("Sporting","Benfica"),(2,1))]]
winner :: Match -> String
winner = undefined
```



### Testes

**Casa**


```haskell
main = print (winner (("Porto","Benfica"),(5,0)))
```


Saída esperada:

```text
"Porto"
```

**Empate**


```haskell
main = print (winner (("Porto","Sporting"),(2,2)))
```


Saída esperada:

```text
"draw"
```

**Fora**


```haskell
main = print (winner (("A","B"),(0,3)))
```


Saída esperada:

```text
"B"
```

Solução

```
winner ((h,a),(x,y)) | x > y = h | x < y = a | otherwise = "draw"
```

Compara os golos das duas equipas; a igualdade é empate.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Pontuação de uma equipa numa jornada

You cannot use library functions or import modules, unless clearly stated otherwise.

Uma liga é uma sequência de jornadas. Cada equipa joga uma partida por jornada; cada partida contém as equipas da casa e visitante e os respetivos golos. Por exemplo, `(("Porto","Benfica"),(5,0))` representa uma vitória do Porto por 5–0. As definições e os exemplos da liga estão no código inicial.

Implement `matchDayScore :: String -> MatchDay -> Int`, which, given a team and a matchday, returns the score obtained by that team on their match of that matchday. Winning a match gives a team 3 points, drawing gives 1 point and losing gives 0 points. If the input team does not exist in the league, then return 0.

Examples:

```
ghci> matchDayScore "Porto" (myLeague !! 0)
1
ghci> matchDayScore "Benfica" (myLeague !! 0)
3
ghci> matchDayScore "Vitoria SC" (myLeague !! 0)
0
```

```haskell
type Match = ((String,String), (Int,Int))
type MatchDay = [Match]
type League = [MatchDay]
myLeague :: League
myLeague = [[(("Porto","Sporting"),(2,2)),(("Benfica","Vitoria SC"),(4,0))],
  [(("Porto","Benfica"),(5,0)),(("Vitoria SC","Sporting"),(3,2))],
  [(("Vitoria SC","Porto"),(1,2)),(("Sporting","Benfica"),(2,1))]]
matchDayScore :: String -> MatchDay -> Int
matchDayScore = undefined
```



### Testes

**Empate**


```haskell
main = print (matchDayScore "Porto" (myLeague !! 0))
```


Saída esperada:

```text
1
```

**Vitória**


```haskell
main = print (matchDayScore "Benfica" (myLeague !! 0))
```


Saída esperada:

```text
3
```

**Derrota**


```haskell
main = print (matchDayScore "Vitoria SC" (myLeague !! 0))
```


Saída esperada:

```text
0
```

**Ausente**


```haskell
main = print (matchDayScore "X" [])
```


Saída esperada:

```text
0
```

Solução

```
matchDayScore _ [] = 0
matchDayScore t (((h,a),(x,y)):ms)
  | t == h = if x > y then 3 else if x == y then 1 else 0
  | t == a = if y > x then 3 else if x == y then 1 else 0
  | otherwise = matchDayScore t ms
```

Procura o jogo da equipa e compara os golos na orientação correta.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Classificação de uma liga

You cannot use library functions or import modules, unless clearly stated otherwise.

Uma liga é uma sequência de jornadas. Cada equipa joga uma partida por jornada; cada partida contém as equipas da casa e visitante e os respetivos golos. Por exemplo, `(("Porto","Benfica"),(5,0))` representa uma vitória do Porto por 5–0. As definições e os exemplos da liga estão no código inicial.

Podes usar `leagueScore`, `sortByCond` e `merge`, fornecidas no código inicial.

Implement `ranking:: League -> [(String,Int)]`, which returns a list of pairs (team,score) with the score obtained by each team during the league. The league score is the sum of the points obtained by the team in each matchday. The output list must be ordered by the scores, in decreasing order. In case of a tie in the scores, return the team name that comes first alphabetically.

Examples:

```
ghci> ranking myLeague
[("Porto",7),("Sporting",4),("Benfica",3),("Vitoria SC",3)]
ghci> ranking (tail myLeague)
[("Porto",6),("Sporting",3),("Vitoria SC",3),("Benfica",0)]
ghci> ranking []
[]
```

```haskell
type Match = ((String,String), (Int,Int))
type MatchDay = [Match]
type League = [MatchDay]
myLeague :: League
myLeague = [[(("Porto","Sporting"),(2,2)),(("Benfica","Vitoria SC"),(4,0))],
  [(("Porto","Benfica"),(5,0)),(("Vitoria SC","Sporting"),(3,2))],
  [(("Vitoria SC","Porto"),(1,2)),(("Sporting","Benfica"),(2,1))]]
matchDayScore :: String -> MatchDay -> Int
matchDayScore _ [] = 0
matchDayScore t (((h,a),(x,y)):ms)
  | t == h = if x > y then 3 else if x == y then 1 else 0
  | t == a = if y > x then 3 else if x == y then 1 else 0
  | otherwise = matchDayScore t ms
leagueScore :: String -> League -> Int
leagueScore t = foldr (\d acc -> matchDayScore t d + acc) 0
sortByCond :: Ord a => [a] -> (a -> a -> Bool) -> [a]
sortByCond [] _ = []
sortByCond [x] _ = [x]
sortByCond l cmp = merge (sortByCond l1 cmp) (sortByCond l2 cmp) cmp
  where (l1,l2) = splitAt (div (length l) 2) l
merge :: Ord a => [a] -> [a] -> (a -> a -> Bool) -> [a]
merge [] l _ = l
merge l [] _ = l
merge (x:xs) (y:ys) cmp
  | cmp x y = x : merge xs (y:ys) cmp
  | otherwise = y : merge (x:xs) ys cmp
ranking :: League -> [(String,Int)]
ranking = undefined
```



### Testes

**Liga**


```haskell
main = print (ranking myLeague)
```


Saída esperada:

```text
[("Porto",7),("Sporting",4),("Benfica",3),("Vitoria SC",3)]
```

**Cauda**


```haskell
main = print (ranking (tail myLeague))
```


Saída esperada:

```text
[("Porto",6),("Sporting",3),("Vitoria SC",3),("Benfica",0)]
```

**Vazia**


```haskell
main = print (ranking [])
```


Saída esperada:

```text
[]
```

Solução

```
unique [] = []
unique (x:xs) = x : unique [y | y <- xs, y /= x]
ranking l = sortByCond [(t,leagueScore t l) | t <- unique [t | d <- l, ((h,a),_) <- d, t <- [h,a]]] cmp
  where cmp (a,x) (b,y) = x > y || (x == y && a < b)
```

Recolhe cada equipa uma vez e ordena por pontos decrescentes, usando o nome para desempatar.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Contar jornadas com empates

You cannot use library functions or import modules, unless clearly stated otherwise.

Uma liga é uma sequência de jornadas. Cada equipa joga uma partida por jornada; cada partida contém as equipas da casa e visitante e os respetivos golos. Por exemplo, `(("Porto","Benfica"),(5,0))` representa uma vitória do Porto por 5–0. As definições e os exemplos da liga estão no código inicial.

Implement `numMatchDaysWithDraws :: League -> Int`, which returns the amount of matchdays in the league where at least one match ended in a draw. Constraint: in this exercise, you must use higher-order functions. You are not allowed to define new recursive functions or use list comprehensions.

Examples:

```
ghci> numMatchDaysWithDraws myLeague
1
```

```haskell
type Match = ((String,String), (Int,Int))
type MatchDay = [Match]
type League = [MatchDay]
myLeague :: League
myLeague = [[(("Porto","Sporting"),(2,2)),(("Benfica","Vitoria SC"),(4,0))],
  [(("Porto","Benfica"),(5,0)),(("Vitoria SC","Sporting"),(3,2))],
  [(("Vitoria SC","Porto"),(1,2)),(("Sporting","Benfica"),(2,1))]]
winner :: Match -> String
winner ((h,a),(x,y)) | x > y = h | x < y = a | otherwise = "draw"
numMatchDaysWithDraws :: League -> Int
numMatchDaysWithDraws = undefined
```



### Testes

**Liga**


```haskell
main = print (numMatchDaysWithDraws myLeague)
```


Saída esperada:

```text
1
```

**Vazia**


```haskell
main = print (numMatchDaysWithDraws [])
```


Saída esperada:

```text
0
```

**Dois empates**


```haskell
main = print (numMatchDaysWithDraws [[(("A","B"),(0,0)),(("C","D"),(1,1))]])
```


Saída esperada:

```text
1
```

Solução

```
numMatchDaysWithDraws = length . filter (any ((== "draw") . winner))
```

Conta cada jornada que contém pelo menos um empate.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Identificar vitórias por goleada

You cannot use library functions or import modules, unless clearly stated otherwise.

Uma liga é uma sequência de jornadas. Cada equipa joga uma partida por jornada; cada partida contém as equipas da casa e visitante e os respetivos golos. Por exemplo, `(("Porto","Benfica"),(5,0))` representa uma vitória do Porto por 5–0. As definições e os exemplos da liga estão no código inicial.

Implement `bigWins :: League -> [(Int,[String])]`, which returns a list of pairs (i,ws), where i is the index of the matchday (with indices starting at 1) and ws are the names of teams from that matchday that won their match with a goal difference of at least 3 goals. Any order of the winners ws of each matchday will be accepted. Constraint: in this exercise, you must use list comprehensions. You are not allowed to define new recursive functions or use higher-order functions (map, filter, foldl ...).

Examples:

```
ghci> bigWins myLeague
[(1,["Benfica"]),(2,["Porto"]),(3,[])]
```

```haskell
type Match = ((String,String), (Int,Int))
type MatchDay = [Match]
type League = [MatchDay]
myLeague :: League
myLeague = [[(("Porto","Sporting"),(2,2)),(("Benfica","Vitoria SC"),(4,0))],
  [(("Porto","Benfica"),(5,0)),(("Vitoria SC","Sporting"),(3,2))],
  [(("Vitoria SC","Porto"),(1,2)),(("Sporting","Benfica"),(2,1))]]
winner :: Match -> String
winner ((h,a),(x,y)) | x > y = h | x < y = a | otherwise = "draw"
bigWins :: League -> [(Int,[String])]
bigWins = undefined
```



### Testes

**Liga**


```haskell
main = print (bigWins myLeague)
```


Saída esperada:

```text
[(1,["Benfica"]),(2,["Porto"]),(3,[])]
```

**Vazia**


```haskell
main = print (bigWins [])
```


Saída esperada:

```text
[]
```

**Limite**


```haskell
main = print (bigWins [[(("A","B"),(0,3))]])
```


Saída esperada:

```text
[(1,["B"])]
```

Solução

```
bigWins l = [(i,[winner m | m@(_, (x,y)) <- d, abs (x-y) >= 3]) | (i,d) <- zip [1..] l]
```

A compreensão exterior conserva todas as jornadas; a interior seleciona diferenças de pelo menos três golos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Encontrar séries de vitórias

You cannot use library functions or import modules, unless clearly stated otherwise.

Uma liga é uma sequência de jornadas. Cada equipa joga uma partida por jornada; cada partida contém as equipas da casa e visitante e os respetivos golos. Por exemplo, `(("Porto","Benfica"),(5,0))` representa uma vitória do Porto por 5–0. As definições e os exemplos da liga estão no código inicial.

Implement `winningStreaks :: League -> [(String,Int,Int)]`, which returns a list of winning streaks, described by a triple (t,s,e), where: t is the name of the team involved in the winning streak; s and e are the indices of the streak's first and last matchday (with indices starting at 1). A winning streak is a sequence of wins in 2 or more consecutive matchdays. Note that the same team may have more than one winning streak and thus appear multiple times in the output. Any order of the output list will be accepted.

Examples:

```
ghci> winningStreaks myLeague
[("Porto",2,3)]
ghci> winningStreaks [[(("RM","Barca"),(4,0))],[(("Barca","RM"),(1,2))],[(("RM","Barca"),(2,2))],[(("RM","Barca"),
(0,4))],[(("Barca","RM"),(3,0))],[(("Barca","RM"),(3,1))]]
[("RM",1,2),("Barca",4,6)]
```

```haskell
type Match = ((String,String), (Int,Int))
type MatchDay = [Match]
type League = [MatchDay]
myLeague :: League
myLeague = [[(("Porto","Sporting"),(2,2)),(("Benfica","Vitoria SC"),(4,0))],
  [(("Porto","Benfica"),(5,0)),(("Vitoria SC","Sporting"),(3,2))],
  [(("Vitoria SC","Porto"),(1,2)),(("Sporting","Benfica"),(2,1))]]
winner :: Match -> String
winner ((h,a),(x,y)) | x > y = h | x < y = a | otherwise = "draw"
winningStreaks :: League -> [(String,Int,Int)]
winningStreaks = undefined
```



### Testes

**Liga**


```haskell
main = print (winningStreaks myLeague)
```


Saída esperada:

```text
[("Porto",2,3)]
```

**Vazia**


```haskell
main = print (winningStreaks [])
```


Saída esperada:

```text
[]
```

**Duas equipas**


```haskell
main = print (let r = winningStreaks [[(("RM","Barca"),(4,0))],[(("Barca","RM"),(1,2))],[(("RM","Barca"),(2,2))],[(("RM","Barca"),(0,4))],[(("Barca","RM"),(3,0))],[(("Barca","RM"),(3,1))]] in (elem ("RM",1,2) r, elem ("Barca",4,6) r, length r))
```


Saída esperada:

```text
(True,True,2)
```

Solução

```
unique [] = []
unique (x:xs) = x : unique [y | y <- xs, y /= x]
runs t [] = []
runs t (i:is) = extend t i i is
extend t s e (i:is) | i == e+1 = extend t s i is
extend t s e rest = (if e > s then [(t,s,e)] else []) ++ runs t rest
winningStreaks l = concat [runs t [i | (i,d) <- zip [1..] l, m <- d, winner m == t] | t <- unique [t | d <- l, ((h,a),_) <- d, t <- [h,a]]]
```

Agrupa, para cada equipa, índices consecutivos de vitórias e descarta grupos de uma só jornada.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Cidades adjacentes e distâncias

You cannot use library functions or import modules, unless clearly stated otherwise.

`RoadMap` representa estradas não orientadas entre cidades, com as respetivas distâncias. Os mapas de exemplo estão no código inicial; `gTest2` é desconexo.

Implement `adjacent :: RoadMap -> City ->[(City,Distance)]`, which returns the cities adjacent to a particular city (i.e. cities with a direct edge between them) and the respective distances to them. Any order of the output list will be accepted. Note that a city is NOT adjacent to itself.

Examples:

```
ghci> adjacent gTest1 "0"
[("1",10),("2",15),("3",20)]
ghci> adjacent gTest2 "0"
[("1",4)]
```

```haskell
type City = String
type Path = [City]
type Distance = Int
type RoadMap = [(City,City,Distance)]
gTest1 :: RoadMap
gTest1 = [("0","1",10),("0","2",15),("0","3",20),("1","2",35),("1","3",25),("2","3",30)]
gTest2 :: RoadMap
gTest2 = [("0","1",4),("2","3",2)]
adjacent :: RoadMap -> City -> [(City,Distance)]
adjacent = undefined
```



### Testes

**Mapa**


```haskell
main = print (let r = adjacent gTest1 "0" in (length r, elem ("1",10) r, elem ("2",15) r, elem ("3",20) r))
```


Saída esperada:

```text
(3,True,True,True)
```

**Desconexo**


```haskell
main = print (adjacent gTest2 "0")
```


Saída esperada:

```text
[("1",4)]
```

**Laço**


```haskell
main = print (adjacent [("A","A",1)] "A")
```


Saída esperada:

```text
[]
```

Solução

```
adjacent rs c = [(b,d) | (a,b,d) <- rs, a == c, b /= c] ++ [(a,d) | (a,b,d) <- rs, b == c, a /= c]
```

Percorre as estradas nos dois sentidos e exclui laços.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Verificar ligações entre cidades

You cannot use library functions or import modules, unless clearly stated otherwise.

`RoadMap` representa estradas não orientadas entre cidades, com as respetivas distâncias. Os mapas de exemplo estão no código inicial; `gTest2` é desconexo.

Implement `areConnected :: RoadMap -> City -> City -> Bool`, which determines if there is a path, composed of one or more roads, connecting both input cities of the input roadmap. Consider that a city is connected to itself.

Examples:

```
ghci> areConnected gTest1 "0" "3"
True
ghci> areConnected gTest2 "0" "3"
False
```

```haskell
type City = String
type Path = [City]
type Distance = Int
type RoadMap = [(City,City,Distance)]
gTest1 :: RoadMap
gTest1 = [("0","1",10),("0","2",15),("0","3",20),("1","2",35),("1","3",25),("2","3",30)]
gTest2 :: RoadMap
gTest2 = [("0","1",4),("2","3",2)]
adjacent :: RoadMap -> City -> [(City,Distance)]
adjacent rs c = [(b,d) | (a,b,d) <- rs, a == c, b /= c] ++ [(a,d) | (a,b,d) <- rs, b == c, a /= c]
areConnected :: RoadMap -> City -> City -> Bool
areConnected = undefined
```



### Testes

**Ligadas**


```haskell
main = print (areConnected gTest1 "0" "3")
```


Saída esperada:

```text
True
```

**Desligadas**


```haskell
main = print (areConnected gTest2 "0" "3")
```


Saída esperada:

```text
False
```

**Mesma**


```haskell
main = print (areConnected [] "X" "X")
```


Saída esperada:

```text
True
```

**Ciclo**


```haskell
main = print (areConnected [("A","B",1),("B","C",1),("C","A",1)] "A" "Z")
```


Saída esperada:

```text
False
```

Solução

```
areConnected roads start end = search [] [start]
  where
    search _ [] = False
    search seen (c:cs)
      | c == end = True
      | c `elem` seen = search seen cs
      | otherwise = search (c:seen) (map fst (adjacent roads c) ++ cs)
```

A pesquisa guarda cidades visitadas para terminar mesmo com ciclos. A cidade inicial está ligada a si própria.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Inserir um ponto numa KD-tree

You cannot use library functions or import modules, unless clearly stated otherwise.

Uma KD-tree guarda pontos distintos. A raiz não vazia é um nó X e os níveis alternam entre X e Y. À esquerda ficam pontos com coordenada do eixo estritamente inferior; à direita, igual ou superior. Pontos distintos podem partilhar uma coordenada. As árvores de exemplo estão no código inicial.

Implement `insert :: (Int,Int) -> KdTree -> KdTree`, which given a point p and a tree t, returns a new tree with the result of adding p to t. Point p should be added on the appropriate leaf node (Empty), according to the rules of the kd-tree stated before. If point p is already in the tree, then return t.

Examples:

```
ghci> insert (3,2) tree1
Node 'x' (3,3) (Node 'y' (2,2) Empty Empty) (Node 'y' (4,4) (Node 'x' (3,2) Empty Empty) Empty)
ghci> insert (1,1) (insert (3,2) tree1)
Node 'x' (3,3) (Node 'y' (2,2) (Node 'x' (1,1) Empty Empty) Empty) (Node 'y' (4,4) (Node 'x' (3,2) Empty Empty) Empty)
```

```haskell
data KdTree = Empty | Node Char (Int,Int) KdTree KdTree deriving (Eq,Show)
tree1 :: KdTree
tree1 = Node 'x' (3,3) (Node 'y' (2,2) Empty Empty) (Node 'y' (4,4) Empty Empty)
tree2 :: KdTree
tree2 = Node 'x' (3,3) (Node 'y' (2,2) (Node 'x' (1,1) Empty Empty) Empty) (Node 'y' (4,4) (Node 'x' (3,2) Empty Empty) Empty)
insert :: (Int,Int) -> KdTree -> KdTree
insert = undefined
```



### Testes

**Raiz**


```haskell
main = print (insert (1,2) Empty)
```


Saída esperada:

```text
Node 'x' (1,2) Empty Empty
```

**Exemplo**


```haskell
main = print (insert (3,2) tree1)
```


Saída esperada:

```text
Node 'x' (3,3) (Node 'y' (2,2) Empty Empty) (Node 'y' (4,4) (Node 'x' (3,2) Empty Empty) Empty)
```

**Duplicado**


```haskell
main = print (insert (3,2) tree2)
```


Saída esperada:

```text
Node 'x' (3,3) (Node 'y' (2,2) (Node 'x' (1,1) Empty Empty) Empty) (Node 'y' (4,4) (Node 'x' (3,2) Empty Empty) Empty)
```

Solução

```
insert p = go 'x'
  where
    go axis Empty = Node axis p Empty Empty
    go _ node@(Node a q left right)
      | p == q = node
      | coordinate a p < coordinate a q = Node a q (go (next a) left) right
      | otherwise = Node a q left (go (next a) right)
    coordinate 'x' (x,_) = x
    coordinate _ (_,y) = y
    next 'x' = 'y'
    next _ = 'x'
```

Coordenadas iguais seguem para a direita; o eixo alterna ao descer. Um ponto igual já existe.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Imprimir uma KD-tree com indentação

You cannot use library functions or import modules, unless clearly stated otherwise.

Uma KD-tree guarda pontos distintos. A raiz não vazia é um nó X e os níveis alternam entre X e Y. À esquerda ficam pontos com coordenada do eixo estritamente inferior; à direita, igual ou superior. Pontos distintos podem partilhar uma coordenada. As árvores de exemplo estão no código inicial.

Implement `putTreeStr :: KdTree -> IO ()`, which prints the contents of the tree in several lines, in a user-friendly manner. The output format must be exactly as detailed in the examples (including regarding the ' ' and newlines). Each tree is printed as follows: a line for the root's point; a line with the condition that all points of the left child must follow; the left child (if it exists); a line with the condition that all points of the right child must follow; the right child (if it exists). At each level of depth in tree, all of the prints must be prefixed by exactly two additional spaces: " ". Note that nothing should be printed for empty trees.

Examples:

```
ghci> putTreeStr Empty
ghci> putTreeStr tree1
(3,3)
x<3
  (2,2)
  y<2
  y>=2
x>=3
  (4,4)
  y<4
  y>=4
ghci> putTreeStr tree2
(3,3)
x<3
  (2,2)
  y<2
      (1,1)
      x<1
    x>=1
  y>=2
x>=3
  (4,4)
  y<4
      (3,2)
      x<3
    x>=3
  y>=4
```

```haskell
data KdTree = Empty | Node Char (Int,Int) KdTree KdTree deriving (Eq,Show)
tree1 :: KdTree
tree1 = Node 'x' (3,3) (Node 'y' (2,2) Empty Empty) (Node 'y' (4,4) Empty Empty)
tree2 :: KdTree
tree2 = Node 'x' (3,3) (Node 'y' (2,2) (Node 'x' (1,1) Empty Empty) Empty) (Node 'y' (4,4) (Node 'x' (3,2) Empty Empty) Empty)
putTreeStr :: KdTree -> IO ()
putTreeStr = undefined
```



### Testes

**Vazia**


```haskell
main = print =<< (putTreeStr Empty)
```


Saída esperada:

```text
()
```

**Um nó**


```haskell
main = print =<< (putTreeStr (Node 'x' (1,2) Empty Empty))
```


Saída esperada:

```text
(1,2)
x<1
x>=1
()
```

**Árvore**


```haskell
main = print =<< (putTreeStr tree1)
```


Saída esperada:

```text
(3,3)
x<3
  (2,2)
  y<2
  y>=2
x>=3
  (4,4)
  y<4
  y>=4
()
```

Solução

```
putTreeStr = go ""
  where
    go _ Empty = return ()
    go indent (Node axis p@(x,y) left right) = do
      putStrLn (indent ++ show p)
      let value = if axis == 'x' then x else y
      putStrLn (indent ++ [axis] ++ "<" ++ show value)
      go (indent ++ "  ") left
      putStrLn (indent ++ [axis] ++ ">=" ++ show value)
      go (indent ++ "  ") right
```

Imprime as condições mesmo quando a subárvore é vazia e acrescenta dois espaços por nível.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

## Catálogos, sequências e proposições

Procurar os atores de um filme

Cada `Movie` é um par com o título e uma lista ordenada de atores. Podes usar `delAll`, que remove todas as ocorrências, e `uniqueVals`, que remove repetidos mantendo a primeira ocorrência. Implemente `findActors :: [Movie] -> String -> Maybe [String]`. Devolva os atores do filme com o título indicado, ou `Nothing` se não existir.

```haskell
type Movie = (String, [String])
myMovies :: [Movie]
myMovies = [("Titanic",["Kate Winslet","Leonardo DiCaprio"]),("Revolutionary Road",["Kate Winslet","Leonardo DiCaprio"]),("Elektra ",["Jennifer Garner"]),("The Great Gatsby",["Leonardo DiCaprio"])]
delAll :: Eq a => a -> [a] -> [a]
delAll x = filter (/= x)
uniqueVals :: Eq a => [a] -> [a]
uniqueVals [] = []
uniqueVals (x:xs) = x : uniqueVals (delAll x xs)
findActors :: [Movie] -> String -> Maybe [String]
findActors = undefined
```



### Testes

**Existe**


```haskell
main = print (findActors [("A",["X","Y"])] "A")
```


Saída esperada:

```text
Just ["X","Y"]
```

**Ausente**


```haskell
main = print (findActors [] "A")
```


Saída esperada:

```text
Nothing
```

Solução

```
findActors movies title = lookup title movies
```

lookup title movies procura o primeiro par com esse título. A ausência é representada por Nothing.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Selecionar filmes por ator

Cada `Movie` é um par com o título e uma lista ordenada de atores. Podes usar `delAll`, que remove todas as ocorrências, e `uniqueVals`, que remove repetidos mantendo a primeira ocorrência. Implemente `moviesWithActor :: [Movie] -> String -> [Movie]`, preservando a ordem dos filmes em que o ator participou.

```haskell
type Movie = (String, [String])
myMovies :: [Movie]
myMovies = [("Titanic",["Kate Winslet","Leonardo DiCaprio"]),("Revolutionary Road",["Kate Winslet","Leonardo DiCaprio"]),("Elektra ",["Jennifer Garner"]),("The Great Gatsby",["Leonardo DiCaprio"])]
delAll :: Eq a => a -> [a] -> [a]
delAll x = filter (/= x)
uniqueVals :: Eq a => [a] -> [a]
uniqueVals [] = []
uniqueVals (x:xs) = x : uniqueVals (delAll x xs)
moviesWithActor :: [Movie] -> String -> [Movie]
moviesWithActor = undefined
```



### Testes

**Ordem**


```haskell
main = print (moviesWithActor [("A",["X"]),("B",[]),("C",["X"])] "X")
```


Saída esperada:

```text
[("A",["X"]),("C",["X"])]
```

**Vazia**


```haskell
main = print (moviesWithActor [] "X")
```


Saída esperada:

```text
[]
```

Solução

```
moviesWithActor movies actor = filter (elem actor . snd) movies
```

`filter` preserva a ordem dos filmes e `elem` verifica a participação do ator.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Reunir atores sem repetidos

Cada `Movie` é um par com o título e uma lista ordenada de atores. Podes usar `delAll`, que remove todas as ocorrências, e `uniqueVals`, que remove repetidos mantendo a primeira ocorrência. Implemente `uniqueActors :: [Movie] -> [String]`, sem repetidos e pela ordem da primeira ocorrência.

```haskell
type Movie = (String, [String])
myMovies :: [Movie]
myMovies = [("Titanic",["Kate Winslet","Leonardo DiCaprio"]),("Revolutionary Road",["Kate Winslet","Leonardo DiCaprio"]),("Elektra ",["Jennifer Garner"]),("The Great Gatsby",["Leonardo DiCaprio"])]
delAll :: Eq a => a -> [a] -> [a]
delAll x = filter (/= x)
uniqueVals :: Eq a => [a] -> [a]
uniqueVals [] = []
uniqueVals (x:xs) = x : uniqueVals (delAll x xs)
uniqueActors :: [Movie] -> [String]
uniqueActors = undefined
```



### Testes

**Repetidos**


```haskell
main = print (uniqueActors [("A",["X","Y"]),("B",["Y","Z"])])
```


Saída esperada:

```text
["X","Y","Z"]
```

**Vazia**


```haskell
main = print (uniqueActors [])
```


Saída esperada:

```text
[]
```

Solução

```
uniqueActors = uniqueVals . concatMap snd
```

`concatMap snd` concatena as listas de atores e `uniqueVals` remove as ocorrências posteriores.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Contar filmes por ator

Cada `Movie` é um par com o título e uma lista ordenada de atores. Podes usar `delAll`, que remove todas as ocorrências, e `uniqueVals`, que remove repetidos mantendo a primeira ocorrência. Implemente `actorFrequencies :: [Movie] -> [(String, Int)]`, contando filmes por ator e mantendo a ordem da primeira ocorrência, sem ordenar por frequência.

```haskell
type Movie = (String, [String])
myMovies :: [Movie]
myMovies = [("Titanic",["Kate Winslet","Leonardo DiCaprio"]),("Revolutionary Road",["Kate Winslet","Leonardo DiCaprio"]),("Elektra ",["Jennifer Garner"]),("The Great Gatsby",["Leonardo DiCaprio"])]
delAll :: Eq a => a -> [a] -> [a]
delAll x = filter (/= x)
uniqueVals :: Eq a => [a] -> [a]
uniqueVals [] = []
uniqueVals (x:xs) = x : uniqueVals (delAll x xs)
actorFrequencies :: [Movie] -> [(String, Int)]
actorFrequencies = undefined
```



### Testes

**Um filme conta uma vez**


```haskell
main = print (actorFrequencies [("A",["X","X","Y"]),("B",["Y"])])
```


Saída esperada:

```text
[("X",1),("Y",2)]
```

**Vazia**


```haskell
main = print (actorFrequencies [])
```


Saída esperada:

```text
[]
```

Solução

```
actorFrequencies ms = [(a, length [() | (_,as) <- ms, a `elem` as]) | a <- uniqueVals (concatMap snd ms)]
```

Para cada ator distinto, conta os filmes que o contêm; repetições no mesmo filme não acrescentam filmes. A contagem considera cada filme uma única vez.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Propriedades das classes de tipos

Qual das seguintes afirmações sobre typeclasses está errada?

Solução

Ord exige Eq como superclasse; a afirmação inversa está errada.

*   **`Ord é uma typeclass para tipos que suportam o operador <=.`.** `Ord` disponibiliza comparação ordenada.
*   **Eq é uma subclasse de Ord..** É `Ord` que exige `Eq` como superclasse, e não o inverso.
*   **Float faz parte da typeclass Fractional..** `Float` é instância de Fractional.
*   **Int faz parte da typeclass Integral..** `Int` é instância de `Integral`.
*   **Um tipo pode pertencer a três typeclasses diferentes..** Um tipo pode ser instância de várias classes.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Tipo de uma compreensão com índices

Indique um tipo possível para `[ (n, x, x !! n) | n <- ls ]`.

Solução

O índice de (!!) é Int e o resultado tem o tipo de um elemento da lista.

*   **`[(Int, [Char], [Char])]`.** Indexar \[`Char`\] devolve `Char`, não \[`Char`\].
*   **`([Int], [String], String)`.** A compreensão devolve uma lista de triplos.
*   **`[(Int, [Int], Int)]`.** O índice é `Int` e indexar \[`Int`\] devolve `Int`.
*   **`[(Int, String, String)]`.** Indexar `String` devolve `Char`, não `String`.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Contar elementos por decrementos

Reimplemente `funcX = foldl (\acc _ -> pred acc) 0` sem usar funções da família dos folds, incluindo `foldr`, `foldl`, `foldr1` e `scanr`.

```haskell
funcX :: [a] -> Int
funcX = undefined
```



### Testes

**Vazia**


```haskell
main = print (funcX ([] :: [Int]))
```


Saída esperada:

```text
0
```

**Três**


```haskell
main = print (funcX [1,2,3])
```


Saída esperada:

```text
-3
```

Solução

```
funcX [] = 0
funcX (_:xs) = pred (funcX xs)
```

Cada elemento decrementa uma vez; a lista vazia começa em zero.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Comparar elementos em posições pares

Usando `zip`, defina `evenPos` para duas listas possivelmente de comprimentos diferentes. Devolva pares de elementos diferentes nas mesmas posições pares, contadas a partir de zero. Exemplos: `evenPos [1,2,3,4,5] [5,4,3,2,1] = [(1,5),(5,1)]; evenPos "banana" "batata" = [('n','t'),('n','t')]`.

```haskell
evenPos :: Eq a => [a] -> [a] -> [(a,a)]
evenPos = undefined
```



### Testes

**Exemplo**


```haskell
main = print (evenPos [1,2,3,4,5] [5,4,3,2,1])
```


Saída esperada:

```text
[(1,5),(5,1)]
```

**Comprimentos**


```haskell
main = print (evenPos [1,2,3] [9])
```


Saída esperada:

```text
[(1,9)]
```

Solução

```
evenPos xs ys = [(x,y) | (i,(x,y)) <- zip [0..] (zip xs ys), even i, x /= y]
```

zip termina na lista mais curta; o índice seleciona posições pares e x /= y exclui valores iguais.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Gerar uma sequência por recorrência

Defina a lista infinita `list` para a₀ = 0, a₁ = 1, aₙ = 3 × aₙ₋₁ − 2 × aₙ₋₂ para n > 1. Segue a recorrência para calcular os termos.

```haskell
list :: [Integer]
list = undefined
```



### Testes

**Primeiros termos**


```haskell
main = print (take 6 list)
```


Saída esperada:

```text
[0,1,3,7,15,31]
```

**Prefixo vazio**


```haskell
main = print (take 0 list)
```


Saída esperada:

```text
[]
```

Solução

```
list = 0 : 1 : zipWith (\a b -> 3*b - 2*a) list (tail list)
```

A recorrência produz 0, 1, 3, 7, 15, 31. zipWith combina cada par de termos consecutivos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Avaliar proposições lógicas

Considere `data Prop = Const Bool | Neg Prop | Conj Prop Prop | Disj Prop Prop | Impl Prop Prop`. Defina recursivamente `valor :: Prop -> Bool` para calcular o valor lógico.

```haskell
data Prop = Const Bool | Neg Prop | Conj Prop Prop | Disj Prop Prop | Impl Prop Prop
valor :: Prop -> Bool
valor = undefined
```



### Testes

**Implicação falsa**


```haskell
main = print (valor (Impl (Const True) (Const False)))
```


Saída esperada:

```text
False
```

**Expressão**


```haskell
main = print (valor (Conj (Neg (Const False)) (Disj (Const False) (Const True))))
```


Saída esperada:

```text
True
```

Solução

```
valor (Const b) = b
valor (Neg p) = not (valor p)
valor (Conj p q) = valor p && valor q
valor (Disj p q) = valor p || valor q
valor (Impl p q) = not (valor p) || valor q
```

A avaliação segue os construtores. A implicação p → q equivale a não p ou q.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

## Recursão e transformação de estruturas

Tipo de uma função sobre pares

Considere `f (x:xs, y:ys) = (2*x+y) : f (xs, ys); f _ = []`. Qual é um tipo admissível?

Solução

A função recebe um par de listas e devolve uma lista de números.

*   **a. `([Float], [Float]) -> [Float]`.** A função recebe um par de listas e devolve uma lista de números.
*   **b. `([Float], [Float]) -> Float`.** A função recebe um par de listas e devolve uma lista de números.
*   **c. `[Float] -> [Float] -> [Float]`.** A função recebe um par de listas e devolve uma lista de números.
*   **d. `([Int] -> [Int]) -> [Int]`.** A função recebe um par de listas e devolve uma lista de números.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Representar listas

Qual das definições é isomorfa a `[Float]`?

Solução

Uma lista é vazia ou contém uma cabeça `Float` e outra lista.

*   **a. `data List = Empty | Cons Float List`.** Uma lista é vazia ou contém uma cabeça `Float` e outra lista.
*   **b. `data List = Last Float | Cons List List`.** Uma lista é vazia ou contém uma cabeça `Float` e outra lista.
*   **c. `data List = Empty | Cons Float Float`.** Uma lista é vazia ou contém uma cabeça `Float` e outra lista.
*   **d. `data List = Last Float | Cons Float List`.** Uma lista é vazia ou contém uma cabeça `Float` e outra lista.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Construir expressões

Considere `data Expr = Num Int | Add Expr Expr | Mul Expr Expr`. Qual representa `(1+2)*(3*4)`?

Solução

Cada operação recebe duas expressões e cada inteiro é embrulhado em `Num`.

*   **a. `Mul (Add 1) (Add 2) (Mul 3) (Mul 4)`.** Cada operação recebe duas expressões e cada inteiro é embrulhado em `Num`.
*   **b. `Mul (Add (Num 1) (Num 2)) (Num 3) (Num 4)`.** Cada operação recebe duas expressões e cada inteiro é embrulhado em `Num`.
*   **c. `Mul (Mul (Num 1) (Num 2)) (Add (Num 3) (Num 4))`.** Cada operação recebe duas expressões e cada inteiro é embrulhado em `Num`.
*   **d. `Mul (Add (Num 1) (Num 2)) (Mul (Num 3) (Num 4))`.** Cada operação recebe duas expressões e cada inteiro é embrulhado em `Num`.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Tipo de uma ação de leitura

Considere `act end = do { x <- getChar; if x /= end then do { xs <- act end; return (x:xs) } else return [] }`. Qual o tipo mais geral?

Solução

getChar fixa os elementos e o terminador como `Char`; a leitura é uma ação `IO`.

*   **a. `IO [Char]`.** getChar fixa os elementos e o terminador como `Char`; a leitura é uma ação `IO`.
*   **b. `IO (Char -> [Char])`.** getChar fixa os elementos e o terminador como `Char`; a leitura é uma ação `IO`.
*   **c. `Char -> IO [Char]`.** getChar fixa os elementos e o terminador como `Char`; a leitura é uma ação `IO`.
*   **d. `Eq a => a -> IO [a]`.** getChar fixa os elementos e o terminador como `Char`; a leitura é uma ação `IO`.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Par de funções

Qual expressão admite o tipo `(String -> String, [Int -> Int])`?

Solução

`reverse` transforma uma `String` e os dois elementos da lista são funções `Int` -> `Int`.

*   **a. `(reverse, [\x -> x, \y -> 2*y])`.** `reverse` transforma uma `String` e os dois elementos da lista são funções `Int` -> `Int`.
*   **b. `(concat, [\x -> x+1, \y -> y-1])`.** `reverse` transforma uma `String` e os dois elementos da lista são funções `Int` -> `Int`.
*   **c. `((++ "!!"), map (+1))`.** `reverse` transforma uma `String` e os dois elementos da lista são funções `Int` -> `Int`.
*   **d. `((++), \x -> [x+1, x-1])`.** `reverse` transforma uma `String` e os dois elementos da lista são funções `Int` -> `Int`.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Versão não curried

Qual o tipo da versão não curried de `g x y z = x+y*z`?

Solução

A versão pedida recebe os três argumentos num só triplo.

*   **a. `Num a => (a, a, a) -> a`.** A versão pedida recebe os três argumentos num só triplo.
*   **b. `Num a => (((a -> a) -> a) -> a) -> a`.** A versão pedida recebe os três argumentos num só triplo.
*   **c. `Num a => (a, a) -> (a, a)`.** A versão pedida recebe os três argumentos num só triplo.
*   **d. `Num a => a -> (a -> (a -> a))`.** A versão pedida recebe os três argumentos num só triplo.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Contar valores positivos

O que calcula `h xss = length [x | xs <- xss, x <- xs, x > 0]`, para `h :: [[Int]] -> Int`?

Solução

Os dois geradores percorrem cada elemento e a guarda conserva os positivos.

*   **a. O número de valores positivos na matriz.** Os dois geradores percorrem cada elemento e a guarda conserva os positivos.
*   **b. O número de linhas em que todos os valores são positivos.** Os dois geradores percorrem cada elemento e a guarda conserva os positivos.
*   **c. O número de linhas com algum valor positivo.** Os dois geradores percorrem cada elemento e a guarda conserva os positivos.
*   **d. O número total de valores.** Os dois geradores percorrem cada elemento e a guarda conserva os positivos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Compreensão e ordem

Considere `j [] = []; j (x:xs) | even x = div x 2 : j xs | otherwise = (3*x+1) : j xs`. Qual definição é equivalente?

Solução

A condição transforma cada elemento sem mudar a ordem.

*   **a. `j xs = [div x 2 | x <- xs, even x] ++ [3*x+1 | x <- xs, otherwise]`.** A condição transforma cada elemento sem mudar a ordem.
*   **b. `j xs = [if even x then div x 2 else 3*x+1 | x <- xs]`.** A condição transforma cada elemento sem mudar a ordem.
*   **c. `j xs = [div x 2 | x <- xs, even x] ++ [3*x+1 | x <- xs, not (even x)]`.** A condição transforma cada elemento sem mudar a ordem.
*   **d. `j xs = sum [if even x then div x 2 else 3*x+1 | x <- xs]`.** A condição transforma cada elemento sem mudar a ordem.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Geradores infinitos

O que é efetivamente produzido por `[x/y | x <- [1..], y <- [1..]]`?

Solução

O gerador interior é infinito, pelo que nunca se avança de x = 1.

*   **a. `Todas as frações x/1 com inteiro x >= 1`.** O gerador interior é infinito, pelo que nunca se avança de x = 1.
*   **b. `Todas as frações 1/y com inteiro y >= 1`.** O gerador interior é infinito, pelo que nunca se avança de x = 1.
*   **c. `Todas as frações x/y com inteiros x,y >= 1`.** O gerador interior é infinito, pelo que nunca se avança de x = 1.
*   **d. `Todas as frações x/x com inteiro x >= 1`.** O gerador interior é infinito, pelo que nunca se avança de x = 1.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Filtrar e transformar

Considere `f :: [String] -> [String]; f [] = []; f (xs:rest) | null xs = f rest | otherwise = (xs ++ "!!") : f rest`. Qual é equivalente?

Solução

É necessário excluir as strings vazias antes de acrescentar os pontos.

*   **a. `f = map (++"!!") . filter (not . null)`.** É necessário excluir as strings vazias antes de acrescentar os pontos.
*   **b. `f = filter null . map (++"!!")`.** É necessário excluir as strings vazias antes de acrescentar os pontos.
*   **c. `f = map (++"!!") . filter null`.** É necessário excluir as strings vazias antes de acrescentar os pontos.
*   **d. `f = filter (not . null) . map (++"!!")`.** É necessário excluir as strings vazias antes de acrescentar os pontos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Map aninhado

Qual é equivalente a `f x = map (map (+1)) x`?

Solução

Cada linha mantém-se separada e cada elemento aumenta uma unidade.

*   **a. `f x = [[z+1 | y <- x, z <- y]]`.** Cada linha mantém-se separada e cada elemento aumenta uma unidade.
*   **b. `f x = [[z+1 | z <- y] | y <- x]`.** Cada linha mantém-se separada e cada elemento aumenta uma unidade.
*   **c. `f x = [[z+2 | z <- y] | y <- x]`.** Cada linha mantém-se separada e cada elemento aumenta uma unidade.
*   **d. `f x = [[y+1 | y <- x]]`.** Cada linha mantém-se separada e cada elemento aumenta uma unidade.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Acumulador e fold

Considere `f xs = g xs [] where { g [] acc = acc; g (x:xs) acc = g xs (x:x:acc) }`. Qual é equivalente?

Solução

`foldl` atualiza o acumulador da esquerda para a direita, antepondo duas cópias.

*   **a. `f = foldl (\acc x -> [x,x]:acc) []`.** `foldl` atualiza o acumulador da esquerda para a direita, antepondo duas cópias.
*   **b. `f = foldl (\acc x -> x:x:acc) []`.** `foldl` atualiza o acumulador da esquerda para a direita, antepondo duas cópias.
*   **c. `f = foldr (\x acc -> [x,x]:acc) []`.** `foldl` atualiza o acumulador da esquerda para a direita, antepondo duas cópias.
*   **d. `f = foldr (\x acc -> x:x:acc) []`.** `foldl` atualiza o acumulador da esquerda para a direita, antepondo duas cópias.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Dígitos numa base

Defina `getDigits :: Int -> Int -> [Int]` por divisões inteiras sucessivas. Assuma n >= 0 e 2 <= b <= 10. Devolva os dígitos do menos para o mais significativo. Exemplos: `getDigits 2 3 = [1,1]; getDigits 10 123 = [3,2,1]; getDigits 2 11 = [1,1,0,1]; getDigits 2 0 = []`.

```haskell
getDigits :: Int -> Int -> [Int]
getDigits = undefined
```



### Testes

**Binário**


```haskell
main = print (getDigits 2 11)
```


Saída esperada:

```text
[1,1,0,1]
```

**Decimal**


```haskell
main = print (getDigits 10 123)
```


Saída esperada:

```text
[3,2,1]
```

**Zero**


```haskell
main = print (getDigits 2 0)
```


Saída esperada:

```text
[]
```

Solução

```
getDigits :: Int -> Int -> [Int]
getDigits _ 0 = []
getDigits b n = n `mod` b : getDigits b (n `div` b)
```

O resto dá o próximo dígito; o quociente elimina-o.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Remover pela comparação

Defina `deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]`, removendo apenas o primeiro elemento que o predicado considera igual ao argumento. Exemplos: ``deleteBy (\x y -> x `mod` 2 == y `mod` 2) 1 [3,4,5] = [4,5]; deleteBy (==) 'x' "YXXXx" = "YXXX"``.

```haskell
deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
deleteBy = undefined
```



### Testes

**Paridade**


```haskell
main = print (deleteBy (\x y -> x `mod` 2 == y `mod` 2) 1 [3,4,5])
```


Saída esperada:

```text
[4,5]
```

**Caráter**


```haskell
main = print (deleteBy (==) 'x' "YXXXx")
```


Saída esperada:

```text
"YXXX"
```

**Ausente**


```haskell
main = print (deleteBy (==) 2 [1,3])
```


Saída esperada:

```text
[1,3]
```

Solução

```
deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
deleteBy _ _ [] = []
deleteBy eq x (y:ys) | eq x y = ys
                     | otherwise = y : deleteBy eq x ys
```

Ao encontrar a primeira correspondência, devolve a cauda sem continuar a remover.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Janelas deslizantes

Defina `slidingWindow :: Int -> [a] -> [[a]]`, com todas as fatias consecutivas de comprimento k. Assuma k <= `length` xs. Sugestão: recursão e `take`. Exemplos: `slidingWindow 3 [1..10] = [[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7],[6,7,8],[7,8,9],[8,9,10]]; slidingWindow 2 "ABCD" = ["AB","BC","CD"]; slidingWindow 4 "ABCD" = ["ABCD"]`. Para k = 0, considere uma janela vazia em cada posição, incluindo o fim.

```haskell
slidingWindow :: Int -> [a] -> [[a]]
slidingWindow = undefined
```



### Testes

**Texto**


```haskell
main = print (slidingWindow 2 "ABCD")
```


Saída esperada:

```text
["AB","BC","CD"]
```

**Inteira**


```haskell
main = print (slidingWindow 4 "ABCD")
```


Saída esperada:

```text
["ABCD"]
```

**Zero**


```haskell
main = print (slidingWindow 0 [1,2])
```


Saída esperada:

```text
[[],[],[]]
```

Solução

```
slidingWindow :: Int -> [a] -> [[a]]
slidingWindow k xs | k < 0 = []
                   | k == 0 = replicate (length xs + 1) []
                   | length xs < k = []
                   | otherwise = take k xs : slidingWindow k (tail xs)
```

Cada chamada avança uma posição. O caso k = 0 foi explicitado, pois não estava definido pelo pedido.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Arestas e adjacências

Uma aresta (x,y,d) liga x a y com distância d. Uma lista de adjacências associa a cada nó os pares (destino, distância). Defina `edgesToAdjacencies :: EdgeList -> AdjList`, com uma entrada por nó, incluindo nós que só aparecem como destino. A ordem das listas não importa. Exemplo: `[("A","D",10),("B","C",15),("A","C",5),("C","A",10),("B","D",20)] corresponde a [("A",[("D",10),("C",5)]),("B",[("C",15),("D",20)]),("C",[("A",10)]),("D",[])]`. Pode usar nub, que remove duplicados.

```haskell
import Data.List (nub)
import qualified Data.List
type Node = String
type Dist = Int
type EdgeList = [(Node,Node,Dist)]
type AdjList = [(Node,[(Node,Dist)])]
edgesToAdjacencies :: EdgeList -> AdjList
edgesToAdjacencies = undefined
```



### Testes

**Grafo**


```haskell
main = print (let norm = Data.List.sort . map (\(n,as) -> (n,Data.List.sort as)) in norm (edgesToAdjacencies [("A","D",10),("B","C",15),("A","C",5),("C","A",10),("B","D",20)]))
```


Saída esperada:

```text
[("A",[("C",5),("D",10)]),("B",[("C",15),("D",20)]),("C",[("A",10)]),("D",[])]
```

**Vazio**


```haskell
main = print (edgesToAdjacencies [])
```


Saída esperada:

```text
[]
```

Solução

```
import Data.List (nub)
import qualified Data.List
type Node = String
type Dist = Int
type EdgeList = [(Node,Node,Dist)]
type AdjList = [(Node,[(Node,Dist)])]
edgesToAdjacencies :: EdgeList -> AdjList
edgesToAdjacencies es = [(n, [(y,d) | (x,y,d) <- es, x == n]) | n <- nub ([x | (x,_,_) <- es] ++ [y | (_,y,_) <- es])]
```

Recolhem-se ambos os extremos, sem repetição, e depois as arestas que partem de cada nó.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Criar uma trie

Uma trie `data Trie = Node [(Char,Trie)] deriving Show` guarda filhos etiquetados por caracteres; `Node []` representa a string vazia. Defina recursivamente `makeTrie :: String -> Trie` que cria os prefixos de uma string. Exemplos: `makeTrie "" = Node []; makeTrie "a" = Node [('a',Node [])]; makeTrie "abc" = Node [('a',Node [('b',Node [('c',Node [])])])]`.

```haskell
import qualified Data.List
data Trie = Node [(Char,Trie)] deriving Show
makeTrie :: String -> Trie
makeTrie = undefined
```



### Testes

**Vazia**


```haskell
main = print (show (makeTrie ""))
```


Saída esperada:

```text
"Node []"
```

**Caminho**


```haskell
main = print (let norm (Node cs) = Node (Data.List.sortOn fst [(c,norm t) | (c,t) <- cs]) in show (norm (makeTrie "abc")))
```


Saída esperada:

```text
"Node [('a',Node [('b',Node [('c',Node [])])])]"
```

Solução

```
data Trie = Node [(Char,Trie)] deriving Show
makeTrie :: String -> Trie
makeTrie [] = Node []
makeTrie (x:xs) = Node [(x,makeTrie xs)]
```

Cada carácter cria um filho, e a string vazia termina o caminho.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Inserir prefixos numa trie

Defina `insert :: String -> Trie -> Trie` para inserir todos os prefixos, sem rótulos repetidos entre filhos. A ordem dos filhos não importa. Por exemplo, inserir "abc" em `Node []` cria o caminho a,b,c; inserir depois "abd" partilha a e b e cria os filhos c e d.

```haskell
import qualified Data.List
data Trie = Node [(Char,Trie)] deriving Show
insert :: String -> Trie -> Trie
insert = undefined
```



### Testes

**Dois ramos**


```haskell
main = print (let norm (Node cs) = Node (Data.List.sortOn fst [(c,norm t) | (c,t) <- cs]) in show (norm (insert "abd" (insert "abc" (Node [])))))
```


Saída esperada:

```text
"Node [('a',Node [('b',Node [('c',Node []),('d',Node [])])])]"
```

**Vazia**


```haskell
main = print (show (insert "" (Node [])))
```


Saída esperada:

```text
"Node []"
```

Solução

```
data Trie = Node [(Char,Trie)] deriving Show
insert :: String -> Trie -> Trie
insert [] t = t
insert (x:xs) (Node cs) = Node (go cs)
  where
    go [] = [(x,insert xs (Node []))]
    go ((c,t):rest) | c == x = (c,insert xs t):rest
                    | otherwise = (c,t):go rest
```

Segue o filho existente ou cria-o; os restantes filhos permanecem intactos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

## Cálculo, tipos e indução

Cons e concatenação

Indique o resultado de `"abc":[[]] ++ "dce":[]`.

Solução

```
["abc",[],"dce"]
```

(:) acrescenta uma lista à cabeça; (++) junta as listas exteriores.

Confere a tua resposta:

*   Compare o resultado e a justificação com a solução.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Cauda de listas

Indique o resultado de `tail ([1]:[2]:[]:[3]:[4]:[])`.

Solução

```
[[2],[],[3],[4]]
```

`tail` remove apenas o primeiro elemento da lista exterior.

Confere a tua resposta:

*   Compare o resultado e a justificação com a solução.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Indexação dupla

Indique o resultado de `[[1,2,3,4],[5,6,7,8],[9,10,11,12]] !! 2 !! 1`.

Solução

```
10
```

Os índices começam em zero: escolhe a terceira linha e o seu segundo elemento.

Confere a tua resposta:

*   Compare o resultado e a justificação com a solução.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Mapear uma multiplicação

Indique o resultado de `map (\x -> x*2) [1,2,3,4]`.

Solução

```
[2,4,6,8]
```

`map` multiplica cada elemento por dois, preservando a ordem.

Confere a tua resposta:

*   Compare o resultado e a justificação com a solução.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Diferenças com zipWith

Indique o resultado de `zipWith (-) [1,3..10] [0,3..]`.

Solução

```
[1,0,-1,-2,-3]
```

As listas começam por \[1,3,5,7,9\] e \[0,3,6,9,12\]. `zipWith` termina com a primeira.

Confere a tua resposta:

*   Compare o resultado e a justificação com a solução.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Remover um prefixo

Indique o resultado de `dropWhile (<6) [2..10]`.

Solução

```
[6,7,8,9,10]
```

Remove o prefixo que satisfaz (<6); o primeiro 6 fica.

Confere a tua resposta:

*   Compare o resultado e a justificação com a solução.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Filtrar uma compreensão

Indique o resultado de `[x | x <- [1..10], x <= 6, x >= 4]`.

Solução

```
[4,5,6]
```

As duas condições têm de ser verdadeiras.

Confere a tua resposta:

*   Compare o resultado e a justificação com a solução.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Uma sequência alternada

Defina por compreensão a lista infinita \[-2,4,-8,16,-32,64,-128,256,...\].

```haskell
alternada :: [Integer]
alternada = undefined
```



### Testes

**Oito termos**


```haskell
main = print (take 8 alternada)
```


Saída esperada:

```text
[-2,4,-8,16,-32,64,-128,256]
```

**Prefixo vazio**


```haskell
main = print (take 0 alternada)
```


Saída esperada:

```text
[]
```

Solução

```
alternada = [(-1)^x * 2^x | x <- [1..]]
```

O índice começa em 1, a potência de dois cresce e (-1)^x alterna o sinal.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Terminar no padrão singleton

Avalie `h = let { f [x] = 1; f (y:z) = y * f z } in f [1,2,3,4,5]`.

Solução

```
24
```

O caso \[5\] devolve 1: o produto é 1 × 2 × 3 × 4 × 1.

Confere a tua resposta:

*   Compare o resultado e a justificação com a solução.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Tipo de uma seleção

Indique um tipo admissível para `f xs = head (tail xs)`.

Solução

```
[a] -> a
```

`tail` conserva o tipo da lista; `head` devolve um elemento. A função exige pelo menos dois elementos para terminar sem erro.

Confere a tua resposta:

*   Compare o resultado e a justificação com a solução.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Tipo de um par

Indique o tipo mais geral de `([False,True], ['0','1'])`.

Solução

```
([Bool], String)
```

O primeiro elemento é uma lista de `Bool`; o segundo é \[`Char`\], também chamado `String`.

Confere a tua resposta:

*   Compare o resultado e a justificação com a solução.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Tipo de uma avaliação estrutural

Considere `data E a = V a | Op (E a) (E a); aval (V v) f g = f v; aval (Op e1 e2) f g = g (aval e1 f g) (aval e2 f g)`. Dê um tipo admissível de aval quando f :: a -> `Bool`.

Solução

```
E a -> (a -> Bool) -> (Bool -> Bool -> Bool) -> Bool
```

f transforma uma folha em `Bool`; g combina os dois resultados `Bool` de cada Op.

Confere a tua resposta:

*   Compare o resultado e a justificação com a solução.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Tipo de uma concatenação

Indique o tipo mais geral de `foldr (++) []`.

Solução

```
[[a]] -> [a]
```

(++) combina uma lista com o acumulador, que também é uma lista. A entrada é, por isso, uma lista de listas.

Confere a tua resposta:

*   Compare o resultado e a justificação com a solução.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Aprovação por nota

Defina `aprov` para uma lista de notas, devolvendo A para nota >= 15 e R caso contrário. Exemplos: `aprov [2,8,15,9] = "RRAR" e aprov [12,10,17,8,19] = "RRARA"`. Pode usar o prelúdio ou compreensão, mas não recursão direta.

```haskell
aprov :: [Int] -> String
aprov = undefined
```



### Testes

**Primeira**


```haskell
main = print (aprov [2,8,15,9])
```


Saída esperada:

```text
"RRAR"
```

**Segunda**


```haskell
main = print (aprov [12,10,17,8,19])
```


Saída esperada:

```text
"RRARA"
```

**Vazia**


```haskell
main = print (aprov [])
```


Saída esperada:

```text
""
```

Solução

```
aprov :: [Int] -> String
aprov xs = [if x >= 15 then 'A' else 'R' | x <- xs]
```

Cada nota é classificada independentemente. Os testes não verificam a ausência de recursão direta.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Contar alunos injustiçados

Defina `injust` para contar os alunos que passariam com nota >= 10 mas são reprovados pelo limiar 15. Exemplos: `injust [2,8,15,9] = 0 e injust [12,10,17,8,19] = 2`. Use o prelúdio ou compreensão, sem recursão direta.

```haskell
injust :: [Int] -> Int
injust = undefined
```



### Testes

**Nenhum**


```haskell
main = print (injust [2,8,15,9])
```


Saída esperada:

```text
0
```

**Dois**


```haskell
main = print (injust [12,10,17,8,19])
```


Saída esperada:

```text
2
```

**Limites**


```haskell
main = print (injust [9,10,14,15])
```


Saída esperada:

```text
2
```

Solução

```
injust :: [Int] -> Int
injust xs = length [x | x <- xs, x >= 10, x < 15]
```

O intervalo de notas injustiçadas inclui 10 e exclui 15. Os testes não verificam o método.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Lista infinita de repetições

Defina recursivamente `repete`, que recebe a e produz `[[],[a],[a,a],[a,a,a],...]`.

```haskell
repete :: a -> [[a]]
repete = undefined
```



### Testes

**Prefixo**


```haskell
main = print (take 4 (repete 'x'))
```


Saída esperada:

```text
["","x","xx","xxx"]
```

**Números**


```haskell
main = print (take 3 (repete (2::Int)))
```


Saída esperada:

```text
[[],[2],[2,2]]
```

Solução

```
repete :: a -> [[a]]
repete x = [] : map (x:) (repete x)
```

A lista começa vazia; acrescentar x a cada elemento produz os comprimentos seguintes. Os testes não verificam a recursão.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Máximo lido da entrada

Escreva `maximo :: IO ()`, que lê naturais, um por linha, até ao terminador 0 e escreve o máximo. Pode usar `maximum`. Se o primeiro valor for 0, escreva 0. Para testar no navegador, os testes fornecem as ações de leitura e escrita. Usa `getLine`, `readLn`, `getContents`, `putStr`, `putStrLn` ou `print` sem prefixo de módulo, mantendo os imports iniciais.

```haskell
import Prelude hiding (getLine, readLn, getContents, putStr, putStrLn, print, interact)
import qualified Prelude
import Data.IORef
import System.IO.Unsafe (unsafePerformIO)

maximo :: IO ()
maximo = undefined
```



### Testes

**Sequência**


```haskell
testInput :: IORef [String]
testInput = unsafePerformIO (newIORef ["3","8","2","0"])
{-# NOINLINE testInput #-}
testOutput :: IORef String
testOutput = unsafePerformIO (newIORef "")
{-# NOINLINE testOutput #-}
getLine :: IO String
getLine = do
  xs <- readIORef testInput
  case xs of
    [] -> ioError (userError "Entrada esgotada")
    (x:rest) -> writeIORef testInput rest >> return x
readLn :: Read a => IO a
readLn = read <$> getLine
getContents :: IO String
getContents = do
  xs <- readIORef testInput
  writeIORef testInput []
  return (unlines xs)
putStr :: String -> IO ()
putStr s = modifyIORef' testOutput (++ s)
putStrLn :: String -> IO ()
putStrLn s = putStr (s ++ "\n")
print :: Show a => a -> IO ()
print = putStrLn . show
interact :: (String -> String) -> IO ()
interact f = getContents >>= putStr . f
main :: IO ()
main = do
  maximo
  captured <- readIORef testOutput
  Prelude.print captured
```


Saída esperada:

```text
"8\n"
```

**Imediato**


```haskell
testInput :: IORef [String]
testInput = unsafePerformIO (newIORef ["0"])
{-# NOINLINE testInput #-}
testOutput :: IORef String
testOutput = unsafePerformIO (newIORef "")
{-# NOINLINE testOutput #-}
getLine :: IO String
getLine = do
  xs <- readIORef testInput
  case xs of
    [] -> ioError (userError "Entrada esgotada")
    (x:rest) -> writeIORef testInput rest >> return x
readLn :: Read a => IO a
readLn = read <$> getLine
getContents :: IO String
getContents = do
  xs <- readIORef testInput
  writeIORef testInput []
  return (unlines xs)
putStr :: String -> IO ()
putStr s = modifyIORef' testOutput (++ s)
putStrLn :: String -> IO ()
putStrLn s = putStr (s ++ "\n")
print :: Show a => a -> IO ()
print = putStrLn . show
interact :: (String -> String) -> IO ()
interact f = getContents >>= putStr . f
main :: IO ()
main = do
  maximo
  captured <- readIORef testOutput
  Prelude.print captured
```


Saída esperada:

```text
"0\n"
```

Solução

```
maximo :: IO ()
maximo = loop 0
  where
    loop :: Int -> IO ()
    loop m = do
      n <- readLn
      if n == 0 then print m else loop (max m n)
```

O acumulador guarda o maior natural lido; o zero termina a leitura. A sequência vazia tem resultado convencionado como 0.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Composição recursiva

Defina recursivamente `compL :: [a -> a] -> a -> a`. Por exemplo `compL [f,g,h] v = f (g (h v))`.

```haskell
compL :: [a -> a] -> a -> a
compL = undefined
```



### Testes

**Ordem**


```haskell
main = print (compL [(+1),(*2)] (3::Int))
```


Saída esperada:

```text
7
```

**Vazia**


```haskell
main = print (compL [] (4::Int))
```


Saída esperada:

```text
4
```

Solução

```
compL :: [a -> a] -> a -> a
compL [] v = v
compL (f:fs) v = f (compL fs v)
```

A cauda é aplicada primeiro, preservando a ordem da composição. Os testes não exigem recursão.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Composição de ordem superior

Defina `compL :: [a -> a] -> a -> a` usando uma função de ordem superior, de modo que `compL [f,g,h] v = f (g (h v))`.

```haskell
compL :: [a -> a] -> a -> a
compL = undefined
```



### Testes

**Ordem**


```haskell
main = print (compL [(+1),(*2)] (3::Int))
```


Saída esperada:

```text
7
```

**Vazia**


```haskell
main = print (compL [] (4::Int))
```


Saída esperada:

```text
4
```

Solução

```
compL :: [a -> a] -> a -> a
compL fs = foldr (.) id fs
```

`foldr` compõe da direita para a esquerda e id é o caso vazio. Os testes não exigem o método.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Somar uma árvore

Para `data Arv a = Vazia | No a (Arv a) (Arv a)`, defina `soma` para calcular a soma dos valores dos nós.

```haskell
data Arv a = Vazia | No a (Arv a) (Arv a)
soma :: Num a => Arv a -> a
soma = undefined
```



### Testes

**Árvore**


```haskell
main = print (soma (No 3 (No 2 Vazia Vazia) (No 5 Vazia Vazia)))
```


Saída esperada:

```text
10
```

**Vazia**


```haskell
main = print (soma (Vazia :: Arv Int))
```


Saída esperada:

```text
0
```

Solução

```
data Arv a = Vazia | No a (Arv a) (Arv a)
soma :: Num a => Arv a -> a
soma Vazia = 0
soma (No x e d) = x + soma e + soma d
```

A árvore vazia contribui zero; cada nó acrescenta o seu valor e as duas somas.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Fold de uma árvore

Para `data Arv a = Vazia | No a (Arv a) (Arv a)`, defina `foldtree` análogo a `foldr` para árvores. A função de combinação tem tipo `a -> b -> b -> b`. Por exemplo, `soma t = foldtree soma3 0 t`, com `soma3 x y z = x+y+z`.

```haskell
data Arv a = Vazia | No a (Arv a) (Arv a)
foldtree :: (a -> b -> b -> b) -> b -> Arv a -> b
foldtree = undefined
```



### Testes

**Soma**


```haskell
main = print (foldtree (\x y z -> x+y+z) 0 (No 3 (No 2 Vazia Vazia) (No 5 Vazia Vazia)))
```


Saída esperada:

```text
10
```

**Estrutura**


```haskell
main = print (foldtree (\x y z -> x:y++z) [] (No 1 Vazia (No 2 Vazia Vazia)))
```


Saída esperada:

```text
[1,2]
```

Solução

```
data Arv a = Vazia | No a (Arv a) (Arv a)
foldtree :: (a -> b -> b -> b) -> b -> Arv a -> b
foldtree _ z Vazia = z
foldtree f z (No x e d) = f x (foldtree f z e) (foldtree f z d)
```

O valor base substitui cada árvore vazia; f combina o nó com os dois resultados.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Indução sobre uma árvore

Para `data Arv a = Vazia | No a (Arv a) (Arv a)`, considere `soma Vazia = 0; soma (No x l r) = x + soma l + soma r; foldtree f z Vazia = z; foldtree f z (No x l r) = f x (foldtree f z l) (foldtree f z r)`. Mostre por indução que `soma t = foldtree soma3 0 t`, onde `soma3 x y z = x+y+z`.

Solução

```
Base: soma Vazia = 0 = foldtree soma3 0 Vazia.
Hipóteses: soma l = foldtree soma3 0 l e soma r = foldtree soma3 0 r.
Passo: foldtree soma3 0 (No x l r)
= soma3 x (foldtree soma3 0 l) (foldtree soma3 0 r)
= x + soma l + soma r
= soma (No x l r).
```

A indução segue os construtores e usa uma hipótese por subárvore.

Confere a tua resposta:

*   Compara cada passo com a resolução.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

Indução sobre uma concatenação

Mostre por indução em `xs` que `foldr f v (xs ++ ys) = foldr f (foldr f v ys) xs`. Pode usar as definições de `(++)` e `foldr`.

Solução

```
Base xs = []: foldr f v ([] ++ ys) = foldr f v ys = foldr f (foldr f v ys) [].
Hipótese: foldr f v (zs ++ ys) = foldr f (foldr f v ys) zs.
Passo xs = z:zs:
foldr f v ((z:zs) ++ ys)
= f z (foldr f v (zs ++ ys))
= f z (foldr f (foldr f v ys) zs)
= foldr f (foldr f v ys) (z:zs).
```

Expande a cabeça da lista e aplica a hipótese à cauda. Em cada igualdade, mantém o mesmo acumulador interior.

Confere a tua resposta:

*   Compara cada passo com a resolução.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/haskell-expressoes-tipos/#fun%C3%A7%C3%B5es-por-equa%C3%A7%C3%B5es)

## Funções, grafos e prefixos

Tipos de pares e funções

Qual das expressões admite o tipo `([Int] -> [Int], [Char])`?

Solução

```
(tail, head ["ABC"]) :: ([Int] -> [Int], [Char])
```

A especialização de `tail` aceita uma lista de inteiros e `head` da lista de strings devolve a string "ABC".

*   **`(tail, head ["ABC"])`.** tail pode ser especializada a \[Int\] -> \[Int\], e head devolve uma String.
*   **`(head, reverse "ABC")`.** head devolve um elemento, não uma lista de inteiros.
*   **`(reverse, tail ["ABC"])`.** O segundo elemento é uma lista de strings, não uma string.
*   **`((++), tail "abc")`.** (++) recebe duas listas; não tem o tipo pedido para o primeiro elemento.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Linhas de uma matriz booleana

Considere `f :: [[Bool]] -> Int; f xss = length [xs | xs <- xss, or xs]`. O que calcula f?

Solução

```
f [[False,True],[True,True],[]] == 2
```

or testa cada linha e `length` conta as linhas selecionadas. Uma linha vazia não é selecionada.

*   **Número de entradas True.** A compreensão seleciona linhas inteiras.
*   **Número de linhas só com valores True.** or exige pelo menos um True.
*   **Número de entradas False.** Não conta entradas individuais.
*   **Número de linhas com pelo menos um True.** or xs seleciona exatamente essas linhas.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Compreensão de prefixos

Considere `g :: Int -> [[Int]]; g n = [[1..i] | i <- [1..n]]`. Qual é o resultado?

Solução

```
g 4 == [[1],[1,2],[1,2,3],[1,2,3,4]]
g 0 == []
```

O gerador percorre os valores de i; para n inferior a 1, o intervalo é vazio.

*   **Listas de comprimentos crescentes de 1 até n.** Para cada i, \[1..i\] tem i elementos, quando n é positivo.
*   **Listas de comprimentos decrescentes de n até 1.** i cresce de 1 até n.
*   **Listas todas com comprimento n.** O comprimento é i.
*   **Listas todas com comprimento 1.** Só a primeira tem comprimento 1.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Filtrar e elevar ao quadrado

Dada a definição `h [] = []; h (x:xs) | x>0 = (x*x) : h xs | otherwise = h xs`, qual a compreensão equivalente?

Solução

```
h xs = [x*x | x <- xs, x>0]
```

A guarda seleciona apenas elementos positivos, preservando a sua ordem.

*   **`h xs = [if x>0 then x*x else 0 | x<-xs]`.** Acrescenta zeros para os valores excluídos.
*   **`h xs = [x*x | x<-xs, x>0] ++ [x | x<-xs, otherwise]`.** Acrescenta todos os valores originais.
*   **`h xs = [if x>0 then x*x else x | x<-xs]`.** Mantém os valores não positivos.
*   **`h xs = [x*x | x<-xs, x>0]`.** O predicado exclui os não positivos antes de formar o quadrado.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Filtragem e composição

Considere `f :: [String] -> [String]; f [] = []; f (x:xs) | length x<=5 = f xs | otherwise = take 5 x : f xs`. Qual é a definição equivalente?

Solução

```
f = map (take 5) . filter ((>5) . length)
```

A composição aplica primeiro `filter` à entrada original e só depois `map`.

*   **`f = filter ((<=5).length) . map (take 5)`.** Filtra depois de truncar, quando todas as strings têm comprimento até 5.
*   **`f = map (take 5) . filter ((<=5).length)`.** Seleciona strings demasiado curtas.
*   **`f = filter ((>5).length) . map (take 5)`.** Após truncar, nenhuma string tem comprimento superior a 5.
*   **`f = map (take 5) . filter ((>5).length)`.** Primeiro seleciona as strings longas, depois trunca-as.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Recursão e fold

Dada `g [] = 0; g ((x,y):ps) = x*y - g ps`, qual é a definição equivalente?

Solução

```
g = foldr (\(x,y) r -> x*y-r) 0
```

`foldr` substitui a lista vazia por 0 e cada passo aplica a operação ao par e ao resultado da cauda.

*   **`g = foldr (\r (x,y) -> x*y-r) 0`.** foldr passa primeiro o elemento, não o acumulador.
*   **`g = foldr (\(x,y) r -> x*y-r) 0`.** O segundo argumento é o resultado recursivo.
*   **`g = foldl (\r (x,y) -> r-x*y) 0`.** Um fold à esquerda altera a associação das subtrações.
*   **`g = foldl (\r (x,y) -> x*y-r) 0`.** Um fold à esquerda processa os pares na ordem oposta à associação pedida.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Contar primos numa lista infinita

Considere ``primes = sieve [2..]; sieve (p:xs) = p : sieve [x | x<-xs, x `mod` p/=0]``. Qual expressão conta os primos entre 10000 e 100000, inclusive?

Solução

```
length (takeWhile (<=100000) $ dropWhile (<10000) primes)
```

Como primes é crescente, `takeWhile` produz uma lista finita. `filter` não pára ao encontrar valores superiores ao limite.

*   **`length (filter (\p -> 10000<=p && p<=100000) primes)`.** filter continua a procurar numa lista infinita e length não termina.
*   **`length (take 100000 $ drop 10000 primes)`.** take e drop usam números de elementos, não limites de valor.
*   **`length (takeWhile (<=100000) $ dropWhile (<10000) primes)`.** Descarta os valores inferiores e termina ao ultrapassar o limite superior.
*   **`length (filter (<=100000) $ filter (>=1000) primes)`.** Os filtros percorrem uma lista infinita e o limite inferior também está errado.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Tipo recursivo de lista de pares

Qual definição representa a mesma estrutura que `[(String,Int)]`?

Solução

```
data PairList = Empty | Cons String Int PairList
```

Cada nó corresponde a um par e à cauda da lista; o caso vazio não transporta dados.

*   **`data PairList = Empty | Cons String Int PairList`.** Empty representa \[\] e Cons guarda os dois campos e o resto.
*   **`data PairList = Empty Int | Cons String PairList`.** O caso vazio contém um Int e cada nó não tem um Int.
*   **`data PairList = Empty String Int | Cons Int PairList`.** Os campos do par não estão em cada nó.
*   **`data PairList = Empty String Int | Cons String Int PairList`.** O caso vazio tem campos adicionais.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Comparar metades dos dígitos

Um inteiro é interessante se for positivo e a sua representação decimal se dividir em duas metades iguais, eventualmente com um dígito extra no meio. Por exemplo, 1213121, 5656 e 22 são interessantes; 12345 não é. Defina `interesting :: Int -> Bool`. Calcule os dígitos com uma função auxiliar recursiva e divisões inteiras, sem `show`.

```haskell
interesting :: Int -> Bool
interesting = undefined
```



### Testes

**Metades pares e ímpares**


```haskell
main = print (map interesting [1213121,5656,22,12345])
```


Saída esperada:

```text
[True,True,True,False]
```

**Positividade e um dígito**


```haskell
main = print (map interesting [-22,0,7])
```


Saída esperada:

```text
[False,False,True]
```

**Zeros internos**


```haskell
main = print (map interesting [1010,1001,100100])
```


Saída esperada:

```text
[True,False,True]
```

Solução

```
interesting :: Int -> Bool
interesting n = n > 0 && take h ds == drop (length ds - h) ds
  where
    ds = digits n []
    h = length ds `div` 2
    digits k acc
      | k <= 0 = acc
      | otherwise = digits (k `div` 10) ((k `mod` 10) : acc)
```

A extração constrói os dígitos da esquerda para a direita. Compara as primeiras e últimas metades, ignorando o dígito central quando existe. Um número positivo com um dígito tem duas metades vazias.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Agrupar elementos consecutivos

Defina `groupBy :: (a -> a -> Bool) -> [a] -> [[a]]`, que divide a lista em grupos consecutivos de valores iguais segundo a comparação dada. Não use `Data.List`. Exemplos: `groupBy (==) "aaAccaa" = ["aa","A","cc","aa"]; groupBy (\x y -> toLower x==toLower y) "AabBbcCC" = ["Aa","bBb","cCC"]`.

```haskell
groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy = undefined
```



### Testes

**Grupos consecutivos**


```haskell
main = print (groupBy (==) "aaAccaa")
```


Saída esperada:

```text
["aa","A","cc","aa"]
```

**Lista vazia**


```haskell
main = print (groupBy (==) ([] :: [Int]))
```


Saída esperada:

```text
[]
```

**Comparação com o primeiro**


```haskell
main = print (groupBy (\x y -> abs (x-y) <= 1) [1,2,3,3])
```


Saída esperada:

```text
[[1,2],[3,3]]
```

**Sem distinguir maiúsculas**


```haskell
main = print (groupBy (\x y -> x == y || abs (fromEnum x - fromEnum y) == 32) "AabBbcCC")
```


Saída esperada:

```text
["Aa","bBb","cCC"]
```

Solução

```
groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy _ [] = []
groupBy eq (x:xs) = (x:matched) : groupBy eq rest
  where (matched, rest) = span (eq x) xs
```

span compara os elementos seguintes com o primeiro do grupo. O primeiro que falha inicia a próxima chamada.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Intercalar listas ordenadas

Defina recursivamente `merge :: Ord a => [a] -> [a] -> [a]`, que combina duas listas ascendentes numa lista ascendente com todos os valores. Percorra as duas listas numa única passagem recursiva. Exemplo: `merge [1,4,5,7,9] [2,3,6,8,10] = [1,2,3,4,5,6,7,8,9,10]`.

```haskell
merge :: Ord a => [a] -> [a] -> [a]
merge = undefined
```



### Testes

**Exemplo**


```haskell
main = print (merge [1,4,5,7,9] [2,3,6,8,10])
```


Saída esperada:

```text
[1,2,3,4,5,6,7,8,9,10]
```

**Repetidos**


```haskell
main = print (merge [1,2,2] [2,3])
```


Saída esperada:

```text
[1,2,2,2,3]
```

**Uma lista vazia**


```haskell
main = print (merge ([] :: [Int]) [1,3])
```


Saída esperada:

```text
[1,3]
```

Solução

```
merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
  | x <= y = x : merge xs (y:ys)
  | otherwise = y : merge (x:xs) ys
```

Escolhe a menor cabeça e avança apenas nessa lista. Quando uma termina, a outra já está ordenada e pode ser devolvida inteira.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Ordenação por intercalação

Defina recursivamente `msort :: Ord a => [a] -> [a]` usando `merge` sort: listas vazias ou singulares já estão ordenadas; divida as restantes em duas metades, ordene-as e combine-as com `merge`. Pode usar `merge`. Exemplo: `msort [3,1,5,2,6,4,7,10,9,8] = [1,2,3,4,5,6,7,8,9,10]`.

```haskell
merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
  | x <= y = x : merge xs (y:ys)
  | otherwise = y : merge (x:xs) ys

msort :: Ord a => [a] -> [a]
msort = undefined
```



### Testes

**Exemplo**


```haskell
main = print (msort [3,1,5,2,6,4,7,10,9,8])
```


Saída esperada:

```text
[1,2,3,4,5,6,7,8,9,10]
```

**Vazia e singular**


```haskell
main = print ((msort ([] :: [Int]), msort [4]))
```


Saída esperada:

```text
([],[4])
```

**Repetidos**


```haskell
main = print (msort [3,1,3,2,1])
```


Saída esperada:

```text
[1,1,2,3,3]
```

Solução

```
merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
  | x <= y = x : merge xs (y:ys)
  | otherwise = y : merge (x:xs) ys

msort :: Ord a => [a] -> [a]
msort [] = []
msort [x] = [x]
msort xs = merge (msort left) (msort right)
  where (left, right) = splitAt (length xs `div` 2) xs
```

As metades são menores para listas com pelo menos dois elementos. Depois de ordenadas, `merge` preserva todos os valores.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Substituição em expressões

Considere `type Name = String; data Expr = Const Int | Var Name | Add Expr Expr | Mult Expr Expr; type Env = [(Name,Int)]`. Defina recursivamente `subst :: Env -> Expr -> Expr` para substituir variáveis pelos valores do ambiente. Variáveis ausentes mantêm-se. Exemplos: `subst [("x",2),("y",3)] (Add (Var "x") (Const 1)) = Add (Const 2) (Const 1); subst [("x",2),("y",3)] (Mult (Var "x") (Add (Var "y") (Const 1))) = Mult (Const 2) (Add (Const 3) (Const 1)); subst [("x",2),("y",3)] (Add (Var "x") (Var "z")) = Add (Const 2) (Var "z")`.

```haskell
type Name = String
data Expr = Const Int | Var Name | Add Expr Expr | Mult Expr Expr deriving (Eq, Show)
type Env = [(Name,Int)]
subst :: Env -> Expr -> Expr
subst = undefined
```



### Testes

**Constante e variável**


```haskell
main = print (subst [("x",2),("y",3)] (Add (Var "x") (Const 1)))
```


Saída esperada:

```text
Add (Const 2) (Const 1)
```

**Árvore aninhada**


```haskell
main = print (subst [("x",2),("y",3)] (Mult (Var "x") (Add (Var "y") (Const 1))))
```


Saída esperada:

```text
Mult (Const 2) (Add (Const 3) (Const 1))
```

**Variável ausente**


```haskell
main = print (subst [("x",2),("y",3)] (Add (Var "x") (Var "z")))
```


Saída esperada:

```text
Add (Const 2) (Var "z")
```

**Ambiente vazio**


```haskell
main = print (subst [] (Mult (Var "x") (Const 3)))
```


Saída esperada:

```text
Mult (Var "x") (Const 3)
```

Solução

```
type Name = String
data Expr = Const Int | Var Name | Add Expr Expr | Mult Expr Expr deriving (Eq, Show)
type Env = [(Name,Int)]
subst :: Env -> Expr -> Expr
subst _ (Const n) = Const n
subst env (Var x) = maybe (Var x) Const (lookup x env)
subst env (Add a b) = Add (subst env a) (subst env b)
subst env (Mult a b) = Mult (subst env a) (subst env b)
```

`lookup` encontra o primeiro valor associado ao nome. A variável ausente é preservada; em cada operação percorrem-se ambos os ramos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)

Árvore binária para árvore rosa

Defina `binary2rose :: BinaryTree a -> RoseTree a` para converter data `BinaryTree` a = Leaf a | Node (`BinaryTree` a) a (`BinaryTree` a) em data `RoseTree` a = Rose a \[`RoseTree` a\]. Exemplo: `binary2rose (Node (Node (Leaf 1) 2 (Leaf 3)) 4 (Node (Leaf 5) 6 (Leaf 7))) = Rose 4 [Rose 2 [Rose 1 [],Rose 3 []],Rose 6 [Rose 5 [],Rose 7 []]]`.

```haskell
data BinaryTree a = Leaf a | Node (BinaryTree a) a (BinaryTree a)
data RoseTree a = Rose a [RoseTree a] deriving (Eq, Show)
binary2rose :: BinaryTree a -> RoseTree a
binary2rose = undefined
```



### Testes

**Folha**


```haskell
main = print (binary2rose (Leaf 1))
```


Saída esperada:

```text
Rose 1 []
```

**Exemplo**


```haskell
main = print (binary2rose (Node (Node (Leaf 1) 2 (Leaf 3)) 4 (Node (Leaf 5) 6 (Leaf 7))))
```


Saída esperada:

```text
Rose 4 [Rose 2 [Rose 1 [],Rose 3 []],Rose 6 [Rose 5 [],Rose 7 []]]
```

**Ramos distintos**


```haskell
main = print (binary2rose (Node (Leaf "e") "raiz" (Leaf "d")))
```


Saída esperada:

```text
Rose "raiz" [Rose "e" [],Rose "d" []]
```

Solução

```
data BinaryTree a = Leaf a | Node (BinaryTree a) a (BinaryTree a)
data RoseTree a = Rose a [RoseTree a] deriving (Eq, Show)
binary2rose :: BinaryTree a -> RoseTree a
binary2rose (Leaf x) = Rose x []
binary2rose (Node l x r) = Rose x [binary2rose l, binary2rose r]
```

Uma folha não tem filhos. Um nó conserva o valor e converte recursivamente os filhos pela ordem esquerda, direita.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/listas-recursao/#construir-e-percorrer)