CODEWITHSUNDEEP
recursionprolog
jdoggg
jdoggg

Reputation: 39

Understand a simple recursion in prolog

I have the following Prolog from the book mastering Prolog, and I'm trying to learn some simple recursion.

mins_to_hours(In, H, M):-
    In<60,
    H = 0,
    M is In.
mins_to_hours(In, H, M):-
    In>=60,
    In1 is In-60,
    H1 is H+1,
    mins_to_hours(In1, H1, M).

I'm not entirely sure why it doesn't work and I've been fiddling with it for hours. Any help even to point me in the right direction is much appreciated. Thanks in advance.

Upvotes: 1

Views: 455

Answers (1)

mat
mat

Reputation: 40768

A major difficulty you are facing in this example is the so-called modedness of low-level arithmetic predicates. For example, let us try the most general query with the code you posted:

?- mins_to_hours(In, H, M).
ERROR: Arguments are not sufficiently instantiated

To get rid of this shortcoming, I first replace the low-level predicates with CLP(FD) constraints, which are available in all major Prolog systems and simplify reasoning over your code.

For this, I simply replace (<)/2 by (#<)/2, (is)/2 by (#=)/2 etc. (depending on your Prolog system, you may also still have to import a library for this):

mins_to_hours(In, H, M):-
    In #< 60,
    H = 0,
    M #= In.
mins_to_hours(In, H, M):-
    In #>= 60,
    In1 #= In-60,
    H1 #= H+1,
    mins_to_hours(In1, H1, M).

Now, let us again try the most general query, where all arguments are fresh variables:

?- mins_to_hours(In, H, M).
In = M,
H = 0,
M in inf..59 ;
H = -1,
In in 60..119,
M+60#=In,
M in 0..59 ;
H = -2,
In in 120..179,
_5238+60#=In,
_5238 in 60..119,
M+60#=_5238,
M in 0..59 .

Here, it seems very odd that H can assume negative values!

Let us try a few concrete cases:

?- mins_to_hours(30, H, M).
H = 0,
M = 30 ;
false.

This still seems quite OK!

?- mins_to_hours(60, H, M).
H = -1,
M = 0 ;
false.

This already seems much less OK!

With a bit of practice, it is easy to see the reason: In the second clause, you are inadvertently confusing the roles of H and H1! Suppose we write the second clause like this:

mins_to_hours(In, H, M):-
    In #>= 60,
    In1 #= In-60,
    H #= H1+1,
    mins_to_hours(In1, H1, M).

Then we get:

?- mins_to_hours(60, H, M).
H = 1,
M = 0 ;
false.

And for two more cases:

?- mins_to_hours(500, H, M).
H = 8,
M = 20 ;
false.

?- mins_to_hours(1000, H, M).
H = 16,
M = 40 ;
false.

Seems pretty nice!

Note that if you stick to lower-level arithmetic, you cannot that easily correct the mistake: Using predicates like (<)/2 and (is)/2 requires that you also take into account the actual execution order of Prolog, and this is much too hard for almost all beginners. I highly recommend you use CLP(FD) constraints instead, since they let you readily try the effect of different goal orders, while keeping the relation correct and general.

Upvotes: 3

Related Questions