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

Question

Я работаю с 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! 

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

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([]) и оценку к истине; это не поможет вам выбрасывать пустые списки, а не атомы символов.

Answer 2

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

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

Myself, я бы написать 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 3

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

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

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

Во-первых, мы определим, как проверить список:

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

и transitive closure из 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]. 

Answer 6

Строительство на 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 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([], []).