Сгладить список в Prolog

Ответ 1

Определение flatten2/2, которое вы указали, вызывается; он действительно ведет себя следующим образом:

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

Итак, учитывая случай, когда вы уже привязали R к [a,b,c,d,e], сбой не вызывает удивления.

Ваше определение отбрасывает хвост списков (ListTail) в третьем предложении - это нужно убрать и подключить обратно в список, чтобы вернуться через RetList. Вот предложение:

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

Этот рекурсивно редуцирует все списки списков в списки отдельных элементов [x] или пустые списки [], которые он выбрасывает. Затем он накапливает и добавляет их все в один список из вывода.

Обратите внимание, что в большинстве реализаций Prolog пустой список [] является атомом и списком, поэтому вызов atom([]) и is_list([]) оценивается как true; это не поможет вам выбрасывать пустые списки, а не атомы символов.

Ответ 2

Вы можете сохранять свои списки открытыми, как с указателем на его начало, так и с "конечным отверстием & frasl; free pointer" (т.е. logvar) в конце, который затем можно создать при достижении конца:

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 --->

Затем вы называете это

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

Таким образом, нет необходимости использовать reverse где угодно. Этот метод известен как "списки различий", но гораздо проще просто подумать об этом как о "открытых списках".

update: это намного проще закодировано с помощью dcg. Поскольку он является однонаправленным (первый аргумент должен быть полностью заземлен), почему бы не использовать разрезы в конце концов:

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

Тестирование:

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.

Если определение было полностью декларативным, последнему следовало бы также с X=[c] ; X=[[],c] ; ... ; X=[[c]] ; ...; увы, это не так.

(edit2: упрощенные обе версии, благодаря комментариям @mat!)

Ответ 3

Обозначение списка пролога - синтаксический сахар поверх очень простых прологовых терминов. Списки Пролога обозначаются так:

• Пустой список представлен атомом []. Зачем? Потому что это выглядит как математическое обозначение для пустого списка. Они могли использовать атом типа nil для обозначения пустого списка, но они этого не сделали.

• Непустой список представлен термином .\2, где первым (самым левым) аргументом является глава списка, а второй (самый правый) аргумент - это хвост списка, который, рекурсивно, сам список.

Некоторые примеры:

• Пустой список: [] представляется в виде атома:

  []
  

• Список одного элемента [a] внутренне сохраняется как

  .(a,[])
  

• Список из двух элементов [a,b] внутренне сохраняется как

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

• Список из трех элементов [a,b,c] внутренне сохраняется как

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

Рассмотрение главы списка также является синтаксическим сахаром над теми же обозначениями:

• [X|Xs] идентичен .(X,Xs)

• [A,B|Xs] идентичен .(A,.(B,Xs))

• [a,b] (см. выше), идентичный .(A,.(B,[]))

Я сам напишу flatten/2 следующим образом:

%------------------------
% 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 a list, anyway?
%-----------------------
list( X ) :- var(X) , ! , fail .
list( []    ) .
list( [_|_] ) .

Ответ 4

Основываясь на if_//3 и list_truth/2, мы можем реализовать myflatten/2 следующим образом:

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)
   ).

Примеры запросов (взятых из других ответов и комментариев к ответам):

?- 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 и not(nil_or_cons_t) описывают те же решения, но порядок решения отличается. Рассмотрим:

?- 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

Ответ 5

Здесь полная версия для полнофункционального аккумулятора:

% 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.

Ответ 6

Я не нашел решение, используя findall, поэтому добавлю его. (он будет работать, если список заземлен)

Сначала мы определяем, как тестировать список:

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

и транзитное закрытие member, мы называем это member*:

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

Сплющенный список - это все решение member*, которые не являются списками:

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

Пример:

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

Ответ 7

Без любого другого предиката, только с рекурсией хвоста.

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([], []).