Assuntos abordados nesta sessão:
Obs.: Este guião tem seguimento no da próxima sessão.
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:
^
).
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:
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 |