Listas en programacion

Cap´ ıtulo 2

Programaci´n con Listas o
En Prolog la estructura de lista est´ predefinida como una estructura rea cursiva lineal cuyas componentes pueden ser heterog´neas porque en Prolog e no existe una comprobaci´n tipos. B´sicamente una lista es una estructura o a con dos argumentos: la cabeza de la lista, que es un componente de la lista, y la cola que es otra lista con el resto de loscomponentes. Normalmente existen dos notaciones para listas, una notaci´n prefija: .(Cabeza,Cola) y o una notaci´n infija [Cabeza|Cola] m´s c´moda de utilizar, y para denotar o a o la lista vac´ se utiliza siempre []. As´ la lista (a,b,c,d) se puede escribir ıa ı, en Prolog de cualquiera de las dos formas siguientes: .(a,.(b,.(c,.(d.[])))) [a|[b|[c|[d|[]]]]],

sin embargo, la segunda forma admitesimplificaciones que permiten escribir todos los elementos de la lista entre corchetes y separados por comas: [a,b,c,d], o escribir varios elementos a la izquierda del s´ ımbolo |, tambi´n separados e por comas, as´ como cualquier combinaci´n de estas dos formas; con lo que ı o nuestra lista se puede escribir de cualquiera de las formas siguientes: [a|[b,c,d]] [a,b|[c,d]] [a,b,c|[d]] [a,b,c,d|[]] .Es importante observar que en las dos notaciones para listas, el segundo argumento debe ser siempre una lista, pues aunque como hemos dicho Prolog no comprueba tipos, s´ es capaz de distinguir las listas de otra clase de ı t´rminos. As´ notaciones como las siguientes e ı, .(a,b) [a|b]

se considerar´ err´neas porque b es una constante (´tomo) y no es una ıan o a lista. Tambi´n hay que tener encuenta que entre los componentes de una e 17

18

´ CAP´ ITULO 2. PROGRAMACION CON LISTAS

lista pueden aparecer otras listas, as´ por ejemplo, [a,b,[c,d,e]] ser´ ı, ıa una lista con tres componentes, el ultimo de los cuales es a su vez una lista, ´ mientras que [a,b|[c,d,e]] ser´ una lista con cinco componentes todos ıa constantes. Para consolidar el uso de las notaciones de listaproponemos el siguiente ejercicio. Ejercicio 2.0.5 Apl´ ıquese el algoritmo de unificaci´n a los pares de t´rmio e nos que aparecen en las filas de la siguiente tabla anotando los resultados de cada aplicaci´n (instanciaciones o fallo) en la columna resultado o resultado [X|Y] [a,[b,c]] [[a,b],c] [a|X] [a|X] [a|X] [a,b,Y] [a,b,X] [a,b|Y] [a,b|[Y]] [a,b|[Y]] [a,b,c] [X|Y] [X|Y] [Y|a] [Y|[c]] [Y] [X,T] [X|T][X,T] [a,b,c] [a,b,c,d]

2.1.

Dominios para listas

Como hemos dicho en el apartado anterior, Prolog es capaz de distinguir las listas de cualquier otra clase de t´rminos, pero esta distinci´n la e o hace a nivel interno para detectar errores de notaci´n durante el proceso de o unificaci´n. Si en alg´n programa queremos saber si un t´rmino T es una o u e lista (no vac´ podemos intentarunificarlo con una expresi´n de la forma ıa) o [X|Xs] usando el predicado de unificaci´n expl´ o ıcita ‘.=.’, o podemos definir un predicado recursivo lista/1 en la forma lista([]). lista([X|Xs]):-lista(Xs). Este predicado es lo m´s parecido a una definici´n del tipo lista que se puede a o hacer en Prolog y sirve para comprobar si un t´rmino es una lista cuando e se lo proporciona un argumento conocido, perotambi´n sirve para generar, e por reevaluaci´n, listas cuyas componentes son variables libres. o Ejercicio 2.1.1 Pru´bese el predicado anterior con los argumentos siguiene tes: a, arbol(r,Iz,De), [a,b] y [a,b|arbol(r,Iz,De)]. Pru´bese nuevae mente con una variable y p´ ıdanse varias reevaluaciones para ver la secuencia de listas que se va generando.

2.2. ELEMENTOS DE UNA LISTAS

19

Deforma parecida se pueden construir predicados para la definici´n de o dominios m´s concretos correspondientes a listas cuyos componentes sean a de una determinada clase, siempre que se pueda usar la unificaci´n para diso tinguir los t´rminos de dicha clase o disponga de un predicado de definici´n e o del correspondiente dominio. Ejercicio 2.1.2 Construid los predicados listanat/1 y listaficha/1 para...