Copia - 4.6-2 Listas y árboles

2025

Programación lógica con Listas y Árboles Programación Lógica y Funcional

Introducción

• Los objetos estructurados (o estructuras) en PROLOG son términos de la forma f(t1, ..., tn) donde f es un símbolo de función n-ario ó funtor, y t1, ..., tn son a su vez términos (que pueden ser constantes, variables o a su vez estructuras).

• Ejemplos de estructuras son las siguientes:

• libro(moby-dick, autor(herman, melville))
• a+(b*c) ó +(a, *(b, c))

Las estructuras se suelen representar por árboles donde el funtor es un nodo y los componentes son los subárboles que cuelgan de dicho nodo. Los ejemplos anteriores se representarían de la forma:

Variables

• Introduciendo variables en una estructura se puede obtener información. Por ejemplo, supongamos que se tiene el siguiente programa:

BIBLIOTECAesta-en-biblio( libro(moby_dick, autor(herman, melville)) ).esta-en-biblio( libro(sueños_de_robot, autor(isaac, asimov)) ).esta-en-biblio( libro(the_art_of_PROLOG, autor(leon, sterling)) ).---------------------------------------esta-en-biblio( revista(eroski, mensual) ).esta-en-biblio( revista(autopista, semanal) ).----------------------------------------

• A este programa BIBLIOTECA se le pueden hacer preguntas como las siguientes:

Listas

• Una estructura de datos muy común en la programación no numérica son las listas. Estas serán unas estructuras PROLOG especiales.

• Una lista es una secuencia ordenada de elementos que puede tener cualquier longitud. Los elementos de una lista (como los de cualquier otra estructura) son términos, los cuales pueden ser en particular otras listas.

• Las listas pueden representarse como un tipo especial de árbol.

• Una lista es o bien la lista vacía, sin elementos, denotada [ ], o bien una estructura cuyo funtor se denota "." (punto) y con dos componentes llamados "cabeza" y "resto" de la lista.

• Ejemplos:

La lista con un solo elemento a es .(a, [ ]) y su árbol es: La lista que consta de los elementos a, b y c sería: .(a, .(b, .(c, [ ]))) y en forma de árbol es:

• Pero la forma sintáctica más habitual de escribir las listas es separando los elementos entre comas y toda la lista encerrada entre corchetes. Las listas anteriores se escribirían de la forma:

[a] y [a,b,c]

• La forma de manejar las listas es dividiéndolas en cabeza (el primer argumento del funtor punto o el primer elemento de la lista) y resto (el segundo argumento del funtor punto o la lista formada por el resto de elementos de la lista).

• La forma sintáctica en PROLOG para describir una lista con cabeza X y resto Y es la notación [X|Y].

• Ejemplos:
• p( [1, 2, 3] ).
• p( [el, gato, estaba, [en, el, tejado]] ).

• Se puede especificar más de un elemento en la cabeza, indicando primero, segundo,...y resto de la lista:

• También se puede consultar la lista combinando las dos formas sintácticas anteriores ([a1, a2, ..., an] y [A|B]):

• NOTA: La naturaleza de las listas, como estructuras con el funtor punto (.), puede verse mediante el predicado predefinido “display”:

Operaciones con Listas

Concatenación de listas

• ¿Cuál es el resultado de concatenar [a] con [b,c]?
• ?- append([a],[b,c],X).
• X=[a,b,c]
• ¿Qué listas se requiere concatenar para que el resultado sea [a,b,c]?
• ?- append(X,Y,[a,b,c]).
• X=[ ]
• Y=[a,b,c];
• X=[a]
• Y=[b,c];
• etc.

Pertenencia a una lista:

• ¿Cuales son los elementos de la lista [1,2,3]?
• ?- member(X,[5,-3,10]).
• X=5;
• X=-3;
• X=10;

• ¿De qué listas de tamaño 3 es miembro a?
• ?- member(a,[X,Y,Z]).

X = a X = _G290 X = _G290 Y = _G293 Y = a Y = _G293 Z = _G296 ; Z = _G296 ; Z = a ;

Comentarios sobre la notación utilizada

• La notación que se ha seguido aquí para presentar los programas y preguntas PROLOG se conoce como “la notación Prolog de Edimburgo”. La notación de los símbolos del alfabeto es la siguiente:

• Los símbolos de predicado y de función (excepto algunos predefinidos) se denotarán mediante una cadena de letras minúsculas (se puede incluir los caracteres numéricos y el ‘_’) donde el primer carácter deberá ser necesariamente una letra minúscula.
• Los símbolos de constante de igual forma que los anteriores, excepto las constantes numéricas que se representarán directamente.
• Las variables se denotarán como cadenas de caracteres (letras, números y algunos símbolos como ‘_’ o ‘?’), siendo el primer carácter una letra mayúscula.

¡GRACIAS!

2025