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

[Michael Day]

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
Administrative Queries: owner-mercury-users at csse.unimelb.edu.au
Subscriptions:          mercury-users-request at csse.unimelb.edu.au
--------------------------------------------------------------------------