prolog - Encontrar el entero máximo en una lista en prólogo

max

Question

Estoy tratando de encontrar el número máximo en una lista. Sé que hay varias soluciones disponibles en línea, pero creo que la mejor manera de aprender es implementarlas por mi cuenta.

Escribí el siguiente código:

max([X],X).
max([H|T],Res):-
    (  H >= Res
    -> max(T,Res1), Res1 = H
    ;  max(T,Res)
    ).

¿Alguien puede señalar mi error? No soy capaz de resolverlo.

Answer 1

Considere el código presentado en mi respuesta a la pregunta relacionada " Encontrar el máximo en una lista - Prólogo ".

El código en la respuesta mencionada se basa en el meta-predicado foldl/4 .

Aquí, muestro cómo hacerlo con los metadatos combine/3 y reduce/3 . Primero, combine/3 :

:- meta_predicate combine(3,?,?).
combine( _ ,[]    ,[]).
combine(P_3,[X|Xs],Ys) :-
   list_prev_combined_(Xs,X,Ys,P_3).

:- meta_predicate list_combined_(?,?,3).
list_combined_([]    ,[], _ ).
list_combined_([X|Xs],Ys,P_3) :-
   list_prev_combined_(Xs,X,Ys,P_3).

:- meta_predicate list_prev_combined_(?,?,?,3).    
list_prev_combined_([]     ,X ,[X]   , _ ).
list_prev_combined_([X1|Xs],X0,[Y|Ys],P_3) :-
   call(P_3,X0,X1,Y),
   list_combined_(Xs,Ys,P_3).

Sobre la base de combine/3 podemos definir reduce/3 siguiente manera:

:- meta_predicate reduce(3,?,?).
reduce(P_3,[X|Xs],V) :- 
   list_aka_prev_reduced_(Xs,Xs,X,V,P_3).

:- meta_predicate list_aka_prev_reduced_(?,?,?,?,3).
list_aka_prev_reduced_([]   ,_ ,V ,V, _ ).
list_aka_prev_reduced_([_|_],Xs,X0,V,P_3) :-
   list_prev_combined_(Xs,X0,Ys,P_3),
   reduce(P_3,Ys,V).

En cuanto a la forma de sus respectivos árboles de prueba, foldl/4 es similar a las listas, mientras que combine/3 y reduce/3 son similares a los árboles binarios equilibrados.

Considere las siguientes consultas:

:- use_module(library(lambda)).

?- foldl(/X^Y^f(X,Y)^true, [1,2,3,4,5,6,7], 0,S).
S = f(7,f(6,f(5,f(4,f(3,f(2,f(1,0))))))).

?- combine(/X^Y^f(X,Y)^true, [1,2,3,4,5,6,7], S).
S = [f(1,2),f(3,4),f(5,6),7].

?- reduce(/X^Y^f(X,Y)^true, [1,2,3,4,5,6,7], S).
S = f(f(f(1,2),f(3,4)),f(f(5,6),7)).

reduce/3 se basa en combine/3 y lo aplica hasta que todos los elementos se hayan combinado en uno:

?- combine(/X^Y^f(X,Y)^true, [1,2,3,4,5,6,7], S). S = [f(1,2),f(3,4),f(5,6),7]. ?- combine(/X^Y^f(X,Y)^true, [f(1,2),f(3,4),f(5,6),7], S). S = [f(f(1,2),f(3,4)),f(f(5,6),7)]. ?- combine(/X^Y^f(X,Y)^true, [f(f(1,2),f(3,4)),f(f(5,6),7)], S). S = [f(f(f(1,2),f(3,4)),f(f(5,6),7))]. ?- reduce(/X^Y^f(X,Y)^true, [1,2,3,4,5,6,7], S). S = f(f(f(1,2),f(3,4)),f(f(5,6),7)).

Vamos a usarlo para obtener el entero máximo Max en la lista [1,5,2,4,3,8,7,2] :

:- use_module(library(clpfd)). ?- reduce(/X^Y^XY^(XY #= max(X,Y)), [1,5,2,4,3,8,7,2], Max). Max = 8. ℅ If you can''t use clpfd, simply use is/2 instead of (#=)/2: ?- reduce(/X^Y^XY^(XY is max(X,Y)), [1,5,2,4,3,8,7,2], Max). Max = 8.

Answer 2

No estás asegurando que Res se crea una instancia. No necesitas un predicado auxiliar para hacer eso. Puede hacer la llamada recursiva antes del control si Res es mayor que H donde Res es el número entero más grande de T

Puede usar -> , pero no es necesario. Pero si no lo hace, un poco más de retroceso estaría involucrado.

Si intenta permanecer más en su ruta con recurrencia después del control, necesitará un predicado auxiliar, como ha sugerido lurker .

Editar: Dado que la respuesta se acepta ahora, aquí están las tres sugerencias implementadas:

max1([H|T], Y):-  % with the -> operator, call first
    max1(T,X),
    (H > X ->
     H = Y;
     Y = X).
max1([X],X).


max2([H|T], Y):-  % without the -> operator, call first (this might be very inefficient)
    max2(T,Y),
    H < Y.
max2([H|T], H):-
    max2(T,Y),
    H >= Y.
max2([X],X).


max3([H|T], Y) :- max_(T,H,Y).            % with helper predicate
max_([H|T],HighestNow,Highest):-          % call after the test
    (H > HighestNow -> max_(T,H, Highest)
     ;
     max_(T,HighestNow,Highest)).
max_([],X,X).