Prolog program: another way to define a functor

Question

In my last exam I had to write a Prolog predicate called double/2, according to the following instructions: double(X, Y) should be true if Y is a list of integers of the same length of X, in which every even number of X is replace with its double. So that, for example, the query double([1, 3, 2, 4], X). should outcome X = [1, 3, 4, 8].

I was allowed for simplicity to use the functor even/1, without defining it (actually it is very easy to define it), which is true when the argument is an even number, and false otherwise. I actually ended up writing the program using also the functor odd/1. But my professor said me: "You could have written it using only even, it's not necessary to use also odd!" So I wonder how I could have written it this way.

What I wrote is the following:

double([], []).
double([N|L], [N|D]) :- odd(N), !, double(L, D).
double([N|L], [M|D]) :- even(N), M is 2*N, double(L, D).

Remark: if I remove even(N) from the last line of code (so if I use only odd(N), which is practically the same as using only even(N), because I use only one of them), then the program still works. But this is not a desirable solution, because this way the 'cut' becomes a red cut (in my program it is a green cut).

Answer 1

You can use instead the standard if-then-else control construct:

double([], []).
double([N|L], [M|D]) :-
    (   even(N) ->
        M is 2*N
    ;   M is N
    ),
    double(L, D).

A performance advantage of this alternative solution (besides avoiding repeating computations when an integer is not odd) is that, assuming your Prolog system implements first-argument indexing (as most do), the correct clause for the double/2 predicate will always be picked at each call without creating a choice-point (assuming that the predicate is called with the first argument instantiated but this or your definition definition would not work otherwise). Note that, in the first clause, the first argument is an atom (the empty list) while in the second clause the argument is a (non-empty) list. First argument indexing is used to avoid trying clauses during a proof that cannot be used to resolve the current goal.

Answer 2

If you are just interested in a correct solution, take @PauloMoura's solution. Here is what I think the intention of this exercise was. Take your original program, it seems (at first sight), that one can remove the goal even(N) in the second clause.

But before that, let me make clear that the predicate name doubles/2 is a misnomer. I'd rather say list_semidoubled/2...

odd(N) :-
   N mod 2 =:= 1.

double([], []).
double([N|L], [N|D]) :-
   odd(N), !, double(L, D).
double([N|L], [M|D]) :-
   % even(N),
   M is 2*N, double(L, D).

However, the cut above does a little bit more than we expected. It does not cut when odd(N) is true alone, but there is a tiny little extra condition that sneaked into our program. Do you see it? Let's have a look at the relevant part:

double([N|L], [N|D]) :-
   odd(N), !, ...

There is odd(N), but look above! In the head another condition is lying there. And it waits until it can wreak havoc! The "hidden" condition is:

If N is equal (unifies) to the first element in the second argument!

Let's try it out!

?- double([1], Xs).
Xs = [1].

Worx as expected, does it not. However:

?- double([1], [2]).
true.

Tiens, what is happening here? That should fail!

A predicate that behaves in that way lacks steadfastness. We would expect the query to fail, for Prolog did not show us this solution.

So the cut above does not always cut as you expected, but a little less than that. Errors as these are often quite difficult to locate, so it is a good idea to avoid them right from the beginning. You have several options:

1 Stick to pure, monotonic Prolog

This is probably the best for beginners. And it is not necessarily less efficient. I'd rather:

double(Xs, Ys) :
   maplist(n_semidoubled, Xs, Ys).

n_semidoubled(X, Y) :-
   M is X mod 2,
   (  M = 0,
      Y is X*2
   ;  M = 1,
      Y is X
   ).

This can be improved to — slightly hackerish:

 n_semidoubled(X, Y) :-
    Y is X*(2-X mod 2).

2 Use (\+)/1, once/1, if-then-else

@PaulMoura already showed you one such possibility. Another is to use (\+)/1:

n_semidoubled(X, X) :-
   odd(X).
n_semidoubled(X, Y) :-
   \+odd(X),
   Y is X*2.

3 Reduce the scope of the cut

If you are now still determined to use this construct, try to restructure your program such that the scope of the cut is as local as possible. That is, instead of placing the cut in the recursive rule, rather make a local predicate:

doubles([], []).
doubles([E|Es], [M|Ms]) :-
   n_semidoubled(E, M),
   doubles(Es, Ms).

n_semidoubled(E, M) :-
   odd(E),
   !,
   M is E.
n_semidoubled(E, M) :-
   M is E*2.

---

There is another anomaly in your original program which is independent of the cut issue. Consider:

?- double([1*1],Xs).
   Xs = [1*1].