[mercury-users] map is not tail-recursive

[Michael Day]

Hi,

Map is not tail-recursive. This means that applying map to a long list
will lead to a stack overflow, which sucks.

Is this something that can be fixed, either by an optimisation to
introduce an accumulator argument or by explicitly writing it like this:

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

    tail_map(Func, Xs) = tail_map0(Func, Xs, []).

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

    tail_map0(_Func, [], Ys) = reverse(Ys).
    tail_map0(Func, [X|Xs], Ys) =
        tail_map0(Func, Xs, [Func(X)|Ys]).

On a more general note, would it be possible to have a stackless Mercury
implementation that allocated stack frames on the heap and could never run
out of stack even for predicates that are not tail-recursive?

Michael

-- 
Print XML with Prince!
http://www.princexml.com
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------