Prolog program: another way to define a functor
In my last exam, I had to write a Prolog predicate titled double/2
according to the following instructions: double(X, Y)
must be true if Y
is a list of integers with the same length X
, into which every even number X
is replaced with its double. So, for example, the request double([1, 3, 2, 4], X).
should come from X = [1, 3, 4, 8].
I was allowed to just use a functor even/1
without defining it (it's actually very easy to define), which is true when the argument is an even number, and false otherwise. I actually ended up writing a program using a functor as well odd/1
. But my professor told me: "You could write this using only, you don't even need to use and weird!" So I'm wondering how I could write it like this.
I wrote 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).
Note: if I remove even(N)
from the last line of code (so if I only use odd(N)
what is practically the same as using only even(N)
because I only use one of them) then the program still works. But this is not a desirable solution, because this makes the "cut" red (in my program, it is a green slice).
source to share
If you're just interested in the right solution, take @PauloMoura's solution. Here's what I think about the intent of this exercise. Take your original program, it seems (at first glance) that the target can be deleted in the second sentence even(N)
.
But first, let me clarify that the predicate name doubles/2
is incorrect. I would 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 is slightly larger than we expected. It doesn't truncate when it odd(N)
is true alone, but there is a small little additional condition that sneaked into our program. Do you see it? Let's take a look at the relevant part:
double([N|L], [N|D]) :-
odd(N), !, ...
There is odd(N)
, but look above! There is another state in the head. And he waits until it can do damage! "Hidden" condition:
If
N
equals (unifies) the first element in the second argument!
Try it!
?- double([1], Xs). Xs = [1].
Worx as expected, isn't it. However:
?- double([1], [2]).
true.
Tyanshi, what's going on here? This must fail!
A predicate that behaves this way has no persistence . We expect the query to fail as Prolog did not show us this solution.
So the cut above does not always cut as you would expect, but slightly less. Errors, as they are often quite difficult to find, so it's a good idea to avoid them from the start. You have several options:
1 Stick to clean, monotonous Prolog
It's probably best for newbies. And it's not necessarily less effective. I would prefer:
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 hackish:
n_semidoubled(X, Y) :-
Y is X*(2-X mod 2).
2 Use (\+)/1
, once/1
, the if-the then-the else
@PaulMoura has already shown 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 incision volume
If you still decide to use this design, try rebuilding your program so that the cut area is as local as possible. That is, instead of placing the cut in a recursive rule, rather do 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 that doesn't depend on the clipping problem. Consider:
?- double([1*1],Xs).
Xs = [1*1].
source to share
Instead, you can use 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).
The performance advantage of this alternative solution (besides avoiding re-computation when the integer is not odd) is that if your Prolog system implements indexing of the first argument (as do most of them), the correct clause for the predicate double/2
will always be fetched on every call without creating a selection point (assuming the predicate is called with the first argument created, but that or your definition of the definition won't work otherwise). Note that in the first sentence, the first argument is an atom (empty list), and in the second, the argument (non-empty) list. The first indexing of the arguments is used to avoid attempting a clause during a proof that cannot be used to resolve the current target.
source to share