Elementos de Programação (LEGI)
Aula Teórica 4: Listas
António Ravara
Secção de Lógica e Computação, Departamento de Matemática
Instituto Superior Técnico
Notas baseadas na bibliografia básica da cadeira
Elementos de Programação (LEGI) Aula Teórica 4: Listas – p.1
Listas
As listas são o único tipo de dados estruturado
disponível no Mathematica
Uma lista é
1. uma sequência (ordenada) de valores arbitrários,
2. eventualmente heterogénea,
3. possivelmente com repetições
Exemplo
Seja l = {3, T RUE , {2, x}, “xpto”}.
1. H EAD [l] −→ L IST
2. F ULL F ORM [l] −→ L IST[3, T RUE , {2, x}, “xpto”]
Elementos de Programação (LEGI) Aula Teórica 4: Listas – p.2
Construção de Listas
Há 3 formas de definir
1. em extensão
enumeram-se os elementos entre chavetas
2. em compreensão
dá-se uma regra (expressão) para “gerar” os
elementos
avaliação da expressão dá a lista
3. por construção
usando operações do Mathematica que manipulam
listas
Elementos de Programação (LEGI) Aula Teórica 4: Listas – p.3
Definição de Listas — 1
Em extensão
Enumeram-se os elementos entre chavetas
constante básica: {} (lista vazia)
Exemplo:
{3, T RUE , {2, x}, “xpto”}
Não se adequa a listas muito grandes ou que sejam
resultado de cálculo
Elementos de Programação (LEGI) Aula Teórica 4: Listas – p.4
Definição de Listas — 2
Em compreensão
Dá-se uma regra para “gerar” os elementos
TABLE [expr, {var, valinf, valsup, incr}]
Avaliação da expressão dá a lista
Exemplos:
TABLE[ai, {i, 0, 5, 2}] −→ {0, 2a, 4a}
TABLE[ai, {i, 4}] −→ {a, 2a, 3a, 4a}
Gera os elementos todos de uma vez
Nem todas as listas são geráveis por regras
Elementos de Programação (LEGI) Aula Teórica 4: Listas – p.5
Definição de Listas — 3
Por construção
Com operações do Mathematica que manipulam listas
Construtoras
Argumentos são listas e/ou (outros) valores
Resultados são listas
(contradomínio é do tipo L IST)
Auxiliares
Manipulam listas
(alteram ou dão informação sobre listas)
Elementos de Programação (LEGI) Aula Teórica 4: Listas – p.6
Listas por construção — 1
Operações construtoras
Operação (constante) básica: {} (−→ L IST)
Operações que colocam elementos numa lista
L IST × Valor −→ L IST
sendo Valor um tipo arbitrário do Mathematica
A PPEND [l, expr] (P REPEND [l, expr])
devolve a lista formada pela lista argumento com o
valor de expr no final (início)
Exemplo: A PPEND [{3, 2}, 2 − 1] −→ {3, 2, 1}
Elementos de Programação (LEGI) Aula Teórica 4: Listas – p.7
Listas por construção — 2
Operações construtoras
(mais) operações que colocam elementos numa lista
I NSERT [l, expr1 , expr2 ]
devolve a lista formada pela lista argumento com o
valor de expr 1 na posição resultante de avaliar expr 2
expr 2 deve ser um inteiro (se negativo, conta-se a
posição a partir do fim da lista)
R EPLACE PART [l, expr1 , expr2 ]
devolve a lista formada pela lista argumento com o
elemento na posição resultante de avaliar expr 2
substituido pelo resultado de avaliar expr 1
Elementos de Programação (LEGI) Aula Teórica 4: Listas – p.8
Listas por construção — 3
(algumas) Operações auxiliares
1. Operações que devolvem (sub)listas
(ver no Mathematica a sua forma mais geral)
D ROP[l, n]
devolve a lista formada pela lista argumento sem os n
primeiros elementos
(sem os últimos n, se n for negativo)
TAKE[l, n]
devolve a lista formada pelos n primeiros elementos
da lista argumento
(com os últimos n, se n for negativo)
Elementos de Programação (LEGI) Aula Teórica 4: Listas – p.9
Listas por construção — 4
Operações auxiliares
1. (mais) operações que devolvem sublistas das originais
D ELETE [l, n]
devolve a lista formada pela lista argumento sem o
n-ésimo elemento
(contando n a partir do fim da lista, se n for negativo)
R EST[l]
devolve a lista formada pela lista argumento sem o
primeiro elemento
Elementos de Programação (LEGI) Aula Teórica 4: Listas – p.10
Listas por construção — 5
Operações auxiliares
1. (ainda mais) operações que devolvem listas
S ORT[l]
devolve a lista resultante de ordenar a lista argumento
S ELECT [l, predicado]
devolve a lista resultante de seleccionar na lista
argumento os valores que verificam o predicado
Exemplo: S ELECT [{1, 2, 3}, O DD Q] −→ {1, 3}
Elementos de Programação (LEGI) Aula Teórica 4: Listas – p.11
Listas por construção — 6
Operações auxiliares
1. (ainda mais) operações que devolvem listas
J OIN[l, l′ ]
concatena duas listas
l[[l′ ]]
devolve a lista formada pelos elementos da lista l nas
posições dadas pelos elementos da lista l′
Exemplo: {4, 5, 6}[[{1, 3}]] −→ {4, 6}
Elementos de Programação (LEGI) Aula Teórica 4: Listas – p.12
Listas por construção — 7
(mais) Operações auxiliares
2. Operações que dão acesso a elementos de listas
F IRST [l]
devolve o primeiro elemento da lista argumento
L AST[l]
devolve o último elemento da lista argumento
l[[n]]
devolve o n-ésimo elemento da lista argumento
Elementos de Programação (LEGI) Aula Teórica 4: Listas – p.13
Listas por construção — 8
(mais) Operações auxiliares
3. Operações que dão informação sobre listas
L ENGHT [l]
devolve o número de elementos de uma lista
argumento (dito o seu comprimento)
M EMBER Q[l, expr]
predicado que verifica se um dado valor ocorre numa
dada lista
P OSITION[l, expr]
devolve a primeira posição de um dado valor na lista
argumento
Elementos de Programação (LEGI) Aula Teórica 4: Listas – p.14
Observações
Equivalências entre operações
Muitas das funções referidas atrás podem ser definidas à
custa de outras (nem todas são essenciais)
Exemplos:
R EST[l] ⇔ D ELETE [l, 1]
D ROP[l, −n] ⇔ TAKE [l, L ENGHT [l] − n]
Funções parciais
Muitas das funções referidas atrás não estão sempre
definidas (dão erro para alguns argumentos)
Exemplos: F IRST [{}] ou D ELETE [{1, 2, 3}, 4]
Elementos de Programação (LEGI) Aula Teórica 4: Listas – p.15
Exercícios
1. Defina uma função que conta o número de valores
pares de uma lista de inteiros
contapares = F UNCTION [l, L ENGTH [S ELECT [l, E VEN Q]]]
2. Defina uma função que conta o número de valores de
uma lista de inteiros que obedecem a determinado
critério
contaq = F UNCTION [{l, q}, L ENGTH [S ELECT [l, q]]]
3. Defina uma função que verifica se uma lista está
ordenada por ordem crescente
ordcresQ = F UNCTION [l, l == S ORT[l]]
Elementos de Programação (LEGI) Aula Teórica 4: Listas – p.16