Свести список в Прологе

Question

Я работаю с Прологом всего пару дней. Я кое-что понимаю, но меня это действительно смущает.

Я предполагаю написать функцию, которая берет список и выравнивает его.

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

Функция убирает внутренние структуры списка.

Это то, что я имею до сих пор:

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

Теперь, это работает, когда я звоню:

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

Но когда я звоню, чтобы посмотреть, является ли список, который я ввожу, уже сведен, возвращается false вместо true:

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

Почему это работает с одной стороны, а не с другой? Я чувствую, что упускаю что-то очень простое.

Answer 1

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

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

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

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

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

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

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

Answer 2

Вы можете поддерживать свои списки открытым, как с указателем на его начало, так и с «конечным отверстием и свободным указателем» (т. Е. 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 в любом месте. Этот метод известен как «списки различий», но гораздо проще думать о нем как о «открытых списках».

---

обновление: Это гораздо проще кодировать с использованием синтаксиса 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 !)

Answer 3

Опираясь на 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

Answer 4

Вот версия для полноты на основе аккумулятора:

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

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

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

2. Непустой список представлен термином .\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's a list, anyway?
%-----------------------
list( X ) :- var(X) , ! , fail .
list( []    ) .
list( [_|_] ) .

Answer 6

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

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

Я не нашел решения, использующего 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].