I am working through some list handling exercises (from Tate’s Seven Languages in Seven Weeks. I have already done a reverseList predicate I’m very proud of.

Now I try to do a minOfList predicate. I got it working with the following code:

minOfList([A], A).
minOfList([H|T], M) :- minOfList(T, E2), M is min(H, E2).

So far so good. However I had started out with a version where I had swapped the two premises in the main rule:

minOfList([H|T], M) :- M is min(H, E2), minOfList(T, E2).

Then I get on querying an “Arguments are not sufficiently instantiated” error. This surprises me. The , between the two premises is an and which by bare logic terms should be commutative (i.e. swappable).

The conjunction, “,” is not commutative as long as you have a side effect. Same goes for the “and” or “&&” between boolean expressions in the condition of an “IF” in any procedural language. In this case, unifying the left side of the is/2 with the result of evaluating the right side is the side effect.

The obvious solution is to keep a running minimum. The extra variable is usually called an “accumulator”. It would look like this.

Aha! Interesting! So in the code with the correct order E2 is “instantiated” through the first premise minOfList(T, E2) when it gets passed to M is min(H, E2). So order does matter.

Sorry, I don’t understand this one: What’s the reference?

It is an ancient dead-tree book that is hard to get (it costs ~50 dollars). Maybe your library has it.

Another way to not evaluate until the end (when everything on the right side of the is/2 is instantiated) is to just build the whole expression during the list traversal and evaluate it at the end.

my_min(List, Min) :-
my_min_1(List, Min_expr),
Min is Min_expr.
my_min_1([Min], Min).
my_min_1([H|T], Min) :-
Min = min(Min0, H),
my_min_1(T, Min0).

You can now switch the order of the last two lines and you will get the same result.

EDIT: so obviously you also have a side effect when you unify (using the =/2) but it doesn’t matter because unification does not care about how the two sides are instantiated: you can have free variables on either side.

PS: You cannot easily write practical programs in Prolog if you insist on staying entirely in “logic programming”. Once you are done with the “Seven Languages in Seven Weeks” (a presumptuous title indeed ) you can try “The Art of Prolog” by Sterling and Shapiro. One thing that sets it apart from other books is that it discusses in some depth the difference between Logic Programming and Prolog programming. It is a distinction that most authors swipe under the rug.

As other people have pointed out, is/2 requires the right-hand side to be grounded. For more “logical” arithmetic, you can use library(clpfd), which would let you use #=/2 instead of is/2 and would work with both orders.