两个子句定义,用于查找列表中的最大数量

Question

如何编写两个子句的递归定义来查找列表中的最大值.到目前为止,我写了这个:

 max(L,M):-  

 max([H|T],M):-

max(T,H,M).
max([],M,M).
max([H|T],Y,M):-
   H =< Y,
   max(T,Y,M).
max([H|T],Y,M):-
   H > Y,
   max(T,H,M).

这不起作用,它说有一个我无法看到的语法错误,我知道它也不是两个子句.任何人都知道如何简化它以使其成为两个条款？

Answer 1

就像你一样,我使用谓词的'max'名称.此实现不依赖于任何内置谓词:

max([X],X).
max([X|Xs],X):- max(Xs,Y), X >=Y.
max([X|Xs],N):- max(Xs,N), N > X.

Answer 2

语法错误是由前两个子句没有主体的事实引起的.

要回答您的问题,请注意列表的最大值可以归纳定义如下:

从而,

max_list([H], H).
max_list([H|T], M2) :- 
  max_list(T, M),
  M2 is max(H, M).

此代码使用max/2(SWI-Prolog,GNU-Prolog).请注意,大多数或所有Prolog实现都具有内置函数max_list/2(S,G),因此实际上不需要自己定义它.

编辑: Bakore指出尾部递归实现可能更有效.您可以通过定义带有max_list/3附加参数的谓词来实现此目的C,即到目前为止看到的最大值.

max_list([H|T], M) :- max_list(T, H, M). 

max_list([], C, C).
max_list([H|T], C, M) :- C2 is max(C, H), max_list(T, C2, M).