list - 如何在Prolog的嵌套列表中找到最大元素？

Question

我试图在 Prolog 中找到多层列表中的最大元素(意思是列表中的列表中的列表...)。问题是，我一一检查了所有谓词，它们都有效，但实际上应该解决我的问题的谓词除外。我的方法是展平列表(使其成为单层)并找到该列表中的最大元素。这是我的代码:

is_list([]).

add([],L,L).
add([X|L1],L2,[X|L3]):-add(L1,L2,L3).

maximum([X|O],M) :- max(O,X,M),!.
max([X|O],Y,M) :- X=<Y, max(O,Y,M).
max([X|O],Y,M) :- X>Y, max(O,X,M).
max([],M,M).

flatten([],[]).
flatten([X|L1],[X|L2]):-not(is_list(X)),!,flatten(L1,L2).
flatten([X|L1],L2):-flatten(X,LX),flatten(L1,LL1),add(LX,LL1,L2).

maximum_in_multilayered_list(L,M):-flatten(L,L1),maximum(L1,N), M is N.

出于某种原因，我收到以下错误:

?- maximum_in_multilayered_list([1,[2,3],4],X).
ERROR: Type error: `[]' expected, found `[2,3]' (a list) ("x" must hold one character)
ERROR: In:
ERROR:   [13] [2,3]=<1
ERROR:   [12] max([[2|...],4],1,_7284) at c:/users/ace_m/documents/prolog/bp.pl:47
ERROR:   [11] maximum([1,...|...],_7328) at c:/users/ace_m/documents/prolog/bp.pl:46
ERROR:   [10] maximum_in_multilayered_list([1,...|...],_7366) at c:/users/ace_m/documents/prolog/bp.pl:75
ERROR:    [9] <user>
   Exception: (12) max([[2, 3], 4], 1, _7596) ? creep

我知道问题在于我实际上是将整数列表与整数进行比较，这意味着它们是不兼容的类型，但为什么会这样呢？我究竟做错了什么？

Answer 1

删除您的 is_list([])它有效。

事实上，任何非空列表都不会被视为 is_list/1 Material ，所以对于 [2,3]在 [1,[2,3],4] flatten/2中的第二个条款定义适用，并添加 X = [2,3]原样进入“扁平化”列表 [X|L2] .
但是is_list/1已经是一个内置谓词，它完全符合您的要求。

另一种实现方式是使用 library(aggregate) .
首先，我们定义一个可回溯谓词，它通过嵌套列表枚举所有非列表(即“普通值”)(取自 this 我最近的一些相关答案):

nembr(Z, A) :-    % member in nested lists
  is_list(A), member(B,A), nembr(Z,B)
  ;
  \+ is_list(A), A=Z.

然后

18 ?- nembr(X, [1,[2,3],4]).
X = 1 ;
X = 2 ;
X = 3 ;
X = 4 ;
false.

19 ?- use_module(library(aggregate)).
true

20 ?- L = [1,[2,3],4], aggregate( max(X), nembr(X,L), R).
L = [1, [2, 3], 4],
R = 4.