Свести список в Прологе
Я работаю с Прологом всего пару дней. Я понимаю некоторые вещи, но это действительно смущает меня.
Я предполагаю написать функцию, которая берет список и выравнивает его.
?- 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!
Почему это работает с одной стороны, а не с другой? Я чувствую, что упускаю что-то очень простое.
7 ответов
Определение 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([]) оба оценивают как истинные; это не поможет вам выбросить пустые списки, в отличие от атомов персонажей.
Вы можете поддерживать свои списки открытым, как с указателем на его начало, так и с "конечным отверстием - свободный указатель" (т.е. 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!)
Опираясь на 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
Вот версия на основе аккумулятора для полноты:
% 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.
Без какого-либо другого предиката, только с хвостовой рекурсией.
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([], []).
Нотация списка Пролога - синтаксический сахар поверх очень простых терминов пролога. Пролог списки обозначаются так:
Пустой список представлен атомом
[], Зачем? Потому что это похоже на математическую запись пустого списка. Они могли бы использовать атом, как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's a list, anyway?
%-----------------------
list( X ) :- var(X) , ! , fail .
list( [] ) .
list( [_|_] ) .
Я не нашел решения, используя 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].