Prolog max dans une liste

Question

mymax([], 'list_is_empty'). 
mymax([Head | []], Max) :- (Max >= Head). 
mymax([Head | List], Max) :- (Max > Head), mymax(List,Max). 

Cela semble fonctionner correctement avec des requêtes telles que MyMax ([1,5,3], 5), etc., mais est incapable de trouver une valeur maximale de son propre et donne la erreur suivante:

ERROR: >/2: Arguments are not sufficiently instantiated 

Je comprends en quelque sorte pourquoi c'est le cas, mais je ne peux pas le verbaliser. Cela peut-il être corrigé ou mon algorithme est-il totalement incorrect?

Answer 1

L'erreur est due au fait que Max n'est toujours pas lié lorsque vous comparez avec Head.

Vous pouvez simplifier ainsi:

mymax([Max], Max). 
mymax([Head | List], Max) :- 
    mymax(List, MaxList), 
    (Head > MaxList -> Max = Head ; Max = MaxList). 

modifier

J'ai essayé de minimiser la modification de votre code, mais, comme @mat a fait remarquer, qui fonctionnerait seulement pour une liste de expressions, par exemple, les nombres. Ensuite, vous pouvez écrire

1 ?- mymax([4+1, 3+3], N). 
N = 3+3 

Si vous n'êtes pas sûr de la liste » domaine (à savoir le type de ses éléments), pourrait être préférable d'utiliser l'opérateur term comparison:

(Head @> MaxList -> ...) 

mais maintenant:

?- mymax([4+1, 3+3], N). 
N = 4+1 

Answer 2

Si vous voulez le rendre facile, trier, inverse, prendre la tête:

mymax(List, Max) :- 
    sort(List, Sorted), 
    reverse(Sorted, [Max|_]). 

Sinon, prenez le premier élément et définissez-le pour être le plus grand (jusqu'à présent). Ensuite, regardez dans le reste de la liste et si vous trouvez un élément plus grand que le plus grand courant, remplacez votre max actuel par celui-ci. C'est ce que fait @CapelliC (en quelque sorte), en utilisant un prédicat de contrôle if-then-else.

Une façon de le faire sans à l'aide d'un if-then prédicat, en utilisant des clauses sous-jacentes à la place, et en profitant du prédicat ISO compare:

mymax([First|Rest], Max) :- 
    mymax_1(Rest, First, Max). 
mymax_1([], Max, Max). 
mymax_1([This|Rest], Current, Max) :- 
    compare(Cmp, This, Current), 
    mymax_2(Cmp, Rest, This, Current, Max). 
mymax_2(>, Rest, This, _, Max) :- 
    mymax_1(Rest, This, Max). 
mymax_2(=, Rest, _, Current, Max) :- 
    mymax_1(Rest, Current, Max). 
mymax_2(<, Rest, _, Current, Max) :- 
    mymax_1(Rest, Current, Max). 

Mais ce style de prédicats d'écriture n'est pas très populaire , probablement parce que c'est trop explicite et implique trop de taper. D'un autre côté, il est récursif et déterministe. Il ne se casse pas aussi lorsque vous passez une variable comme premier argument:

?- mymax(L, 13). 

Vous pouvez également consulter la mise en œuvre de max_list/2 et max_member/2 de la bibliothèque standard de toute implémentation Prolog open-source (SWI-Prolog par exemple) pour une approche plus pragmatique (mais en utilisant toujours if-then-else).

Answer 3

Pour trouver le maximum d'une liste que vous pouvez dire que c'est un membre de cette liste, et il n'y a aucun élément de cette liste plus grande qu'elle:

my_max(L, V) :- 
    member(V, L), 
    \+((member(X, L), X > V)). 

Answer 4

opérateurs arithmétiques de faible niveau (>=)/2 et (>)/2 ne fonctionnent que lorsque leurs arguments sont instanciés à concrètes expressions arithmétiques. Pour que votre programme fonctionne également pour des requêtes plus générales comme ?- mymax(List, Max)., pensez à utiliser les contraintes , disponibles dans toutes les principales implémentations de Prolog.

Par exemple, en utilisant des contraintes de domaine finis dans SICStus ou SWI-Prolog:

:- use_module(library(clpfd)). 

list_max([L|Ls], Max) :- 
    list_max_(Ls, L, Max). 

list_max_([], Max, Max). 
list_max_([L|Ls], Max0, Max) :- 
    Max1 #= max(Max0,L), 
    list_max_(Ls, Max1, Max). 

ou de manière équivalente, en utilisant foldl/4:

:- use_module(library(clpfd)). 

list_max([L|Ls], Max) :- foldl(x_y_max, Ls, L, Max). 

x_y_max(X, Y, Max) :- Max #= max(X, Y). 

Exemple requête et des résultats:

?- list_max(Ls, Max). 
Ls = [Max] ; 
Ls = [_G551, _G554], 
Max#>=_G551, 
Max#=max(_G551, _G554), 
Max#>=_G554 ; 
Ls = [_G636, _G639, _G642], 
_G657#>=_G636, 
_G657#=max(_G636, _G639), 
Max#>=_G657, 
_G657#>=_G639, 
Max#=max(_G657, _G642), 
Max#>=_G642.