Prolog

Manejo de listas en Prolog

CI-1441
Paradigmas Computacionales
Prof. Yadira Solano

Definición
secuencias finitas de términos arbitrarios donde
el orden de los elementos es relevante
un elemento puede repetirse dentro de la lista.

objeto estructurado:
todos los objetos estructurados son árboles.
tipo especial de estructura (árboles binarios)

23/05/2008

2

Notación
Engeneral, una lista se puede escribir
en una variedad de formas
equivalentes
1. Externa: [ t1, t2, ...].
2. Flexible: [H | T]
3. Interna:
op( t1, op(t2, op(t3, op(t4, [] )))).
23/05/2008

3

[]

Notación interna
Ejemplo:
la lista [t1,t2,t3,t4] puede escribirse
como:

[t1,t2|[t3|[t4]]], o
[t1|[t2|[t3|[t4|[]]]]],
muy artificial pero correcta
sintácticamente

op
op

t1

opt2

op

t3
t4

23/05/2008

[]
4

Lista

(cont.)

Lista vacía: [ ].
Lista no vacía: consta de 2 partes que se combinan por
medio de un operador
Cabeza: objeto (átomo), lista (árbol), una variable.
Cola: lista, [ ] (lista vacía o Nil)

Ejemplos:
único elemento: [t]
t: cabeza.
[ ] cola; lista vacía (nil) ≡ átomo.

más de un elemento: [t1,t2,...,tn].
t1: cabeza
23/05/2008[t2,...,tn]: cola (se obtiene removiendo t1 de la lista)

5

Notación [H | T ]
–

?- [a|[b,c,d]] = [a,b,c,d].
yes
Ambas listas sintácticamente equivalentes: cola = lista

–

?- [a|b,c,d] = [a,b,c,d].
no
Hay incorrectamente 3 términos después de la barra y solo debe
haber un único término, el cuál debe ser una lista.

23/05/2008

6

Listas (ejemplos)
Generación de unalista sencilla:
loc_lista([mango, brocoli, galletas], cocina).
loc_lista([mesa, computadora], oficina).
loc_lista([lampara, sobre], escritorio).
loc_lista([estampilla, llave], sobre).
loc_lista([lavadora], patio).
loc_lista([ropa], lavadora).
loc_lista([], sala). %No hay nada
?- loc_lista(X, cocina), write(X).
X = [mango, brocoli, galletas]
23/05/2008

7

Listas (ejemplos)
Posiblesconsultas:
?- [H|T] = [mango, brocoli, refrigerador].
H = mango
T = [brocoli, refrigerador]
?- [H|T] = [a, b, c, d, e].
H=a
T = [b, c, d, e]
Ejemplos:?- [H|T] = [piña, bananos].
H = piña
(la cola es una lista
T = [bananos]
con 1 elemento)
?- [H|T] = [a, [b,c,d]].
H=a
T = [[b, c, d]]
23/05/2008

8

Listas (ejemplos)

?- [H|T] = [mangos].
H = mangos
T = [ ] (la cola es unalista vacía)
?- [H|T] = [ ].
no
La lista vacía no unifica sintácticamente porque no
tiene cabeza.

Importante:
Esta falla se usa para probar la condición límite en la
rutina recursiva, i.e., la unificación con el patrón [X|Y]
tendrá éxito si hay elementos en la lista, de lo contrario
falla.
23/05/2008

9

Ejemplos

La cola es una lista vacía
?- [H|T] = [mangos].
H = mangos
T=[]La lista vacía no unifica con la sintaxis estándar
porque no tiene cabeza.
?- [H|T] = [ ].
no

NOTA:
Esta falla es muy importante, se usa para probar la condición
límite en la rutina recursiva, i.e., si hay elementos en la lista la
unificación con el patrón [X|Y] tendrá éxito de lo contrario la
unificación falla indicando que la condición límite aplica.

23/05/2008

10

Listas(ejemplos)

Se pueden especificar otros elementos antes de
la barra (|); la única regla es que lo que sigue
sea una lista

?- [Uno, Dos | T] = [mango, piña, cas, mora].
Uno = mango
Dos = piña
T = [cas, mora]

23/05/2008

11

Listas (ejemplos)
Variables internas: la unificación de listas es un punto crítico en la
construcción de predicados útiles para el manejo de listas.
?- [X,Y|T]= [a|Z].
X=a
Y = _01
T = _02
Z = [_01 | _02]
?- [H|T] = [apple, Z].
H = apple
T = [_01]
Z = _01

Z unifica [Y|T].

T unifica [Z].

En ambos casos, Prolog busca la manera más general para relacionar
o limitar las variables.
23/05/2008

12

Operaciones con listas
–

Inserción
X=[a,b,c]. Y=[m,n,s|X] → Y=[m,n,s,a,b,c].

–

Destrucción de listas
[X | Y] = [c, a, r, l,...