0

I am fresh in Prolog. And I am trying to write a predicate that finds the Max value and its index of a list of integers. i.e max_list([2,3,4], MAX, INDEX) will yield MAX=4, INDEX=2

Thank you for reply~ My apologize! This is the first time I ask questions in stackoverflow. I could write a predicate to find the maximum or a minimum of a list, but I don't know how to get the exact position the value in the list. I am just trying to comprehend the answers.

repeat
  • 18,496
  • 4
  • 54
  • 166
Li Xinyuan
  • 11
  • 2

4 Answers4

4

Using ...

:- use_module(library(clpfd)).

..., maplist/2, and nth0/3 we define:

zs_maximum_at(Zs,Max,Pos) :-
   maplist(#>=(Max),Zs),
   nth0(Pos,Zs,Max).

Here's the query the OP gave:

?- zs_maximum_at([2,3,4],M,I).
I = 2, M = 4.

OK! ... how about the most general query?

?- zs_maximum_at(Zs,M,I).
  Zs = [M], I = 0, M in inf..sup
; Zs = [ M,_B], I = 0, M #>= _B
; Zs = [_A, M], I = 1, M #>= _A
; Zs = [ M,_B,_C], I = 0, M #>= _B, M #>= _C
; Zs = [_A, M,_C], I = 1, M #>= _A, M #>= _C
; Zs = [_A,_B, M], I = 2, M #>= _A, M #>= _B
; Zs = [ M,_B,_C,_D], I = 0, M #>= _B, M #>= _C, M #>= _D
; Zs = [_A, M,_C,_D], I = 1, M #>= _A, M #>= _C, M #>= _D
...

Edit: What about arithmetic expressions?

  1. We can allow the use of arithmetic expressions by adding an additional goal (#=)/2:

    zs_maximum_at(Zs,Expr,Pos) :-
   maplist(#>=(Max),Zs),
   nth0(Pos,Zs,Expr),
   Expr #= Max.

    Now we can run queries like the following one—but lose monotonicity (cf. this clpfd manual)!

    ?- zs_maximum_at([0+1,1+1,2-0,3-1,1+0],M,I).
  I = 1, M = 1+1
; I = 2, M = 2-0
; I = 3, M = 3-1
; false.

  2. To disable arithmetic expressions we can use length/2 in combination with ins/2:

    zs_maximum_at(Zs,Max,Pos) :-
   length(Zs,_),
   Zs ins inf..sup,
   maplist(#>=(Max),Zs),
   nth0(Pos,Zs,Max).

    Running above query again, we now get:

    ?- zs_maximum_at([0+1,1+1,2-0,3-1,1+0],M,I).
ERROR: Type error: `integer' expected, found `0+1' (a compound)

Note that the issue (of allowing arithmetic expressions or not) is not limited to .
It is also present when using plain-old Prolog arithmetic predicates like is/2 and friends.

Community
  • 1
  • 1
repeat
  • 18,496
  • 4
  • 54
  • 166
2

I'm no Prolog expert myself so this is probably not the most beautiful solution, but this predicate should do what you want:

max_list([X|Xs],Max,Index):-
    max_list(Xs,X,0,0,Max,Index).

max_list([],OldMax,OldIndex,_, OldMax, OldIndex).
max_list([X|Xs],OldMax,_,CurrentIndex, Max, Index):-
    X > OldMax,
    NewCurrentIndex is CurrentIndex + 1,
    NewIndex is NewCurrentIndex,
    max_list(Xs, X, NewIndex, NewCurrentIndex, Max, Index).
max_list([X|Xs],OldMax,OldIndex,CurrentIndex, Max, Index):-
    X =< OldMax,
    NewCurrentIndex is CurrentIndex + 1,
    max_list(Xs, OldMax, OldIndex, NewCurrentIndex, Max, Index).
repeat
  • 18,496
  • 4
  • 54
  • 166
Limmen
  • 1,407
  • 11
  • 17
2

a variation on joel76 answer:

max_list(L, M, I) :- nth0(I, L, M), \+ (member(E, L), E > M).
CapelliC
  • 59,646
  • 5
  • 47
  • 90
  • If anyone else stumbles across this: `\+` is the'[not provable operator', see https://stackoverflow.com/questions/1712034/what-does-mean-in-prolog – Markus Weninger Jun 28 '21 at 11:34
1

Another approach, not very efficient but more "prologish" is to say : What is the max of a list ? it's a member of the list, and no other member of this list is greater than the max ! So :

max_list(Lst, Max, Ind) :-
   member(Max, Lst),
   \+((member(N, Lst), N > Max)),
   % Now, with SWI-Prolog, (may be with other Prolog)
   % nth0/3 gives you the index of an element in a list
   nth0(Ind, Lst, Max).
joel76
  • 5,565
  • 1
  • 18
  • 22
  • 1
    s(X): Ok! Instead of `\+((member(N,Lst), N > Max))` one could use `maplist(>=(Max),Lst)`. (This is not 100% equivalent, but allows using [tag:clpfd] instead of plain-old Prolog integer arithmetic...) – repeat Oct 03 '15 at 08:56