prolog - 检查列表是否在 Prolog 中被展平

Question

给定一个列表，我想使用 prolog 检查给定列表是否平坦。

Example:-

1. ?- is_flat([1,2,3]) should return true

2. ?- is_flat([1,f,2,r(p),8]) should return true

3. ?- is_flat([1,2,[3,e,w],u]) should return false

我正在考虑逻辑，即遍历列表的每个元素，然后使用 is_list 检查头部是否为列表。我试过：

is_flat([]).
is_flat([H|T]) :- is_list(H), is_flat(T).

但我不认为我走在正确的轨道上。请建议我如何解决这个问题。

标签： prolog

Answer 1

给出的方法是正确的，我们只需要“反转真值”is_list/2测试（或者更准确地说，一旦遇到列表就宣布证明失败）。为了更好地衡量，我添加了一个完全不必要的消息编写指令：

is_flat([]).
is_flat([X|Xs]) :- 
   format("Examining ~q\n",[X]),
   \+ is_list(X),
   is_flat(Xs).

然后：

?- is_flat([a,b,c]).
Examining a
Examining b
Examining c
true.

但：

?- is_flat([a,[x,y,z],c]).
Examining a
Examining [x,y,z]
false.

使用maplist/2

这可以用 紧凑地完成maplist/2，它将谓词应用于每个元素，并在此类应用程序出现故障时立即中断：

another_is_flat(List) :- maplist(not_is_list,List).

not_is_list(L) :- \+ is_list(L).

然后：

?- another_is_flat([a,b,c]).
true.

?- another_is_flat([a,[x,y,z],c]).
false.

使用forall/2

或者使用 CapelliC 的解决方案。forall/2正是为此而设计的：它\+is_list(E)为每个成功的条件（在这种情况下）执行测试（在这种情况下， member(E,L)），并且表现得像短路 AND（在成功时也不会留下意外绑定）：

another_another_is_flat(L) :- forall(member(E,L),\+is_list(E)).

然后：

?- another_another_is_flat([a,b,c]).
true.

?- another_another_is_flat([a,[x,y,z],c]).
false.

边缘案例：

?- another_another_is_flat([]) .
true.

“空洞的真相”：正确接受空列表。