Sessão Laboratorial 3
Assuntos abordados nesta sessão:
Obs.: Este guião tem seguimento no da
próxima sessão.
Definição de funções recursivas
A recursividade é um recurso fundamental para codificar funções não triviais numa linguagem funcional. A ideia básica consiste em permitir-se codificar uma função com recurso a ela própria, desde que com argumentos mais simples. O exemplo sempre citado é a definição da função factorial:
n! = n * (n-1) * ... * 1. Observando que
(n-1)!=(n-1) *...*1, verificamos que podemos definir
n!=n*(n-1)! para
n>0 (em que
0!=1). Em
haskell poderiamos então definir:
fact :: Int -> Int
fact 0 = 1
fact n = n * (fact (n-1))
Observe que o argumento da invocação recursiva é estritamente menor do que o parâmetro da função - é por este motivo que o cálculo da função termina. De facto, para o cálculo de
(fact 3)
, o interpretador realiza as seguintes reduções:
(fact 3) ---> 3 * (fact 2) ---> 3 * (2 * (fact 1)) --->
---> 3 * (2 * (1 * (fact 0))) ---> 3 * (2 * (1 * 1)) = 6
Um outro domínio onde a recursividade surge naturalmente é ao realizar funções sobre listas (sequências). Aí, a forma mais natural de definirmos uma função consiste em explicitar qual o resultado para o caso da lista vazia
[]
, e para o caso da lista não vazia
(x:xs)
. Neste último caso, podemos invocar a própria função recursivamente na cauda
xs
porque esta é necessariamente mais pequena do que lista original. Um exemplo clássico é a função que calcula o comprimento:
len :: [a] -> Int
len [] = 0
len (x:xs) = 1 + (len xs)
Tarefa 1: Defina as seguintes funções que:
- dado a e b determine a^b (sem utilizar a operação de exponenciação
^
).
- dado uma lista de inteiros, conte o número de zeros contidos nessa lista.
- dado uma lista de inteiros, calcule o seu somatório.
- dado uma lista e um elemento, verifique se esse elemento está contido na lista.
Sinónimos de tipos
O tipos pré-definidos do
Haskell são suficientemente poderosos para representarem uma grande variedade de dados. A título de exemplo, considere que se pretende representar e manipular a informação relativa a alunos de um curso e as suas respectivas notas. Assim, para cada aluno pretende-se registar: o número, o nome, e a nota. Essa informação pode ser representada no tipo
(Int, String, Float)
. Para representar a informação de todos os alunos do curso, utilizamos uma lista desse tipo.
Em casos como este, é útil fazer uso da possibilidade oferecida pelo
haskell em atribuir sinómimos de tipos (declaração
type
) - podemos dessa forma atribuir um nome mais informativo ao tipo em questão. Uma função que verifique se o aluno está aprovado pode ficar codificada como:
type Aluno = (Int, String, Float)
type Curso = [Aluno]
verifAprov :: Aluno -> Bool
verifAprov (num, nome, nota) = (nota >=10)
Tarefa 2: Defina:
- a lista
listaAlunos
contendo informação referente aos seguintes alunos
Num. | Nome | Nota |
1234 | José Azevedo | 13.2 |
2345 | Carlos Lopes | 9.7 |
3456 | Rosa Mota | 17.9 |
- uma funções que dado a lista de alunos, determine:
- Uma lista só com os números dos alunos,
- Uma lista só com os nomes dos alunos,
- O número de alunos aprovados e reprovados,
- Uma lista com os alunos aprovados,
- Uma lista com os alunos reprovados,
- A média das notas dos alunos,
- A média das notas dos alunos aprovados,