CODEWITHSUNDEEP
prolog
Matt Esch
Matt Esch

Reputation: 22956

Understand lists and recursion in Prolog

I'm having a difficult time thinking in Prolog. What is incorrect about this statement:

numberList([], 0).
numberList([H|T], Limit) :-
    H is Limit,
    numberList(T, Limit - 1).

I would like 

?- numberList(X,Limit).

to determine [Limit, Limit-1 ... 1] as the only solution for a given value for Limit, ie 

?- numberList(X, 100).

would yield X = [100, 99, 98, ..., 1]..

My guess is that there is something pretty wrong with my understanding here for this not to be working. I'm not necessarily asking for a solution to what I am trying to do, I would just like to understand why my first attempt is wrong.

Upvotes: 3

Views: 358

Answers (2)

re Paul
re Paul

Reputation: 122

"Limit - 1" is being thought as a function call, in C-languages and such it would work. It is asking/commanding the Prolog "find a subtract-function, call it with Limit-variable and 1". It is asking Prolog to understand "Limit - 1" as a function call result, but Prolog understands "Limit - 1" as a compound term subtract(Limit,1), it is a predicate from First-order logic

"H is Limit" this is also thought as a function call

Prolog does not have functions (???), I think that claim is a big obstacle for C-people. Instead of functions (as with C and such, as with mathematics), Prolog has predicates (as in predicate logic, First-order and such)

Function is a command that COMMANDS the microprocessor. Instead predicate presents data to microprocessor to "see with the eyes of a microprocessor", presents data to microprocessor to perceive.

Predicate DESCRIBES a piece of world, describes some relations between objects in that world, and microprocessor tries to verify those relations. Microprocessor tries to prove that those relations really exist in it's knowledge. Those relations can exist multiple times in it's knowledge, so the microprocessor can return multiple results (aka. non-determinism)

Prolog is a fantastic programming language, probably I should write fantastic description language, fantastic pattern recognition language, fantastic inference/deduction language (simple inferences/deductions, it is not a kind of "Artificial Intelligence", inferences/deductions as in digital electronic logic gates) . I was a eager Visual Studio programmer before, but I have studied Prolog few years now.

C languages etc. are for Commanding, and Prolog languages etc. are for Describing.

Upvotes: 0

m09
m09

Reputation: 7493

There are two main problems lurking around here:

1- You have troubles getting unification and arithmetic operations at the right places

2- You're not checking your input enough

Remarks about 1- (is)/2 is used to perform arithmetic, here it would be, for example, to substract 1 to Limit. (is)/2 can but should not be used to unify a variable to an already evaluated arithmetic expression. (=)/2 should be prefered (unification).

Remarks about 2- even if you get the operators right, your program'd loop. More on that later.

You won't gain much by just switching operators up yourself, so here is the correct way:

numberList([], 0).
numberList([Limit|T], Limit) :-
    NewLimit is Limit - 1,
    numberList(T, NewLimit).

Here you can see that I use unification implicitely in the head of the second clause, another way to put it is the following:

numberList([], 0).
numberList([H|T], Limit) :-
    H = Limit,
    NewLimit is Limit - 1,
    numberList(T, NewLimit).

But now, as you could see by trying this program out, it finds a correct solution but loops if you ask for another one with ;.

The reason might be harder to spot for the eyes of the beginner: when Prolog succeeds and returns a solution, it can only find new one by exploring choice points left during the execution. Here, the only choice point left is when Limit is 0. So it tries the second clause instead of the first one in that case and loops until it reaches NegativeInfinity. Sadly, since the trip is quite long to get there, it overflows before. The solutions to this problem are to add a guard to the second clause, specifying that Limit should be greater than 0 or to add a cut to the first clause or even better: to do both. Ask if you have troubles doing that yourself!

Upvotes: 3

Related Questions