在 Prolog 中展平列表

发布于 2024-12-31 22:53:42 字数 856 浏览 1 评论 0原文

我才使用 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!

为什么一方面可以，另一方面不行？我觉得我错过了一些非常简单的东西。

原文

I've only been working with Prolog for a couple days. I understand some things but this is really confusing me.

I'm suppose to write a function that takes a list and flattens it.

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

The function takes out the inner structures of the list.

This is what I have so far:

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

Now, this works when I call:

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

But when I call to see if a list that I input is already flattened, is returns false instead of true:

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

Why does it work on one hand, but not the other? I feel like I'm missing something very simple.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

街角迷惘 2025-01-07 22:53:43

我没有使用 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].

I didn't find a solution using findall, so I'll add it. (it will work if the list is fully ground, including that all its elements are fully ground)

First, we define how to test for a list:

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

and the transitive closure of member, we call it member*:

'member*'(X, Y) :- member(X, Y).
'member*'(X, Y) :- member(Z, Y), 'member*'(X, Z).

The flattened list is all the solution of member* which are not lists:

flatten(X, Y) :- findall(Z, ('member*'(Z, X), \+ list(Z)), Y).

Example:

?- flatten([[4],[[5,6],[7,[8],[9,[10,11]]]]],Y).
Y = [4, 5, 6, 7, 8, 9, 10, 11].

回复收藏 0 原文

提笔落墨 2025-01-07 22:53:42

您给出的 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；这不会帮助您丢弃空列表而不是字符原子。

The definition of flatten2/2 you've given is busted; it actually behaves like this:

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

So, given the case where you've already bound R to [a,b,c,d,e], the failure isn't surprising.

Your definition is throwing away the tail of lists (ListTail) in the 3rd clause - this needs to be tidied up and connected back into the list to return via RetList. Here is a suggestion:

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

This one recursively reduces all lists of lists into either single item lists [x], or empty lists [] which it throws away. Then, it accumulates and appends them all into one list again out the output.

Note that, in most Prolog implementations, the empty list [] is an atom and a list, so the call to atom([]) and is_list([]) both evaluate to true; this won't help you throw away empty lists as opposed to character atoms.

回复收藏 0 原文

空‖城人不在 2025-01-07 22:53:42

您可以保持您的列表开放式，在其末尾有一个指向其开头的指针，并在其末尾有一个“结束孔/自由指针”（即 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,c],[[d],[],[e]]]), R, [1,2,3]).
R = [a, b, c, d, e, 1, 2, 3].

19 ?- phrase(flattn([a,[b,X],[[d],[],[e]]]), [a, b, c, d, e]).
X = c.

如果定义是完全声明性的，那么最后一个也应该通过 X=[c] 成功； X=[[],c]; ...; X=[[c]]; ...;唉，事实并非如此。

（edit2：简化了两个版本，感谢 @mat 的评论！）

You can maintain your lists open-ended, with both a pointer to its start, and an "ending hole ⁄ free pointer" (i.e. logvar) at its end, which you can then instantiate when the end is reached:

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

You then call it as

flatten2( A, B):- flatten2( A, B, []).

That way there's no need to use reverse anywhere. This technique is known as "difference lists", but it's much easier just to think about it as "open-ended lists" instead.

update: This is much easier coded using the dcg syntax. Since it is unidirectional (the first argument must be fully ground), why not use cuts after all:

flattn([]) --> [], !.
flattn([A|T]) --> {\+is_list(A)}, [A], !, flattn(T).
flattn([A|T]) --> flattn(A), flattn(T).

Testing:

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,c],[[d],[],[e]]]), R, [1,2,3]).
R = [a, b, c, d, e, 1, 2, 3].

19 ?- phrase(flattn([a,[b,X],[[d],[],[e]]]), [a, b, c, d, e]).
X = c.

If the definition were fully declarative, the last one should've succeeded also with X=[c] ; X=[[],c] ; ... ; X=[[c]] ; ...; alas, it isn't.

(edit2: simplified both versions, thanks to @mat's comments!)

回复收藏 0 原文

情深如许 2025-01-07 22:53:42

Prolog 的列表符号是非常简单的 prolog 术语之上的语法糖。 Prolog 列表如下表示：

空列表由原子[] 表示。为什么？因为这看起来像是空列表的数学符号。他们本可以使用像 nil 这样的原子来表示空列表，但他们没有。
非空列表由术语 .\2 表示，其中第一个（最左边）参数是列表的 head ，第二个（最右边）参数参数是列表的尾，递归地，它本身就是一个列表。

一些示例：

空列表：[] 表示为原子：
<前><代码>[]
一个元素的列表，[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( [_|_] ) .

Prolog's list notation is syntactic sugar on top of very simple prolog terms. Prolog lists are denoted thus:

The empty list is represented by the atom []. Why? Because that looks like the mathematical notation for an empty list. They could have used an atom like nil to denote the empty list but they didn't.
A non-empty list is represented by the term .\2, where the first (leftmost) argument is the head of the list and the second (rightmost) argument is the tail of the list, which is, recursively, itself a list.

Some examples:

An empty list: [] is represented as the atom it is:
```
[]
```
A list of one element, [a] is internally stored as
```
.(a,[])
```
A list of two elements [a,b] is internally stored as
```
.(a,.(b,[]))
```
A list of three elements, [a,b,c] is internally stored as
```
.(a,.(b,.(c,[])))
```

Examination of the head of the list is likewise syntactic sugar over the same notation:

[X|Xs] is identical to .(X,Xs)
[A,B|Xs] is identical to .(A,.(B,Xs))
[A,B] is (see above) identical to .(A,.(B,[]))

Myself, I'd write flatten/2 like this:

%------------------------
% 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( [_|_] ) .

回复收藏 0 原文

日裸衫吸 2025-01-07 22:53:42

在 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

Building on if_//3 and list_truth/2, we can implement myflatten/2 as follows:

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)
   ).

Sample queries (taken from other answers, and comments to answers):

?- 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 and not(nil_or_cons_t) describe have same solutions, but the solution order differs. Consider:

?- 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

回复收藏 0 原文

时光是把杀猪刀 2025-01-07 22:53:42

为了完整性，这是一个基于累加器的版本：

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

Here's an accumulator based version for completeness:

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

回复收藏 0 原文

奢望 2025-01-07 22:53:42

没有任何其他谓词，仅具有尾递归。

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

Without any other predicate, with tail-recursion only.

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

回复收藏 0 原文

~没有更多了~