Understand lists and recursion in Prolog

Question

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.

short answer: ?- A-1 = 0. fails. ?- A-1 is 0. fails too. ?- length(X,5),X=[5|_T],append(_T,[_],_Z),maplist(succ,_Z,X). does what you want. — Will Ness
– Will Ness, Commented May 11, 2012 at 12:13

m09 · Accepted Answer · 2012-05-10 22:25:39Z

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!

Don't hesitate to post questions again if you have troubles! Prolog can be tough on newcomers sometimes :p
Well, I read a few examples, and they seemed to say hey, this is so intuitive your mother could do it... I almost had to ask her.
A cut in the first clause alone does not work: numberList(_,-1) and numberList(L,1.5). And why any cut at all? And why not library(clpfd)?
well I did not really advise the cut alone solution so I won't comment further on the issue. For the cut it can be understandable if the entry format wished is (-, +), else it's a bad idea. But as you mentioned removing the cut wouldn't cut (haha) it here, we'd have to use something else than basic arithmetic to obtain a multi way predicate.

re Paul · Accepted Answer · 2015-01-26 17:27:39Z

"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.

Collectives™ on Stack Overflow

Understand lists and recursion in Prolog

2 Answers 2

4 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Related