# [mercury-users] list.merge is not tail recursive

Michael Day mikeday at yeslogic.com
Thu Jan 21 10:51:47 AEDT 2010

```Hi,

Following up on the stack overflow bug I just reported that affects
list.sort, it seems that the cause of the problem is that list.merge is
not tail recursive:

list.merge([], [], []).
list.merge([A | As], [], [A | As]).
list.merge([], [B | Bs], [B | Bs]).
list.merge([A | As], [B | Bs], [C | Cs]) :-
( compare(>, A, B) ->
C = B,
list.merge([A | As], Bs, Cs)
;
% If compare((=), A, B), take A first.
C = A,
list.merge(As, [B | Bs], Cs)
).

As a result it overflows the stack when merging long lists.
Unfortunately even the --optimise-constructor-last-call option has no
effect on this code (in rotd-2008-01-30), due to the way it is written!

Here is a rewritten version that works as the optimisation applies and
makes it tail recursive to use constant stack space:

:- func my_merge(list(T), list(T)) = list(T).

my_merge([], []) = [].
my_merge([A|As], []) = [A|As].
my_merge([], [B|Bs]) = [B|Bs].
my_merge([A|As], [B|Bs]) =
( if compare('>', A, B) then
[B|my_merge([A|As], Bs)]
else % if A =< B then
[A|my_merge(As, [B|Bs])]
).

This also works:

my_merge([A|As], [B|Bs]) = Cs :-
( if compare('>', A, B) then
Cs = [B|my_merge([A|As], Bs)]
else % if A =< B then
Cs = [A|my_merge(As, [B|Bs])]
).

But this fails:

my_merge([A|As], [B|Bs]) = [C|Cs] :-
( if compare('>', A, B) then
C = B,
Cs = my_merge([A|As], Bs)
else % if A =< B then
C = A,
Cs = my_merge(As, [B|Bs])
).

It would be nice if the constructor last call optimisation was
sufficiently general to handle this case. (And is the standard library
compiled with this optimisation?)

Either way, the list.merge and list.sort functions need to be changed!

Best regards,

Michael

--
Print XML with Prince!
http://www.princexml.com
--------------------------------------------------------------------------
mercury-users mailing list
Post messages to:       mercury-users at csse.unimelb.edu.au