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,