Prolog: prédicat pour un maximum sans accumulateur

Question

Est-il possible de créer un prédicat max/2sans un accumulateur pour que max(List, Max) est vrai si et seulement si Max est la valeur maximale de List (une liste d'entiers)?

Answer 1

Oui, vous pouvez calculer le maximum après l'étape récursive. Comme:

max([M],M).   % the maximum of a list with one element is that element. 
max([H|T],M) :- 
    max(T,M1),  % first calculate the maximum of the tail. 
    M is max(H,M1). % then calculate the real maximum as the max of 
        % head an the maximum of the tail. 

Ce prédicat fonctionnera sur des points flottants par exemple. Néanmoins, il est préférable d'utiliser un accumulateur puisque la plupart des interpréteurs Prolog utilisent optimisation de l'appel de fin (TCO) et prédicats avec accumulateurs ont tendance à travailler avec des appels de queue. Par conséquent, les prédicats avec TCO n'obtiennent généralement pas d'exception de dépassement de pile si vous souhaitez traiter d'énormes listes.

Comme @Lurker says, is ne fonctionne que si la liste est complètement mise à la masse: c'est une liste finie et tous les éléments sont mis à la terre. Vous pouvez toutefois utiliser la programmation logique de contrainte de Prolog package clp(fd):

:- use_module(library(clpfd)). 

max([M],M).   % the maximum of a list with one element is that element. 
max([H|T],M) :- 
    max(T,M1),  % first calculate the maximum of the tail. 
    M #= max(H,M1). % then calculate the real maximum as the max of 
        % head an the maximum of the tail. 

Vous pouvez alors pour les appels d'instance:

?- max([A,B,C],M),A=2,B=3,C=1. 
A = 2, 
B = M, M = 3, 
C = 1 ; 
false. 

Alors après l'appel max/2, par terre A, B et C, nous obtenons M=3.

Answer 2

Ni le prédicat standard est/2 ni un prédicat CLP (FD) (# =)/2 peut faire des mathématiques ici. Alors qu'à la fin, pour certaines applications telles que la géométrie exacte, ils pourraient ne pas convenir. Pour faire un point, considérons un exemple et l'alternative d'un système d'algèbre informatique (CAS). Je fais la démonstration avec le nouveau prototype Jekejeke Minlog 0.9.2 qui fournit CAS à partir de Prolog.

Nous avons au préalable deux prédicats eval_keys/2 et min_key/2, leur code se trouve en annexe dans ce post. Illustrons ce que ce prédicat fait, d'abord avec entier. Le premier prédicat est tout simplement les clés d'une liste de paires évaluées:

Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.3.25-3-gc3a87c2) 
Copyright (c) 1990-2016 University of Amsterdam, VU Amsterdam 

?- eval_keys([(1+3)-foo,2-bar],L). 
L = [4-foo,2-bar] 

Le second prédicat prend cette première valeur où la clé est minimale:

?- min_key([4-foo,2-bar],X). 
X = bar 

Maintenant, regardons d'autres valeurs clés, nous allons utiliser des racines carrées, qui appartiennent au domaine des nombres algébriques. Les nombres algébriques sont irrationnels et ne s'adaptent donc jamais dans un flotteur. Nous obtenons donc pour le nouvel exemple le résultat foo:

?- eval_keys([(sqrt(98428513)+sqrt(101596577))-foo,sqrt(400025090)-bar],L). 
L = [20000.62724016424-foo, 20000.627240164245-bar]. 

?- min_key([20000.62724016424-foo, 20000.627240164245-bar], X). 
X = foo. 

CLP (FD) ne dispose que de nombres entiers et il n'y a aucun moyen direct pour représenter des nombres algébriques. D'un autre côté, de nombreux systèmes CAS supportent les radicaux.Notre prototype soutient même la comparaison d'entre eux afin que nous puissions obtenir le résultat exact bar:

Jekejeke Prolog 2, Runtime Library 1.2.2 
(c) 1985-2017, XLOG Technologies GmbH, Switzerland 

?- eval_keys([(sqrt(98428513)+sqrt(101596577))-foo,sqrt(400025090)-bar],L). 
L = [radical(0,[98428513-1,101596577-1])-foo, 
    radical(0,[400025090-1])-bar] 

?- min_key([radical(0,[98428513-1,101596577-1])-foo, 
    radical(0,[400025090-1])-bar],X). 
X = bar 

Ce bar est le résultat exact peut être vu par exemple en utilisant une calculatrice multi-précision. Si on double la précision, nous voyons en effet que la dernière racine carrée est l'un et pas petites salles la somme des racines carrées:

?- use_module(library(decimal/multi)). 
% 7 consults and 0 unloads in 319 ms. 
Yes 

?- X is mp(sqrt(98428513)+sqrt(101596577), 32). 
X = 0d20000.627240164244658958331341095 

?- X is mp(sqrt(400025090), 32). 
X = 0d20000.627240164244408966171597261 

Mais un CAS besoin de ne pas procéder de cette façon. Par exemple, notre Prolog implementation utilise une méthode inspirée du polynôme de Swinnerton-Dyer pour comparer des expressions radicales, ce qui fonctionne purement symbolique.

Annexe Test Code:

% :- use_module(library(groebner/generic)). /* to enable CAS */ 

eval_keys([X-A|L], [Y-A|R]) :- Y is X, eval_keys(L, R). 
eval_keys([], []). 

min_key([X-A|L], B) :- min_key(L, X, A, B). 

min_key([X-A|L], Y, _, B) :- X < Y, !, min_key(L, X, A, B). 
min_key([_|L], X, A, B) :- min_key(L, X, A, B). 
min_key([], _, A, A).