CODEWITHSUNDEEP
recursionprologtail-recursion
digit-1
digit-1

Reputation: 11

Tail-Recursion in Prolog

I'm new to Prolog and I'm having trouble with a practise question on tail recursion.

Question:

Define a relationship, where the first argument is a list of objects, the second is a number, and the third is the total price of the objects in the list plus the second argument; and also ensure that the call to the recursion is the last clause of your rule.

Object list:

cost( table, 1000).  
cost( chair, 100).  
cost( lamp, 80).  
cost( oven, 800).

e.g. totalTail( [chair,table], 100, X) ==> X = 1200.

What rules should I be defining?

Upvotes: 1

Views: 330

Answers (1)

Will Ness
Will Ness

Reputation: 71065

You can start by defining what you already know it ought to be:

totalTail( [chair, table], 100, X) :- X = 1200.

or, equivalently,

totalTail( [Chair, Table], 100, X) :- 
    Chair = chair, cost( Chair, 100),
    Table = table, cost( Table, 1000),
    X is 100 + 100 + 1000.

or, equivalently,

totalTail( [Chair, Table], InitialCost, X) :- InitialCost = 100,
    Chair = chair, cost( Chair, ChairCost), ChairCost = 100,
    Table = table, cost( Table, TableCost), TableCost = 1000,
    X is InitialCost + ChairCost + TableCost.

or, equivalently,

totalTail( [Chair, Table], InitialCost, X) :- 
                   cost( Chair, ChairCost),
                   cost( Table, TableCost),
    X is InitialCost + ChairCost + TableCost.

(Boom!) Or, equivalently,

totalTail( [A, B], InitialCost, X) :- 
                   cost( A, ACost),
                   cost( B, BCost),
    X is InitialCost + ACost + BCost.

or even 

totalTail( [A, B, C], Z, X) :- 
                   cost( A, ACost),
                   cost( B, BCost),
                   cost( C, CCost),
    X is Z + ACost + BCost + CCost.

which is the same as

totalTail( [A, B, C], Z, X) :- 
                   cost( A, ACost),
                   totalTail( [B, C], Z, X2)
    X is Z + ACost + X2.

Right? Wrong! Can you spot the error? Did we count something twice, there?

So fixing it, we get

totalTail( [A, B, C], Z, X) :- 
                   cost( A, ACost),
                   Z2 is .... + .... ,
                   totalTail( [B, C], Z2, X).

Right. But isn't it the same as

totalTail( [A | BC], Z, X) :- BC = [B, C],
                   cost( A, ACost),
                   Z2 is .... + .... ,
                   totalTail( BC, Z2, X).

But, again, why limit yourself to that very specific option, BC = [B, C]? Do we really have to specify it?

And what if the first argument does not match the [A | BC] list at all? What kind of a list would that be? And what should X be in that case?

Upvotes: 3

Related Questions