展平列表

Question

试图从http://www.ic.unicamp.br/~meidanis/courses/mc336/2009s2/prolog/problemas/解决练习 07

我从一个看起来像下面的迭代开始

my_flatten1([], []).
my_flatten1([[A|T]|U], [A|V]) :-
   append(T, U1, V),
   my_flatten1(U, U1).
my_flatten1([A|T], [A|U]) :-
   not(is_list(A)),
   my_flatten1(T, U).

is_flat(A) :-
   my_flatten1(A, A).

它似乎适用于以下一组查询

my_flatten1([a, [b, [c, d], e]], X).
my_flatten1(X, [a, b, c]).
my_flatten1(X, [a|T]).
my_flatten1(X, [a, b, A]).
my_flatten1([a, X], M).
my_flatten1([a|X], M).

is_flat([a|X]).
is_flat([a,[c]|X]).
is_flat([F,[c]|X]).

my_flatten1(A, B).
my_flatten1([A], B).
my_flatten1([[A]], B).
my_flatten1([[a|A]], B).
my_flatten1([a|A], B).
my_flatten1([X|B], [1,2,3,4]).
my_flatten1([[a,c|D]|X], [a|B]).

但是我没有成功地my_flatten基于my_flatten1. 总会有一些查询失败或以无限循环结束，或者只产生一个最明显的结果。

编辑以澄清我所追求的内容，例如我可以my_flatten1使用变量作为第一个参数调用以分配括号：

?- my_flatten1(X, [a, b]).
X = [[a], [b]] ;
X = [[a], b] ;
X = [[a, b]] ;
X = [a, [b]] ;
X = [a, b].

Answer 1

不知道你是否知道，当你点击问题标题时，99个Prolog问题都包含解决方案？

不管怎样，my_flatten它看起来像下面这样：

my_flatten(X,[X]) :- \+ is_list(X).
my_flatten([],[]).
my_flatten([H|T],R) :-
    my_flatten(H,HFlat),
    my_flatten(T,TFlat),
    append(HFlat,TFlat,R).

一些问题：

?- my_flatten([[]],R).
   R = [].

?- my_flatten([[1],[2]],R).
   R = [1, 2].

?- my_flatten([[1],[[3]]],R).
   R = [1, 3].

编辑

正如 @lambda.xy.y 所正确观察到的，上述版本不会终止查询：

?- my_flatten(X,[X]).

所以我看了一下 SWI 的内置行为flatten/2并观察到：

?- flatten([],[]).
   true.

?- flatten([],X).
   X = [].

?- flatten(X,[]).
   false.

?- flatten(X,Y).
   Y = [X].

?- flatten(X,[X]).
   true.

执行：

my_flatten(L,R) :-
    my_flatten(L,[],Flat),
    !,
    R=Flat.

my_flatten(X,R,[X|R])  :- \+ is_list(X), !.
my_flatten([],R,R)     :- !.
my_flatten([H|T],A1,R) :- !,
    my_flatten(H,A2,R),
    my_flatten(T,A1,A2).
my_flatten(NonList,T,[NonList|T]).