[m-users.] Why does list.length use an auxiliary function?

Zoltan Somogyi zoltan.somogyi at runbox.com
Sun Dec 23 21:16:58 AEDT 2018



On Sun, 23 Dec 2018 01:10:36 -0500, Jeffrey Brown <jeffbrown.the at gmail.com> wrote:
>     simple_length( [], 0 ).
>     simple_length( [_|Rest], N ) :-
>       simple_length( Rest, N0 ),
>       N = 1 + N0.
> 
> Why is it instead this more complex one?
>
>     length_acc([], N, N).
>     length_acc([_ | L1], N0, N) :-
>         N1 = N0 + 1,
>         list.length_acc(L1, N1, N).

Because length_acc is tail recursive (i.e. the recursive clause does nothing
after the recursive call, while simple_length is NOT tail recursive (since
it increments the result of the recursive call). This makes the accumulator version
more efficient. See the wikipedia page on tail recursion.

Zoltan.


More information about the users mailing list