CODEWITHSUNDEEP
recursionprolog
Wakka Wakka Wakka
Wakka Wakka Wakka

Reputation: 281

Simple Recursive Prolog Function

I'm currently trying to create a simple function that prints the integers in a list given the first and last number.

For example, the function call: count(3,7,Z) would print "Z = [3,4,5,6,7]"

Here is my attempt so far:

count(First,Last,Result):-
  First <= Last,
  append(First,Result,Result),
  count(First+1,Last,Result).

What exactly am I doing wrong? The idea is that as long as First is less than or equal to last, the sequence will keep being appended to the Result List.

Thanks in advance! I've been battling this for quite a while!

Upvotes: 0

Views: 1067

Answers (2)

Pietro Braione
Pietro Braione

Reputation: 1153

There are many issues with your program. First, when you write 3 + 2 Prolog does not, as any other language do, calculate the result. You must explicitly ask to do the calculation and bind the result of the calculation to a variable by the predicate is, e.g., X is 3 + 2, ... and then you will have X bound to 5 to be used in the rest of the rule's tail.

Second, writing append(First, Result, Result) means "by appending First to Result you obtain again Result", which will always fail (read: produce false) unless First is the empty list, because if you append something to a list, you obtain a longer list than the one you started with. You clearly failed in distinguishing the two Results in append and count - they are really not the same. Note also that append(A, B, C) applies to lists, so A, B and C must all be lists or terms that can be instantiated to lists, or it will fail. That's precisely your case since First is always a number - definitely not a list, but a member for it. So you shall not use append: Use list construction and unification with = to append an element to a list and bind the obtained result to a variable, e.g., X = [Element | List].

Finally, were all of the above correct, your predicate would nevertheless fail because you do not define the base case of the induction. In other words: When your predicate should answer []? This must happen when, as CapelliC remarks, First > Last: In that case the range is empty, and Result must also be. In your program, when this happens, the predicate plainly fails (note that, when you write foo(X, Y) :- X >= 0, Y is X + 1., this means failure whenever X is less than zero). Being the empty range the base case of the recursion, the evaluation of your predicate will, sooner or later, end there, and so it will always fail.

In the end, you should write something like:

ints(First, Last, Interval) :- First > Last -> Interval = [] ;
  NFirst is First + 1, ints(NFirst, Last, NInterval), Interval = [First | NInterval].

(I gave more declarative names to your predicates and variables). Of course this predicate will work only when invoked with First and Last completely instantiated to numbers (it cannot be inverted).

Upvotes: 0

CapelliC
CapelliC

Reputation: 60034

line by line:

  1. count(First,Last,Result):-

    bad style: the name suggest another functionality

  2. First <= Last,

    the 'less or equal' operator is =<

  3. append(First,Result,Result),

    you're passing INT,LIST,LIST, but append/3 has signature LIST,LIST,LIST, and you want a value update, but variables in Prolog are 'immutable', such call could succeed only if Result doesn't change

  4. count(First+1,Last,Result).

    arithmetic expressions must be explicitly evaluated, here you pass a structure +(First,1)

And you also miss to code the behaviour required when the test (once corrected) will fail. What about First>Last ?

Upvotes: 1

Related Questions