ppt - listas y arboles en prolog

Aplanar una lista en Prolog

Question

Solo he estado trabajando con Prolog durante un par de días. Entiendo algunas cosas pero esto realmente me confunde.

Se supone que debo escribir una función que toma una lista y la aplana.

?- flatten([a,[b,c],[[d],[],[e]]],Xs).  
Xs = [a,b,c,d,e].                           % expected result

La función saca las estructuras internas de la lista.

Esto es lo que tengo hasta ahora:

flatten2([],[]).
flatten2([Atom|ListTail],[Atom|RetList]) :-
      atom(Atom), flatten2(ListTail,RetList).
flatten2([List|ListTail],RetList) :-
      flatten2(List,RetList).

Ahora, esto funciona cuando llamo:

?- flatten2([a,[b,c],[[d],[],[e]]], R).
R = [a,b,c,d,e].                         % works as expected!

Pero cuando llamo para ver si una lista que ingresé ya está acoplada, devuelve false lugar de true :

?- flatten2([a,[b,c],[[d],[],[e]]], [a,b,c,d,e]).
false.                                   % BAD result!

¿Por qué funciona en una mano, pero no en la otra? Siento que me estoy perdiendo algo muy simple.

Answer 1

Aquí hay una versión basada en el acumulador para completar:

% flatten/2
flatten(List, Result) :- flatten(List, [], Result).

% auxiliary predicate flatten/3
flatten([], Result, Result).
flatten([Head| Tail], Part, Result) :- 
    is_list(Head),
    !, 
    flatten(Head, HR),
    append(Part, HR, PR),
    flatten(Tail, PR, Result).
flatten([Head| Tail], Part, Result) :- 
    append(Part, [Head], PR),
    flatten(Tail, PR, Result).
flatten(X, Part, Result) :-
    fail.

Answer 2

La definición de flatten2/2 que has dado está rota; en realidad se comporta así:

?- flatten2([a, [b,c], [[d],[],[e]]], R).
R = [a, b, c] ;
false. 

Entonces, dado el caso en el que ya ha enlazado R a [a,b,c,d,e] , el fallo no es sorprendente.

Su definición es deshacerse de la cola de las listas ( ListTail ) en la tercera cláusula; esto debe ser ordenado y conectado nuevamente a la lista para regresar a través de RetList . Aquí hay una sugerencia:

flatten2([], []) :- !.
flatten2([L|Ls], FlatL) :-
    !,
    flatten2(L, NewL),
    flatten2(Ls, NewLs),
    append(NewL, NewLs, FlatL).
flatten2(L, [L]).

Este recursivamente reduce todas las listas de listas en listas de elementos individuales [x] , o listas vacías [] que se desechan. Luego, se acumula y los agrega a todos en una lista de nuevo de la salida.

Tenga en cuenta que, en la mayoría de las implementaciones de Prolog, la lista vacía [] es un átomo y una lista, por lo que la llamada a atom([]) y is_list([]) evalúan como verdaderas; esto no te ayudará a tirar listas vacías en lugar de átomos de caracteres.

Answer 3

La notación de la lista de Prolog es azúcar sintáctica por encima de los términos de prólogo muy simples. Las listas de prólogos se denotan así:

1. La lista vacía está representada por el átomo [] . ¿Por qué? Porque se parece a la notación matemática para una lista vacía. Podrían haber usado un átomo como nil para denotar la lista vacía pero no lo hicieron.

2. Una lista no vacía está representada por el término ./2 , donde el primer argumento (el extremo izquierdo) es el encabezado de la lista y el segundo (el extremo derecho) es la cola de la lista, que es, recursivamente, una lista.

Algunos ejemplos:

• Una lista vacía: [] se representa como el átomo que es:

  []

• Una lista de un elemento, [a] se almacena internamente como

  .(a,[])

• Una lista de dos elementos [a,b] se almacena internamente como

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

• Una lista de tres elementos, [a,b,c] se almacena internamente como

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

El examen del jefe de la lista es también azúcar sintáctica sobre la misma notación:

• [X|Xs] es idéntico a .(X,Xs)

• [A,B|Xs] es idéntico a .(A,.(B,Xs))

• [A,B] es (ver arriba) idéntico a .(A,.(B,[]))

Yo mismo escribiría flatten/2 así:

%------------------------
% public : flatten a list
%------------------------
flatten( X , R ) :-
  flatten( X , [] , T ) ,
  reverse( T , R )
  .

%--------------------------------------------
% private : flatten a list into reverse order
%--------------------------------------------
flatten( [] , R , R ) .        % the empty list signals the end of recursion
flatten( [X|Xs] , T , R ) :-   % anything else is flattened by
  flatten_head( X , T , T1 ) , % - flattening the head, and
  flatten( Xs , T1 , R )       % - flattening the tail
  .                            %

%-------------------------------------
% private : flatten the head of a list
%-------------------------------------
flatten_head( X , T , [X|T] ) :- % if the head is a not a list
  /+ list(X) ,                   % - simply prepend it to the accumulator.
  ! .                            %
flatten_head( X , T , R     ) :- % if the head is a list
  flatten( X , T , R )           % - recurse down and flatten it.
  .

%-----------------------
% what''s a list, anyway?
%-----------------------
list( X ) :- var(X) , ! , fail .
list( []    ) .
list( [_|_] ) .

Answer 4

No encontré una solución usando findall , así que la findall . (Funcionará si la lista es molida)

Primero, definimos cómo probar una lista:

list(X) :- var(X), !, fail.
list([]).
list([_|_]).

y el cierre transitivo de member , lo llamamos member* :

''member*''(X, Y) :- member(X, Y).
''member*''(X, Y) :- member(Z, Y), ''member*''(X, Z).

La lista aplanada es toda la solución del member* que no son listas:

flatten(X, Y) :- findall(Z, (''member*''(Z, X), /+ list(Z)), Y).

Ejemplo:

?- flatten([[4],[[5,6],[7,[8],[9,[10,11]]]]],Y).
Y = [4, 5, 6, 7, 8, 9, 10, 11].

Answer 5

Puede mantener sus listas abiertas, con un puntero hasta su inicio y un "agujero final po puntero libre" (es decir, logvar) al final, que luego puede crear una instancia cuando se llega al final:

flatten2( [], Z, Z):- !.                                        % ---> X
flatten2( [Atom|ListTail], [Atom|X], Z) :-                      %      .
    /+is_list(Atom), !,                                         %      .
    flatten2( ListTail, X, Z).                                  %      Y
flatten2( [List|ListTail], X, Z) :-                             %      .
    flatten2( List,     X, Y),       % from X to Y, and then    %      .
    flatten2( ListTail, Y, Z).       % from Y to Z              %      Z --->

Entonces lo llamas como

flatten2( A, B):- flatten2( A, B, []).

De esa manera no hay necesidad de usar reverse ninguna parte. Esta técnica se conoce como "listas de diferencia", pero es mucho más fácil pensar en ella como "listas abiertas".

actualización: esto es mucho más fácil codificado usando la sintaxis dcg . Ya que es unidireccional (el primer argumento debe ser completamente molido), ¿por qué no usar cortes después de todo?

flattn([]) --> [], !.
flattn([A|T]) --> {/+is_list(A)}, [A], !, flattn(T).
flattn([A|T]) --> flattn(A), flattn(T).

Pruebas:

16 ?- phrase(flattn([a,[b,c],[[d],[],[e]]]), [a, b, c, d, e]).
true.

17 ?- phrase(flattn([a,[b,c],[[d],[],[e]]]), R).
R = [a, b, c, d, e].

18 ?- phrase(flattn([a,[b,X],[[d],[],[e]]]), [a, b, c, d, e]).
X = c.

Si la definición fuera totalmente declarativa, la última también debería haber tenido éxito con X=[c] ; X=[[],c] ; ... ; X=[[c]] ; ... X=[c] ; X=[[],c] ; ... ; X=[[c]] ; ... X=[c] ; X=[[],c] ; ... ; X=[[c]] ; ... ; Ay, no lo es.

( edit2 : simplificó ambas versiones, gracias a los comentarios de @ !)

Answer 6

Sin ningún otro predicado, solo con cola recursiva.

flatten([[X|S]|T], F) :- flatten([X|[S|T]], F).
flatten([[]|S], F) :- flatten(S, F).
flatten([X|S], [X|T]) :- /+(X = []), /+(X = [_|_]), flatten(S, T).
flatten([], []).

Answer 7

Sobre la base de if_//3 y list_truth/2 , podemos implementar myflatten/2 siguiente manera:

myflatten(Xs,Ys) :-
   phrase(myflatten_aux(Xs),Ys).

myflatten_aux([]) --> [].
myflatten_aux([T|Ts]) --> 
   if_(neither_nil_nor_cons_t(T), [T], myflatten_aux(T)),
   myflatten_aux(Ts).

:- use_module(library(dialect/sicstus/block)).

:- block neither_nil_nor_cons(-).
neither_nil_nor_cons(X) :-
   /+nil_or_cons(X).

nil_or_cons([]).
nil_or_cons([_|_]).

neither_nil_nor_cons_t(X,Truth) :-
   (  nonvar(X)
   -> (  neither_nil_nor_cons(X) -> Truth = true
      ;                             Truth = false
      )
   ;  nonvar(Truth) 
   -> (  Truth == true -> neither_nil_nor_cons(X)
      ;  Truth == false,  nil_or_cons(X)
      )
   ;  Truth = true,  neither_nil_nor_cons(X)
   ;  Truth = false, nil_or_cons(X)
   ).

Consultas de muestra (tomadas de otras respuestas y comentarios a las respuestas):

?- myflatten([[4],[[5,6],[7,[8],[9,[10,11]]]]], Xs).
Xs = [4, 5, 6, 7, 8, 9, 10, 11].

?- myflatten([1,[8,3],[3,[5,6],2],8], Xs).
Xs = [1, 8, 3, 3, 5, 6, 2, 8].

?- myflatten([a,[b,c],[],[[[d]]]], Xs).
Xs = [a, b, c, d].

?- myflatten([a,[b,c],[[d],[],[e]]], Xs).
Xs = [a, b, c, d, e].

neither_nil_nor_cons_t y not(nil_or_cons_t) describen tienen las mismas soluciones, pero el orden de la solución es diferente. Considerar:

?- myflatten([A,B,C],Xs), A=a,B=b,C=c.
A = a,
B = b,
C = c,
Xs = [a, b, c] ;                       % does not terminate universally