CODEWITHSUNDEEP
prolog
Rocky
Rocky

Reputation: 91

Prolog encoded integers, less/2(X, Y) predicate

A question states the following:

In Prolog, non-negative integers can be encoded as numerals given by 0 and its successors (with, for example, the numeral s(s(s(0))) encoding 3).

numeral(0).
numeral(s(X)) :- numeral(X).

Define the predicate less/2(X, Y) that holds when X and Y are numerals encoding non-negative integers x and y such that x < y. For example,

?- less(0, s(0)).
yes.
?- less(s(s(0)), s(s(0))).
no.

I have been able to come up with a solution for this question, however, it suffers from a limitation. Here is my solution:

less(X, s(X)) :- numeral(X).
less(X, Z) :- less(X, Y), less(Y, Z).

This solution correctly outputs a yes for inputs that satisfy this predicate. However, for inputs that expect a no, this solution seems to enter an endless recursion of some sort, and the program just keeps running, rather than outputting a no.

Please help.

Upvotes: 1

Views: 111

Answers (2)

Duda
Duda

Reputation: 3746

I would do it like this:

less(0, s(Y)) :- numeral(Y).
less(s(X), s(Y)) :- less(X, Y).

?- less(0, s(0)).
true.

?- less(s(s(0)), s(s(0))).
false.

The idea is that 0 is less than any s(Y), where Y is a numeral. If X is not 0, then X is s(X'), and X = s(X') is less than Y = s(Y') iff X' is less than Y'.

This does only work if both X and Y are numerals. If X is not a numeral then it will get stuck somewhere in the recursion and "returns" false. Same for Y, except that there need to be a test at the end if the rest of Y is a numeral.

Upvotes: 3

devck
devck

Reputation: 341

Try this:

less2(X, s(X)) :- numeral(X).
less2(X, s(Y)) :- less2(X,Y).

Seems to work for me; your solution could recurse endlessly though, because if there exists no value of Y between X and Z it will simply try everything under the sun.

Upvotes: 2

Related Questions