CAPÍTULO 05 Listas. Listas são estruturas de dados fundamentais da área de programação. Listas...

CAPÍTULO 05

Listas

Listas

• Listas são estruturas de dados fundamentais da área de programação.

• Listas em Haskell representam coleções de objetos de um determinado tipo (homogêneos).

• Para um dado tipo t, existe o tipo "lista de elementos do tipo t", designado por [t].

• Por exemplo:[1,2,3,3,0,1] :: [Int][False,False, True] :: [Bool]

são uma lista de Int e uma lista de Bool.

Definição

• Uma lista sempre é composta de dois segmentos, exceto quando está vazia. Tais segmentos são a cabeça (head) e o corpo (tail).

Definição• Uma lista com cabeça a e cauda x

é escrita no formato (a:x) .• Atenção: em (a:x)

– a é um elemento da lista -> cabeça da lista

– x é uma outra lista -> cauda da lista (que é uma outra lista ou sub-lista)

• Observação: A lista vazia “[]” está presente em qualquer lista e o último elemento aponta para esta lista “[]”.

Definição

• Uma lista é formada por tipos de dados homogêneos, mas pode-se utilizar como alternativa uma lista de tuplas, na qual os dados das tuplas podem ser heterogêneos.

• Restrição: todos os elementos de uma lista devem ser do mesmo tipo!

Casamento de padrões

• (‘a’ : [’b’, ’c’, ’d’]) == [‘a’, ’b’, ’c’, ’d’]• (‘a’ : ’b’ : ’c’ : [’d’]) == [‘a’, ’b’, ’c’, ’d’]• (‘a’ : ’b’ : ’c’ : ’d’ : []) == [‘a’, ’b’, ’c’, ’d’]• [‘a’ : [‘b’, ‘c’, ‘d’] ] == [ [‘a’, ’b’, ’c’, ’d’] ]• (‘a’ : y) == [‘a’, ’b’, ’c’, ’d’]• (‘a’ : _) == [‘a’, ’b’, ’c’, ’d’]• (‘a’ : ‘b’ : [‘c’, ‘d’]) == [x : y : z]

Casamento de padrões

• Alguns erros típicos de casamento de padrões em listas:

• [‘a’ : ‘b’ : [‘c’, ‘d’] ] /= [‘a’, ’b’, ’c’, ’d’]

• [ [‘a’, ’b’, ’c’, ’d’] ] /= [‘a’, ’b’, ’c’, ’d’]

• [‘a’, ’b’, [’c’], ’d’] /= [‘a’, ’b’, ’c’, ’d’]

• [ [ [‘a’] : ’b’, ’c’, ’d’] ] /= [ [‘a’, ’b’, ’c’, ’d’] ]

• [‘a’, ’b’] /= [‘a’]

Operadores “:” e “++"

• Atenção: os operadores “:” e “++” são diferentes!

• O operador : recebe um elemento a e uma lista x, retornando uma nova lista onde a é o primeiro elemento.

• O operador ++ recebe duas listas e retorna sua concatenação! Uma lista única.

• Para memorizar:elemento : lista = listalista ++ lista = lista

Exemplos

• Comprimento (tamanho) da lista: Este é um exemplo clássico sobre listas.

• 1. O comprimento de uma lista vazia é zero;

• 2. O comprimento de uma lista (a:x) é dada por 1 mais o comprimento da sublista “x” que também é uma lista:

compto [] = 0 --função 1compto (a:x) = 1+compto x --função 2

Exemplos

• Um “mapa de memória aproximado” da execução de “compto [1, 2, 3, 4]” é dado por:

Exemplos

• Obter os N primeiros termos da lista:

• primeiros 0 _ = [ ]

• primeiros _ [ ] = [ ]

• primeiros n (a:x) = a : primeiros (n-1) x

• Execução:

Exemplos

• Adicionar um objeto a lista:

• Esta função adiciona um objeto na lista sem repetições, isto é, caso ele já exista na lista o mesmo não é adicionado:

insere c [ ] = [c]

insere c (a:x)|c == a = a : x

|otherwise = a : insere c x

A função “Observe”

• É uma das funções definidas na biblioteca Observe.hs. Destina-se a mostrar as diversas instâncias que variáveis e funções assumem durante a execução de um programa.

• Sintaxe:

import Observe

rem_ultimo [ _ ] = [ ]rem_ultimo (a:b) = observe “a” a : observe “rem_ultimo” rem_ultimo b

A função “Observe”

• O resultado de uma execução da função rem_ultimo com a função observe é dado por:

Main> rem_ultimo [2, 3, 4, 5, 6, 7, 7]

>>>>>>>> Observations <<<<<<<

a

2

3

4

5

6

7

A função “Observe”

rem_ultimo

{ \ (3 : 4 : 5 : 6 : 7 : _ : [ ]) -> 3 : 4 : 5 : 6 : 7 : [ ]

\ (4 : 5 : 6 : 7 : _ : [ ]) -> 4 : 5 : 6 : 7 : [ ]

\ (5 : 6 : 7 : _ : [ ]) -> 5 : 6 : 7 : [ ]

\ (6 : 7 : _ : [ ]) -> 6 : 7 : [ ]

\ (7 : _ : [ ]) -> 7 : [ ]

\ (_ : [ ]) -> [ ]

}

Compreensão de Lista

• A compreensão de listas é feita com um construtor de listas que utiliza conceitos e notações da teoria dos conjuntos. Por exemplo, seja o conjunto A definido por:

A = {x2 | X Є N ^ x é par}

• Este exemplo define o conjunto dos quadrados dos números pares.

• Em Haskell pode ser representado por uma lista definida da seguinte maneira:

Compreensão de Lista

constroi_lista = [x*x | x <- [9... 39], par x]par :: Int -> Boolpar x = mod x 2 == 0Execução:Main> par 26TrueMain> constroi_lista[100, 144, 196, 256, 324, 400, 484, 576,

676, 784, 900, 1024, 1156, 1296, 1444]

Strings

• As strings são formadas por uma seqüência de caracteres, um após o outro, formando uma lista em particular com o tipo caracter ou Char.

Prelude> “Oi Mundo”

“Oi Mundo”

Prelude> [‘O’, ‘i’, ‘ ’, ‘M’, ‘u’, ‘n’, ‘d’, ‘o’]

“Oi Mundo”

Prelude> (‘O’ : ‘i’ : ‘ ’ : ‘M’ : ‘u’ : [‘n’, ‘d’, ‘o’])

“Oi Mundo”

Conversões entre tipos

• A função show apresenta na tela strings e valores numéricos em geral.

• Em particular, a função putStr, imprime uma palavra do tipo String.

• A função read lê um conteúdo e o converte a numérico se for o caso.

• Exemplos:Prelude> “O quadrado de 7 eh: ” ++ show (7 * 7)

“O quadrado de 7 eh: 49”

Conversões entre tipos

Prelude> show (log 4567)“8.426611813185”

Prelude> read “77” + 380

Prelude> read “77 + 56” + 33Program error: Prelude.read: no parse

Prelude> show (read “77” + log 100)“81.6055170185”

Caracteres Especiais

• Alguns caracteres especiais dentro de uma string produzem efeitos na saída, quando sob a função putStr:

• \t ► Produz um espaço-padrão tabulado na saída.

• \n ► Força um salto de linha.• \\ ► Torna uma barra invertida um

caracter normal.• \’ ► Idem para aspas simples (’).• \” ► Idem para aspas duplas (”).

Avaliação Preguiçosa

• Um exemplo clássico de avaliação preguiçosa é exibida por:

lista_infinita :: Int -> [Int]

lista_infinita n = n : lista_infinita (n+1)

...

lista_infinita 3 = 3 : lista_infinita (3+1)

= 3 : 4 : lista_infinita (4+1)

= 3 : 4 : 5 : lista_infinita (5+1)

...

...

Avaliação Preguiçosa

• Esta função computa infinitos valores para uma lista de inteiros, a partir de um número passado como parâmetro. A soma não é determinada até que necessária. Como não há critério de parada, esta, cresce indefinitivamente.

Padrões em Haskell

• Como já visto, em Haskell há casamentos com constantes inteiras, booleanas, caracteres, strings;

• Variáveis;• Tuplas de padrões; ex: (p1,p2,...) onde p1,p2,... também são padrões.

• Listas de padrões; ex: (p1:p2) onde p1 e p2 também são padrões.

• O padrão “_” (o “underscore”);• Construtores de padrões: ( .. : ..), case

Padrões em Haskell

• Quando um argumento a casa com um padrão p?– se p é uma constante e p=a; Ex: 7 == 7– se p é uma variável x, sendo que a será associado a x;– se p é uma tupla (p1,p2,...), a=(a1,a2,...) e cada

componente de a casa com o respectivo componente de p.Ex: (3,1,2) == (3,1,2)

True – se p é uma lista (p1:p2), a é uma lista não vazia e a

cabeça de a casa com p1 e sua cauda casa com p2.– Ex: (1 , 2 , [4 .. 40] ) == (1 , 2, [4 .. 40])

True

Padrões em Haskell

Quanto ao “_” ?{- inicio: uma nova lista, sem o último elemento -} inicio :: [a] -> [a] inicio [ _ ] = [] inicio (x:xs) = observe "x" x : observe "inicio" inicio xs

inicio [1 .. 7][1,2,3,4,5,6]

Não esquecer:

module Listas whereimport Observe

Padrões em Haskellinicio [1 .. 7][1,2,3,4,5,6]

>>>>>>> Observations <<<<<<

x 1 2 3 4 5 6

inicio { \ (2 : 3 : 4 : 5 : 6 : 7 : []) -> 2 : 3 : 4 : 5 : 6 : [] , \ (3 : 4 : 5 : 6 : 7 : []) -> 3 : 4 : 5 : 6 : [] , \ (4 : 5 : 6 : 7 : []) -> 4 : 5 : 6 : [] , \ (5 : 6 : 7 : []) -> 5 : 6 : [] , \ (6 : 7 : []) -> 6 : [] , \ (7 : []) -> [] }

Padrões em Haskell

• Restrição importante: não é permitido usar um mesmo nome mais de uma vez dentro do mesmo padrão!

• Exemplo:

ERRO – variável repetida em padrão!!! (Repeated variable "x" in

pattern)

• Solução :

1 .2 .3 .

1 .2 .3 .

func :: Int -> Int -> Boolfunc x x = Truefunc x y = False

1 .2 .3 .

1 .2 .3 .

func :: Int -> Int -> Boolfunc x y | x == y = Truefunc x y = False

Aplicação: BD para Biblioteca

• Uma biblioteca usa um banco de dados para manter um registro dos livros emprestados aos clientes.

• Pessoas e livros serão representados por Strings.

• O BD será uma lista de pares (Pessoa,Livro).

• Se um par (p,b) estiver no BD, isso significa que o cliente p pegou um exemplar do livro b emprestado.

Tipos

• Exemplo de BD:

exBD = [ ("Alice", "Senhor dos Anéis"), ("Ana", "Windows 3.1"), ("Alice", "Excel para Leigos"), ("Ricardo", "Senhor dos Anéis") ]

1 .2 .3 .

1 .2 .3 .

type Pessoa = Stringtype Livro = Stringtype BancoDados = [ (Pessoa, Livro) ]

Funções de Pesquisa

• As funções de pesquisa em BD recebem como entrada um BD, uma pessoa ou livro, e retornam o resultado da pesquisa.

• Exemplos:– Dada uma pessoa, encontrar os livros emprestados por

ela.– Dado um livro (pode ter mais de uma cópia), listar as

pessoas que estão com o mesmo emprestado.– Dado um livro, descobrir se está emprestado.– Dada uma pessoa, calcular o número de livros que ela tem

emprestados no momento.livros :: BancoDados -> Pessoa -> [Livro]clientes :: BancoDados -> Livro -> [Pessoa]emprestado :: BancoDados -> Livro -> BoolnumEmprest :: Bancodados -> Pessoa -> Int

Funções de Atualização

• As funções de atualização recebem como entrada um BD e retornam um novo BD, resultado de uma operação.

• Exemplos:– Emprestar um livro a um cliente.– Devolver um livro emprestado.

fazEmprest :: BancoDados -> Pessoa -> Livro -> BancoDadosretEmprest :: BancoDados -> Pessoa -> Livro -> BancoDados

Definindo as funções de Pesquisa

• Definir a função: livros :: BancoDados -> Pessoa -> [Livro]

• As funções clientes, emprestado, numEmprest podem ser definidas de forma semelhante.

1 .2 .3 .4 .5 .

1 .2 .3 .4 .5 .

livros :: BancoDados -> Pessoa -> [Livro]livros [] p = []livros ((n,b) : resto) p | p == n = b : livros resto p | otherwise = livros resto p

Definindo as funções de Atualização

• Definir a função: fazEmprest :: BancoDados -> Pessoa ->

Livro -> BancoDados

• Basta adicionar um novo par ao banco de dados (pode haver repetições).

• Pesquisar o BD e remover a primeira ocorrência do par (pes,liv).

• Se não existir esse par no BD, é caracterizada uma situação de erro!

1 .2 .3 .

1 .2 .3 .

fazEmprest:: BancoDados -> Pessoa -> Livro -> BancoDadosfazEmprest db p b = (p,b) : db

Definindo as funções de Atualização

retEmprest:: BancoDados -> Pessoa -> Livro -> BancoDados

retEmprest ((p,b) : resto) pes liv | p == pes && b == liv = resto | otherwise = (p,b) : retEmprest resto pes liv

retEmprest [] pes liv = error ("falha em retEmprest:" ++ pes ++ " " ++ liv)

Cancela apenas a primeira ocorrência do par.Cancela apenas a primeira ocorrência do par.

Definindo as funções de Atualização

• Definição alternativa, cancelando todas as ocorrências do par:

retEmprest:: BancoDados -> Pessoa -> Livro -> BancoDados

retEmprest ((p,b) : resto) pes liv | p==pes && b==liv = retEmprest resto pes liv | otherwise = (p,b) : retEmprest resto pes liv

retEmprest [] pes liv = []

Conclusão

• Listas e suas funções são TAD’s do Haskell

• O poliformismo de tipos é evidenciado. Aplica-se uma função igualmente a todos objetos da lista. Uma função é reusada, sobre vários tipos!

• Uma função serve há vários tipos de listas.• Há muitas funções prontas (“built-in”), já

definidas pelo ambiente.