CODEWITHSUNDEEP
recursionprolog
TheLeonKing
TheLeonKing

Reputation: 3601

Recursion in Prolog: Addition to variables

I don't really understand how recursion works in Prolog. Assume you have the following two functions:

my_length([],0).
my_length([_|T], Length) :-
    my_length(T, T_length),
    Length is T_length + 1.

my_nth0(Position, [Element|_], Element, Position).
my_nth0(Position, [_|Tail], X, CurrentPos) :-
    NextPos is CurrentPos + 1,
    my_nth0(Position, Tail, X, NextPos).

I understand my_nth0: every time you call the function recursively, you increase NextPos by 1. However, I don't understsand my_length. I'd write it like this:

my_length([],0).
my_length([_|T], Length) :-
    T_Length is Length + 1.,
    my_length(T, T_length).

That seems to follow the same style as my_nth0. However, the first function implementation, which seems to be correct, does exactly the opposite (it basically says T_length is Length - 1). Why does this work?

Upvotes: 1

Views: 233

Answers (2)

repeat
repeat

Reputation: 18726

Read the second clause of my_length/2 right-to-left!

If the length of T is T_length

then the length of [_|T] is T_length+1.

Upvotes: 2

lurker
lurker

Reputation: 58244

Did you actually try out your version of my_length/2 to see what happens? After you fix your syntax error (:)), you'll get a 'variable not instantiated error' if you query, my_length([1,2,3], N). because it will attempt to evaluate T_Length is Length + 1 when Length doesn't have a value. Thus, the recursive call has to come first if you use is/2 so that Length has a value from the recursive call as in the first example.

In addition, in your example, you are attempting to increase the variable via T_Length is Length + 1 but your recursive base case ends up with a length of 0. You cannot "grow" the length to 0.

my_length([], 0).     % Base case is length = 0
my_length([_|T], Length) :-
    % Length is UNINSTANTIATED on my_length([1,2,3], N) query
    %  so the following 'is/2' will fail to evaluate
    T_Length is Length + 1,
    my_length(T, T_length).    % T_length > Length, but base case is 0!

Alternatively, if you used CLPFD and fix the order of evaluation of Length versus T_Length, you can put it in the order that you are showing:

my_length([], 0).
my_length([_|T], Length) :-
    % The following defines an arithmetic 'relation' between Length and T_Length
    %   and is permitted as a constraint
    Length #= T_Length + 1,
    my_length(T, T_length).

You could also do the length using an accumulator to get the tail recursion so that you can indeed grow the length value until it reaches the end:

my_length(L, N) :-
    my_length(L, 0, N).

my_length([], N, N).    % Reached the length
my_length([_|T], A, N) :-   % Here, `A` is instantiated by design
    A1 is A + 1,        % So this is/2 expression will evaluate
    my_length(T, A1, N).

Upvotes: 1

Related Questions