Listas

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

lista vacia = []
lista en general: [H|T] (H = head, T = Tail)

[H|T] = [a,b,c]  => H = a, T = [b,c]
      = [a|[b,c]]
      = [a,b|[c]]
      = [a,b,c|[]]

[a,b,c,d,e] = [a,b,c|T]   => T = [d,e]

Podemos definir lista como:

es_lista([]).
es_lista([H|T]) :- es_lista(T).

anade(El,Lista,[El|Lista]).

elemento(X,[X|T]).
elemento(X,[_|T]):-
       elemento(X,T).             (usos)

quita(El,[El|L],L).
quita(El,[H|T],[H|R]):-
       quita(El,T,R).

También para anadir un elemento en diferentes lugares:

quita(a,L,[b,c,d])

elemento(El,L) :- quita(El,L,_).

anade(El,Lista1,Lista2) :- quita(El,Lista2,Lista1).

prefijo([],L).
prefijo([X|T],[X|R]):- prefijo(T,R).       (usos)

sufijo(L,L).
sufijo(L,[H|T]):- sufijo(L,T).             (usos)

sublista(L1,L2):-
       prefijo(L3,L2),
       sufijo(L1,L3).

sublista(L1,L2):-
       prefijo(L1,L3),
       sufijo(L3,L2).

sublista(L1,L2):- prefijo(L1,L2).
sublista(L1,[H|T]):- sublista(L1,L2).

append([],L,L).
append([H|L1],L2,[H|L3]):-
        append(L1,L2,L3).                    (usos)

adyacentes(X,Y,L) :- append(_,[X,Y|_],L).

prefijo(L1,L2):- append(L1,X,L2).

sufijo(L1,L2):- append(X,L1,L2).

sublista(L1,L2) :- 
       append(X,Y,L2),
       append(L1,Z,Y).

sublista(L1,L2):-
       append(X,Y,L2),
       append(Z,L1,X).

member(X,L) :- append(Y,[X|Z],L).

member(X,L) :- sublista([X,L).

last(X,[X]).
last(X,[_|T]):- last(X,T).

last(X,L) :- append(Y,[X],L).

long([],0).
long([H|T],s(N)):- long(T,N).

Si queremos guardar las acciones que hace el mono podemos añadir un argumento extra:

come(edo(_,_,_,si),[]).
come(Edo1,[Acc|Resto]) :-
        mov(Edo1, Acc, Edo2),
        come(Edo2,Resto).

Permutación:

(A)

: permuta el resto y añade un elemento

permuta([],[]).
permuta([El|L],Perm):-
       permuta(L,LP),
       anade(El,LP,Perm).

(B)

: quita 1 elemento y permuta el resto

permuta([],[]).
permuta(L,[El|R]):-
       quita(El,L,L2),
       permuta(L2,R).

Si preguntamos: permuta(L,[a,b,c]).
(A) nos da las primeras 6 soluciones y despues se cicla
(B) nos da solo la primera y despues se cicla

Voltea una lista:

voltea([],[]).
voltea([H|T],Vol):-
     voltea(T,TVol),
     append(TVol,[H],Vol).

Sin embargo, ocupa mucha memoria. Un ``truco'' común en Prolog (y Lisp) es inlcuir un argumento extra para ir guardando los resultados parciales (un acumulador) y volverla tail recursive.

voltea(L,LV) :- voltea(L,[],LV).

voltea([],L,L).
voltea([H|T],Acum,Vol):-
     voltea(T,[H|Acum],LVol).

Palindrome lo podemos definir asi:

palin([]).
palin([_]).
palin([H|T]):-
    append(EnMedio,[H],T),
    palin(EnMedio).

Alternativamente: palin(L) :- voltea(L,L).

Aplana:

aplana([],[]).
aplana([H|T],Res) :-
      aplana(H,HP),
      aplana(T,TP),
      append(HP,TP,Res).
aplana(X,[X]).

Podemos hacer una version con una lista intermedia para evitar el ``append''

aplana(List,ListPl) :- aplana(List,[],ListPl).

aplana([],L,L).
aplana([H|T],L1,L3) :-
     aplana(H,L1,L2),
     aplana(T,L2,L3).
aplana(X,S,[X|S]).