如何在 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，因此对于 [1,[2,3],4] 中的 [2,3]，第 秒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.

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

How to find max element in nested list in Prolog?

list

prolog

nested-lists

swi-prolog

flatten