...collaborate on

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,

r5 - 23 Oct 2006 - 11:27:39 - JoseBacelarAlmeida
This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback
Syndicate this site RSSATOM