PDF de programación - Programación lógica con listas

Programación lógica con listas

Ingeniería Informática

Ingeniería Técnica en Informática de Sistemas

Departamento de Lenguajes y

Ciencias de la Computación

Universidad de Málaga

Contenido

1. Programación básica con listas
2. Generar/comprobar con listas

Programación lógica con listas

2

Programación básica con listas

Definición de listas

Sea D un dominio o tipo base

Definición: el conjunto de listas L de D se define inductivamente
1. nil ∈ L (lista vacía)
2. si L ∈ L ∧ D ∈ D, entonces D :: L ∈ L

[base]
[recursivo]

:: es un constructor infijo: D × L → L
primer argumento es la cabeza, el segundo la cola
Ejemplo:

a :: b :: c :: nil
1 :: 2 :: 3 :: 4 :: nil
(a :: nil) :: (b :: c :: nil) :: nil

Programación lógica con listas

4

Representación Prolog de las listas

Necesitamos términos recursivos para representar listas

Seguimos la definición inductiva de L:
1. nil ∈ L (lista vacía)
2. si L ∈ L ∧ D ∈ D, entonces D :: L ∈ L

[base]
[recursivo]

Caso base
Caso recursivo estructura functor ./2 .(Cabeza, Cola)

constante []

Una lista bien formada es un término generado por la gramática:

5

L ::= []

| .(T,L)

donde T es un término Prolog
Programación lógica con listas

Prolog no tiene tipos

Las listas así definidas tienen el término como tipo base:

.(a, .(b, .(c, [])))
.(a, .(1, .(f(X,y), [])))
.( .(a, .(b, [])), .(t(U,c),[]) )

En general, los contenedores tendrán el término como tipo base

Ventajas: Prolog es polimórfico
Inconvenientes: Prolog es inseguro

Programación lógica con listas

6

Endulzando las listas

Prolog añade azúcar sintáctico para mejorar la legibilidad:

L ::= []

| [T1, T2, …, Tn]
| [T1, T2, …, Tn | L] % al menos n elementos

% vacía
% n elementos

prefijo

cola

Ejemplo:
.(a,.(b,.(c,[]))) [a,b,c]
.(a,.(1,.(f(X,y), []))) [a,1,f(X,y)]

.(.(a,.(b,[])),.(t(U,c),[]) ) [[a,b],[t(U,c)]]
Programación lógica con listas

7

Azúcar según el gusto

la lista

.(a,.(b,.(c,[])))

puede representarse de varias formas equivalentes:

[a,b,c]
[a,b,c | []]
[a,b | [c]]
[a | [b,c]]
[a | [b | [c] ]]
[a | [b | [c | [] ]]]

Cuidado: después del la | tiene que haber una lista
Programación lógica con listas

8

Plantillas de listas (I)

¿Qué representa cada una de estas listas?
[X]
[X,Y]
[X,X]
[X|[Y]]
[X|Xs]
[a|As]
[X,Y|Zs]
[Xs|Xs]
[Xs|a]

Programación lógica con listas

9

Plantillas de listas (y II)

¿Qué representa cada una de estas listas?
[X]
[X,Y]
[X,X]
[X|[Y]]
[X|Xs]
[a|As]
[X,Y|Zs]
[Xs|Xs]
[Xs|a]

listas de un elemento
listas de dos elementos
listas de dos elementos iguales
listas de dos elementos (equivale a [X,Y])
listas de al menos un elemento
listas que empiezan por a
listas de al menos dos elementos
listas cuyo primer elemento es una lista que
coincide con la cola (ej. [[1,2,3], 1, 2, 3])
no es una lista, después de | debe haber una lista

Programación lógica con listas

10

Unificación de listas

las listas deben unificar elemento a elemento
hay que rescribir las listas colocando la | en la misma posición

(el prefijo más corto)
Ejemplo:

[X | Y]
[a,b,c]

[X | Y]
[a | [b,c]]

{ X / a,

Y / [b,c] }

[X, Y | Ys] [X | [Y|Ys]]
[a | Zs]

[a | Zs]

{ X / a,

Zs / [Y | Ys] }

Programación lógica con listas

11

Ejercicios

Unificar los siguientes pares de listas:
1. [X|Y]
2. [a,[b,c]]
3. [[a,b],c]
4. [a|X]
5. [a|X]
6. [a|X]
7. [a,b,X]
8. [a,b|Y]
9. [a,b|[Y]]
10. [a,b|[Y]]

[a,b,c]
[X|Y]
[X|Y]
[Y|a]
[Y|[c]]
[Y]
[X|T]
[X,T]
[a,b,c]
[a,b,c,d]

Programación lógica con listas

12

Definición de dominio

Seguimos la definición inductiva de L:

•
•

nil ∈ L (lista vacía)
si L ∈ L ∧ D ∈ D, entonces D :: L ∈ L

Utilizaremos la sintaxis simplificada:
% es_lista(?Xs)
es_lista([]).
es_lista([X|Xs]) :- es_lista(Xs).

[base]
[recursivo]

% base
% recursivo

Notación: variables acaban en s cuando deben ser listas; ej: Xs
Ejercicio: Define es_lista_de_naturales/1

Programación lógica con listas

13

Comprobando y generando listas
?- es_lista([A,2+3,t(X)]). % test
Yes
?- es_lista([a,X|c]).
No
?- es_lista(Xs).
Xs = [] ;
Xs = [_G308] ;
Xs = [_G308, _G311] ;
Xs = [_G308, _G311, _G314]
…

% test

% generador no acotado

Programación lógica con listas

14

El predicado longitud/1 (I)
longitud(+Xs,?N) – la lista Xs tiene N elementos

Ejemplo:

?- longitud([a,b,c], 3). % test
Yes
?- longitud([a,b,c],N).
N = 3 ;
No

% generador único

Programación lógica con listas

15

El predicado longitud/1 (II)
longitud(+Xs,?N) – la lista Xs tiene N elementos

Aplicamos recursión sobre la lista Xs:
longitud([], ?) :- ...
longitud([X|Xs], ? ) :- ...

Programación lógica con listas

16

El predicado longitud/1 (III)
longitud(+Xs,?N) – la lista Xs tiene N elementos

El caso base es trivial:

longitud([],0).
longitud([X|Xs], ? ) :- ...

Programación lógica con listas

17

El predicado longitud/1 (y IV)
longitud(+Xs,?N) – la lista Xs tiene N elementos

El caso recursivo es muy simple (patrón recursivo):

longitud([],0).
longitud([X|Xs], N) :-

longitud(Xs,T), % reducir y resolver
N is T+1.

% componer

¿Cómo sería recursivo de cola?

Programación lógica con listas

18

El predicado longitud/1 recursivo de cola
longitud(+Xs,?N) – la lista Xs tiene N elementos

Basta aplicar directamente el patrón:

longitud(Xs,N) :- long_cola(Xs,0,N).
long_cola([],N,N).
long_cola([X|Xs],Ac,N) :-
Ac1 is Ac+1,
long_cola(Xs,Ac1,N).

Ejercicio: compara las tablas de comportamiento de las versiones
recursiva y recursiva de cola

Programación lógica con listas

19

Ejercicios

Define versiones recursivas y recursivas de cola de los siguientes

predicados sobre listas de números:

1. suma(+Xs,?N), N es la suma de los elementos de Xs
2. maximo(+AsMBs,?M), M es el máximo de AsMsBs
3. minimo(+AsMBs,?M), M es el mínimo de AsMsBs
4. cuantas(+X,+AsXBs,?N), X aparece N veces en AsXBs
5. escalar(+Xs,+Ys,?P), P es el producto escalar de Xs y Ys
6. rango(+X,+Y,?Ls), Ls es la lista con los enteros entre X e Y

Programación lógica con listas

20

El predicado miembro/2 (I)
miembro(?X,?Xs) – X pertenece a la lista Xs

¿Cómo aplicamos recursión sobre la lista?
miembro(X, ?):- ...
miembro(X, ?):- ...

¿Cuál es el caso base?

% base
% recursivo

Programación lógica con listas

21

El predicado miembro/2 (II)
miembro(?X,?Xs) – X pertenece a la lista Xs

Caso base: he encontrado el elemento
miembro(X,[X|Xs]).
miembro(X, ?):- ...

% base
% recursivo

sólo puedo inspeccionar la cabeza de la lista
suponemos que Xs es una lista

Programación lógica con listas

22

El predicado miembro/2 (y III)
miembro(?X,?Xs) – X pertenece a la lista Xs

Caso recursivo: puede estar en el resto de la lista
miembro(X,[X|Xs]).
miembro(X,[Y|Xs]):- miembro(X,Xs). % recursivo

% base

Los casos base y recursivo no son excluyentes

Programación lógica con listas

23

Usos de miembro/2
?- miembro(b,[a,b,c]). % test
Yes
?- miembro(X,[a,b,c]). % generador acotado
X = a ;
X = b ;
X = c ;
No
?- miembro(a,Xs).
Xs = [a|_G323] ;
Xs = [_G322, a|_G326] ;
Xs = [_G322, _G325, a|_G329]
...
Programación lógica con listas

% generador no acotado

24

Comportamiento

Tabla de comportamiento de miembro/2
miembro(X,AsXBs)
Uso
(+,+) test
(-,+) generador acotado
(+,-) generador no acotado
(-,-) generador no acotado
Notación: el nombre AsXBs refleja la estructura del término: una
lista que contiene X

Significado
X ∈ AsXBs
{X | X ∈ AsXBs}
AsXBs= [_, ..., _, X | _]
AsXBs= [_, ..., _, X | _]

Ejercicio: Construir la tabla utilizando como caso base

miembro(X,[X|Xs]) :- es_lista(Xs).

Programación lógica con listas

25

El predicado prefijo/2 (I)
prefijo(?Xs,?XsYs) – Xs es prefijo de XsYs

Se puede razonar:

aplicando el patrón: reducir, resolver, componer (hacia atrás)
operacionalmente, recorriendo Xs (hacia delante)

Lo resolveremos de ambas formas

Programación lógica con listas

26

El predicado prefijo/2 (II)
prefijo(?Xs,?XsYs) – Xs es prefijo de XsYs

Aplicamos recursión sobre el primer argumento:
prefijo([],?) :- ...
prefijo([X|Xs],?) :- ...

% base
% recursivo

Caso base: ¿de qué listas es prefijo la lista vacía?

Programación lógica con listas

27

El predicado prefijo/2 (III)
prefijo(?Xs,?XsYs) – Xs es prefijo de XsYs

Caso base: la lista vacía es prefijo de cualquier lista
prefijo([],Ys).
prefijo([X|Xs],?) :- ...

% base
% recursivo

Caso recursivo: reducir, resolver y componer

Programación lógica con listas

28

El predicado prefijo/2 (IV)
prefijo(?Xs,?XsYs) – Xs es prefijo de XsYs

Caso recursivo: reducir y resolver son triviales
prefijo([],Ys).
prefijo([X|Xs],?) :-

prefijo(Xs,XsYs).

Caso recursivo: componer

supongamos que Xs es prefijo de XsYs
¿de qué listas es prefijo [X|Xs] ?

% base
% recursivo

Programación lógica con listas

29

El predicado prefijo/2 (V)
prefijo(?Xs,?XsYs) – Xs es prefijo de XsYs

prefijo([],Ys).
prefijo([X|Xs],[X|XsYs]):-

prefijo(Xs,XsYs).

% base
% recursivo

También se puede razonar operacionalmente

Programación lógica con listas

30

El predicado prefijo/2 (VI)
prefijo(?Xs,?XsYs) – Xs es prefijo de XsYs

Recorremos la primera lista de la cabeza a la cola:
prefijo([X|Xs],?) :-

...

Si la primera lista comienza con X, ¿por qué debe empezar la
segunda lista?

Programación lógica con listas

31

El predicado prefijo/2 (VII)
prefijo(?Xs,?XsYs) – Xs es prefijo de XsYs
La segunda también debe comenzar por X:
prefijo([X|Xs],[X|XsYs]) :-

...

Ya hemos comprobado que las cabezas coinciden: ¿y los restos?

Programación lógica con listas

32

El predicado prefijo/2 (VIII)
prefijo(?Xs,?XsYs) – Xs es prefijo de XsYs

Continuamos recorriendo la lista para comprobar el resto:
prefijo([X|Xs],[X|XsYs]) :-

prefijo(Xs,XsYs).

¿Cuando acabamos?

Programación lógica con listas

33

El predicado prefijo/2 (IX)
prefijo(?Xs,?XsYs) – Xs es prefijo de XsYs

Cuando hayamos recorrido completamente la primera lista:
prefijo([],Ys).
prefijo([X|Xs],[X|XsYs]) :-

prefijo(Xs,XsYs).

Programación lógica con listas

34

El predi