Сгладить список в Prolog
Я работаю с Prolog всего пару дней. Я понимаю некоторые вещи, но это меня действительно сбивает с толку.
Я должен написать функцию, которая берет список и выравнивает его.
?- 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!
Почему это работает с одной стороны, но не с другим? Я чувствую, что мне не хватает чего-то очень простого.
Ответы
Ответ 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([], []).