Recursion in Prolog: Addition to variables

Question

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?

my_nth0/4 is needlessly inefficient on backtracking. Compare ?- length(Es,100), time((my_nth0(0,Es,X,0),false)). with ?- length(Es,100), time((nth0(0,Es,X),false). — repeat
– repeat, Commented Nov 24, 2015 at 20:20

repeat · Accepted Answer · 2015-11-24 21:07:50Z

2

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.

answered Nov 24, 2015 at 21:07

repeat

18.8k4 gold badges57 silver badges166 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

lurker · Accepted Answer · 2015-11-24 19:29:19Z

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).

Collectives™ on Stack Overflow

Recursion in Prolog: Addition to variables

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related