CODEWITHSUNDEEP
prolog
shellnut
shellnut

Reputation: 25

Prolog recursion doesn't work the other way

I am learning Prolog and I got stuck in the code where the knowledge base and base rules are:

   rectangle(a1, 3, 5).  %Name,Width,Height
   rectangle(a2, 1, 2).
   rectangle(a3, 4, 3).

   calcWH(T,C) :-
      rectangle(T,W,_), C is W. % finds the width of the rect.

The recursive part is:

calcWTH([],0). % Base case
calcWTH([H | T ] ,K) :-
   length([H|T],L),
   L =< 3,
   calcWTH(T,M),
   calcWH(H,O),
   K is O+M.

What I want to do with this code is, with calcWTH I want to calculate total width of the list of rectangles. For example

 calcWTH([a1,a2,a3],A)

returns 8, as expected. The thing I'm puzzled is that this code only works for one way, not the other. For example when I make a query like

calcWTH(A,3)

It first finds A= [a1], then A=[a2,a2,a2], and afterwards I expect the program to stop because of the part length([H|T],L), L =< 3 But It gets into a loop indefinitely. What am I missing here?

Upvotes: 1

Views: 83

Answers (1)

user27815
user27815

Reputation: 4797

Think about what this is doing:

length([H|T],L), L =< 3
  1. Make a list
  2. Check its length is less than 3, if it is - then success, other wise back track to length/2 and try making another list and then check if that list is length is less than 3.

But we know that list/2 is creating lists in order of larger size, so we know that if list of length 3 fails, then the next list created on back tracking will be bigger and all other lists.. but prolog does not know that. You could imagine writing a length predicate that searchs for lists in a differnt order, maybe randomly, or from a predefined big size to ever smaller lists. Then we would want the backtracking to work as is.

Anyway that is why you get infinite recursion, it will keep trying new lists, of ever increasing size.

You might find adding constraints is a good way to solve your problem:

Using a constrained variable with `length/2`

Upvotes: 1

Related Questions