CODEWITHSUNDEEP
listprologminimum
UnSat
UnSat

Reputation: 1407

How to find the minimum of the list of the terms?

I have a list of terms as below

[t('L', 76), t('I', 73), t('V', 86), t('E', 69)]

I want to write a predicate in prolog so that it will return the term with minimum second value. i.e. from above list it should return t('E', 69)

Below is what I tried. But this is not working.

minChar(L, Min) :-
    setof(t(_, A), member(t(_, A), L), Li),
    Li = [Min|_].

Here is the output it gives for above input.

?- minChar([t('L', 76), t('I', 73), t('V', 86), t('E', 69)], Min).
Min = t(_G14650, 69) ;
Min = t(_G14672, 73) ;
Min = t(_G14683, 76) ;
Min = t(_G14661, 86).

Upvotes: 1

Views: 1025

Answers (3)

joel76
joel76

Reputation: 5615

You are a beginner in Prolog, so try to think Prolog.

What is the minimum of a list ? An element of this list, and no other element of this list is smaller. So you can write

my_min(L, Min) :-
    member(Min, L),
    \+((member(X, L), X < Min)).

One will say : "it's not efficient !". Yes, but I think it's a good way to learn Prolog.

You should adapt this code to your case.

EDIT I said adapt :

min_of_list(L, t(X,Y)) :-
    member(t(X, Y), L),
    \+((member(t(_, Z), L), Z < Y)).

Upvotes: 1

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476554

Instead of using a setof which runs in O(n log n) (at least), you can also write a minChar predicate yourself:

minChar([X],X) :-
    !.
minChar([t(_,V1)|T],t(A2,V2)) :-
    minChar(T,t(A2,V2)),
    V2 < V1,
    !.
minChar([X|_],X).

Or you could further boost performance, by using an accumulator:

minChar([X|T],Min) :-
    minChar(T,X,Min).

minChar([],X,X).
minChar([t(A2,V2)|T],t(_,V1),Min) :-
     V2 < V1,
     !,
     minChar(T,t(A2,V2),Min).
minChar([_|T],X,Min) :-
    minChar(T,X,Min).

The code works as follows: first you unify the list as [X|T], (evidently there must be at least one items, otherwise there is no minimum). Now you take X as the first minimum. You iterate over the list, and at each time you compare t(A2,V2) (the new head of the list), with t(A1,V1) (the currently found minimum). If the second attribute V2 is less than V1, we know we have found a new minimum, and we continue our search with that term. Otherwise, the quest is continued with the old current minimum. If we reach the end of the list, we simply return the current minimum.

Another performance hack, is placing the empty list case as the last one, and place the the current minimum is the smallest case first:

minChar([t(_,V2)|T],t(A1,V1),Min) :-
     V1 <= V2,
     !,
     minChar(T,t(A1,V1),Min).
minChar([X|T],_,Min) :-
    minChar(T,X,Min).
minChar([],X,X).

This because Prolog always first executes the predicates in the order defined. It will occur only once that you reach the empty list case (at the end of the list). And after a will, the odds of finding a smaller value will be reduced significantly.

Upvotes: 4

Oskar
Oskar

Reputation: 899

As lurker says, predicates can't start with a capital letter, so fix that first.

There are two basic problems here: first off all, the two underscores in your second line refers to different variables, so setof/3 doesn't know that you want the same variable both in the template and in the member/2 call.

Second, setof sorts the result (which is why you can extract the minimum like that), but the way you've constructed the template, it will sort it incorrectly. Sorting in swi-prolog uses the standard order of terms definition, and in your case, you're sorting compound terms of the type t(A, B), where A is an atom and B is a number. This will sort it lexicographically first on A and then on B, which is not what you want, you want to sort on B.

The standard trick here when you want to sort things with a key that isn't identical to the term itself is to extract the key you want, bind it with the (-)/2 functor, and then sort it. So, for your example, this should work: 

minChar(L, Min) :- 
  setof(B-t(A, B), member(t(A, B), L), Li),
  Li = [_-Min|_].

Remember here that in Prolog, when you say X - Y, you're not actually doing any subtraction, even though it looks you are. You are simply binding X and Y together using the (-)/2 functor. It only does subtraction if you specifically ask it to, but using some operator that forces arithmetic evaluation (such as =:=, <, > or is, for instance). This is why 1+1 = 2 is false in Prolog, because = is a unification operator, and doesn't do any arithmetic evaluation.

To be clear: you don't have to use - for this, you can use whatever functor you like. But it's traditional to use the minus functor for this kind of thing.

Edit: also, setof/3 will backtrack over any free variables not found in the template, and since the two underscores don't refer to the same free variables, it will backtrack over every possible assignment for the second underscore, and then throw that result away and assign a new free variable for the first underscore. That's why you can backtrack over the result and get a bunch of anonymous variables that you don't know where they came from.

Upvotes: 4

Related Questions