Prolog recursion base case

0
votes

I have a slightly complex recursive function in prolog. What it does isn't super important because I'm pretty sure my problem lies in the method headers.

  • V is a list that doesn't change in the entire function
  • Vset is a list of lists - In the function I pull off one of the individual lists, multiply it by list V, and store that value. That individual list gets removed from the list of lists.

  • Dlist is a list comprised of all the values computed

    distanceAllVectors(V, [], [H|T]).
distanceAllVectors(V, Vset, Dlist) :-   
   #function code here

I've traced the function in prolog and at one point Dlist is full of the correct values and Vset is empty. That's the point at which I need this function to end.

I apologize for not posting the entire code, but it's comprised of a few different methods that would take more time to explain when I'm 99% sure this is the root of my problem.

I'm confused about what my base case should be, and how base cases work in prolog in general.

Thank you!

2
recursionprolog
You Prolog should warn you about singletons in your base case. Try to solve such warnings. – CapelliC

2 Answers

0
votes

Two main choices, you build your list while exiting the recursion, or if your Prolog supports Tail Call Optimisation, you can build with an accumulator and exit with a unification. Also to consider, the order of the Distances will be opposite for each method.

Building the list on exit and retaining order:

% base case, the list being processed is empty, so are the distances
% time to start exiting the recursion
distanceAllVectors(_, [], []).
% recursive case, calculate one, process the rest, put the Distance
% onto the Distances on the way out of the recursion
distanceAllVectors(V, [HeadList|Tail], [Dist|Distances]) :-
    distanceOneVector(V, HeadList, Dist),
    distanceAllVectors(V, Tail, Distances).

With an accumulator and reversing the order:

% interface to accumulator
distanceAllVectors(V, Vectors, Distances) :-
    distanceAllVectors(V, Vectors, [], Distances).

% base case, the list of vectors is emptied, unify
% Distances with the accumulator (by calling it Distances)
% Immediately exit the recursion via Tail Call Optimization
distanceAllVectors(_, [], Distances, Distances).
% recursive case, calculate one, add to accumulator and continue
distanceAllVectors(V, [HeadList|Tail], Acc, Distances) :-
    distanceOneVector(V, HeadList, Dist),
    distanceAllVectors(V, Tail, [Dist|Acc], Distances).
0
votes

See my comments in the code.

% If V is the empty list, then result is the empty list. (You were missing this case.)
distanceAllVectors([], _, []).

% If Vset is the empty list, then result is the empty list.
distanceAllVectors(_, [], []).

% If V and Vset are not the empty list, the result R is
% V multiplied by the first element S in Vset, followed
% by the result U of multiplying V by the tail T of Vset.
distanceAllVectors(V, [S|T], [R|U]) :-
    mult(V, S, R),                  % <-- Base case.
    distanceAllVectors(V, T, U).    % <-- Recursive case.

% Multiply X by Y, result is simply m(X, Y).
% You have to implement your real multiplication here.
 mult(X, Y, m(X, Y)).