...collaborate on
View   r5  >  r4  >  r3  >  r2  >  r1

LI1Aula3 5 - 23 Oct 2006 - Main.JoseBacelarAlmeida
Line: 1 to 1
 

Sessão Laboratorial 3

Assuntos abordados nesta sessão:

Added:
>
>
Obs.: Este guião tem seguimento no da próxima sessão.
 
Line: 68 to 69
 
    • A média das notas dos alunos,
    • A média das notas dos alunos aprovados,
Deleted:
<
<

Funções de ordem superior simples

Nas funções realizadas na tarefa anterior é bem patente que algumas delas partilham um mesmo padrão: um exemplo será o cálculo das listas dos alunos aprovados e reprovados - em ambos os casos "filtramos" da lista original os elementos que satisfazem um dado critério. O facto de o Haskell permitir manipular funções como quaisqueres outros valores (e.g. podemos passar funções como argumentos para outras funções) permite-nos criar funções que abstraiam esses padrões comuns. Continuando com o exemplo da lista de aprovados/reprovados, podemos utilizar função pré-definida

filter :: (a->Bool) -> [a] -> [a]
que filtra todos os elementos de uma lista que satisfassam um dado predicado. As funções ficariam então:
alunosAprov :: Curso -> [Aluno]
alunosAprov xs = filter (verifAprov) xs

alunosReprov :: Curso -> [Aluno]
alunosReprov xs = filter (not . verifAprov) xs
Obs.: (not . verifAprov) é a composição de ambas as funções: not após verifAprov.

Outras funções pré-definidas no Prelude que correspondem a padrões repediamente encontrados são:

  • map::(a->b)->[a]->[b], (map f l) aplica a função f a cada elemento de l retornando a lista de resultados. Exemplo: map verifAprov listaAlunos retorna [True, False, True].
  • zip::[a]->[b]->[(a,b)], (zip l1 l2) associa os elementos das listas l1 e l2 produzindo uma lista de pares. Exemplo: (zip [1,2,3] ['A','B','C']) retorna [(1,'A'),(2,'B'),(3,'C')].
  • unzip::[(a,b)]->([a],[b]), (unzip l) separa uma lista de pares duas listas, cada uma contendo cada uma das componentes. Exemplo: (unzip [(1,'A'),(2,'B'),(3,'C')]) retorna ([1,2,3],['A','B','C'])
  • ...

Tarefa 3: Pode fazer uso de alguma(s) destas funções nas funcionalidades pedidas na tarefa anterior? Experimente...

Utilização das bibliotecas

Já se referiu que a biblioteca do Haskell dispõe de um vasto conjunto de funções úteis (algumas já tem vindo a ser referidas, muitas outras o serão ao longo do semestre...). A forma última de se conhecer a oferta existente, e de obter informação para a sua utilização consiste em consultar a documentação existente. Para a tarefa que se segue pretende-se utilizar algumas funções dos seguintes módulos (para além das já referidas...):

Tarefa 4: Pretende-se realizar um programa que realize um histograma com a frequência das palavras que ocorrem nesse texto. Assim, o resultado de avaliar

hist "Um texto com palavras... um, com, palavras, palavras, dois,dois"
deverá retornar a lista:
[("um",2),("texto",1),("com",2),("palavras",3),("dois",2)]
Note que se ignora a pontuação e não se distinguem as letras maiúsculas das minúsculas.

LI1Aula3 4 - 12 Oct 2006 - Main.JoseBacelarAlmeida
Line: 1 to 1
 

Sessão Laboratorial 3

Changed:
<
<


>
>
Assuntos abordados nesta sessão:
 
Changed:
<
<
Nesta sessão...
>
>
 


Line: 21 to 18
 fact 0 = 1 fact n = n * (fact (n-1))
Changed:
<
<
Observe que o argumento da invocação recursiva é estritamente menor do que o parâmetro da função - é este facto que garante que a função termina. De facto, para o cálculo de (fact 3) o interpretador realiza as seguintes reduções:
>
>
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:
 
Changed:
<
<
(fact 3) ---> 3 * (fact 2) ---> 3 * (2 * (fact 1)) ---> 3 * (2 * (1 * (fact 0))) ---> 3 * (2 * (1 * 1)) = 6
>
>
(fact 3) ---> 3 * (fact 2) ---> 3 * (2 * (fact 1)) ---> ---> 3 * (2 * (1 * (fact 0))) ---> 3 * (2 * (1 * 1)) = 6
 
Added:
>
>
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

Changed:
<
<
O tipos prédefinidos do Haskell são suficientemente poderosos para representarem uma grande variedade de dados que possamos quer vir a manipular. 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.
>
>
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.
 
Changed:
<
<
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 a esse tipo. Para codificar uma função que verifique se o aluno está aprovado podemos codificar:
>
>
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]
Line: 41 to 53
 Tarefa 2: Defina:
  • a lista listaAlunos contendo informação referente aos seguintes alunos
Added:
>
>
 
Num. Nome Nota
1234 José Azevedo 13.2
2345 Carlos Lopes 9.7
3456 Rosa Mota 17.9
Added:
>
>
 
  • 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,
Line: 56 to 70
 

Funções de ordem superior simples

Changed:
<
<
Nas funções realizadas na tarefa anterior é bem patente que algumas delas partilham um mesmo padrão: um exemplo será o cálculo das listas dos alunos aprovados e reprovados - em ambos os casos "filtramos" da lista original os elementos que satisfazem um dado critério. O facto de o Haskell permitir manipular funções como quaisquer outros valores (e.g. podemos passar funções como argumentos para outras funções) permite-nos criar funções que abstraiam esses padrões comuns. Continuando com o exemplo da lista de aprovados/reprovados, podemos utilizar função pré-definida
>
>
Nas funções realizadas na tarefa anterior é bem patente que algumas delas partilham um mesmo padrão: um exemplo será o cálculo das listas dos alunos aprovados e reprovados - em ambos os casos "filtramos" da lista original os elementos que satisfazem um dado critério. O facto de o Haskell permitir manipular funções como quaisqueres outros valores (e.g. podemos passar funções como argumentos para outras funções) permite-nos criar funções que abstraiam esses padrões comuns. Continuando com o exemplo da lista de aprovados/reprovados, podemos utilizar função pré-definida
 
filter :: (a->Bool) -> [a] -> [a]
Line: 80 to 94
 

Utilização das bibliotecas

Changed:
<
<
Já se referiu que a biblioteca do Haskell dispõe de um vasto conjunto de funções úteis.
>
>
Já se referiu que a biblioteca do Haskell dispõe de um vasto conjunto de funções úteis (algumas já tem vindo a ser referidas, muitas outras o serão ao longo do semestre...). A forma última de se conhecer a oferta existente, e de obter informação para a sua utilização consiste em consultar a documentação existente. Para a tarefa que se segue pretende-se utilizar algumas funções dos seguintes módulos (para além das já referidas...):
 Tarefa 4: Pretende-se realizar um programa que realize um histograma com a frequência das palavras que ocorrem nesse texto. Assim, o resultado de avaliar
hist "Um texto com palavras... um, com, palavras, palavras, dois, dois"
Changed:
<
<
deverá retornar como resultado:
>
>
deverá retornar a lista:
 
[("um",2),("texto",1),("com",2),("palavras",3),("dois",2)]

LI1Aula3 3 - 12 Oct 2006 - Main.JoseBacelarAlmeida
Line: 1 to 1
 

Sessão Laboratorial 3

Line: 9 to 9
 Nesta sessão...
Added:
>
>

 
Deleted:
<
<

Definições de funções recursivas

Funções da biblioteca...

words, unwords, etc...

Histograma de palavras

Sinónimos de tipos

complexos...

Declarações locais

 
Added:
>
>

Definição de funções recursivas

 
Changed:
<
<
trabalho final: alunos... nota máxima, média, reprovs,...
>
>
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 - é este facto que garante que a 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

Sinónimos de tipos

O tipos prédefinidos do Haskell são suficientemente poderosos para representarem uma grande variedade de dados que possamos quer vir a manipular. 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 a esse tipo. Para codificar uma função que verifique se o aluno está aprovado podemos codificar:

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,

Funções de ordem superior simples

Nas funções realizadas na tarefa anterior é bem patente que algumas delas partilham um mesmo padrão: um exemplo será o cálculo das listas dos alunos aprovados e reprovados - em ambos os casos "filtramos" da lista original os elementos que satisfazem um dado critério. O facto de o Haskell permitir manipular funções como quaisquer outros valores (e.g. podemos passar funções como argumentos para outras funções) permite-nos criar funções que abstraiam esses padrões comuns. Continuando com o exemplo da lista de aprovados/reprovados, podemos utilizar função pré-definida

filter :: (a->Bool) -> [a] -> [a]
que filtra todos os elementos de uma lista que satisfassam um dado predicado. As funções ficariam então:
alunosAprov :: Curso -> [Aluno]
alunosAprov xs = filter (verifAprov) xs

alunosReprov :: Curso -> [Aluno]
alunosReprov xs = filter (not . verifAprov) xs
Obs.: (not . verifAprov) é a composição de ambas as funções: not após verifAprov.

Outras funções pré-definidas no Prelude que correspondem a padrões repediamente encontrados são:

  • map::(a->b)->[a]->[b], (map f l) aplica a função f a cada elemento de l retornando a lista de resultados. Exemplo: map verifAprov listaAlunos retorna [True, False, True].
  • zip::[a]->[b]->[(a,b)], (zip l1 l2) associa os elementos das listas l1 e l2 produzindo uma lista de pares. Exemplo: (zip [1,2,3] ['A','B','C']) retorna [(1,'A'),(2,'B'),(3,'C')].
  • unzip::[(a,b)]->([a],[b]), (unzip l) separa uma lista de pares duas listas, cada uma contendo cada uma das componentes. Exemplo: (unzip [(1,'A'),(2,'B'),(3,'C')]) retorna ([1,2,3],['A','B','C'])
  • ...

Tarefa 3: Pode fazer uso de alguma(s) destas funções nas funcionalidades pedidas na tarefa anterior? Experimente...

Utilização das bibliotecas

Já se referiu que a biblioteca do Haskell dispõe de um vasto conjunto de funções úteis.

Tarefa 4: Pretende-se realizar um programa que realize um histograma com a frequência das palavras que ocorrem nesse texto. Assim, o resultado de avaliar

hist "Um texto com palavras... um, com, palavras, palavras, dois, dois"
deverá retornar como resultado:
[("um",2),("texto",1),("com",2),("palavras",3),("dois",2)]
Note que se ignora a pontuação e não se distinguem as letras maiúsculas das minúsculas.
 

LI1Aula3 2 - 09 Oct 2006 - Main.JoseBacelarAlmeida
Line: 1 to 1
 

Sessão Laboratorial 3

Line: 12 to 12
 

Definições de funções recursivas

Added:
>
>

Funções da biblioteca...

words, unwords, etc...

Histograma de palavras

Sinónimos de tipos

complexos...

Declarações locais

trabalho final: alunos... nota máxima, média, reprovs,...


LI1Aula3 1 - 06 Oct 2006 - Main.JoseBacelarAlmeida
Line: 1 to 1
Added:
>
>

Sessão Laboratorial 3


Nesta sessão...

Definições de funções recursivas


Revision 5r5 - 23 Oct 2006 - 11:27:39 - JoseBacelarAlmeida
Revision 4r4 - 12 Oct 2006 - 23:54:26 - JoseBacelarAlmeida
Revision 3r3 - 12 Oct 2006 - 18:44:42 - JoseBacelarAlmeida
Revision 2r2 - 09 Oct 2006 - 23:22:18 - JoseBacelarAlmeida
Revision 1r1 - 06 Oct 2006 - 08:48:34 - 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