[erlang-questions] Erlang math libraries

ok <>
Fri May 18 06:44:22 CEST 2007


On 18 May 2007, at 2:30 pm, Jay Anderson wrote:ing at lists.erl in  
stdlib and this is
> the implementation of lists:map:
>
> map(F, [H|T]) ->
>     [F(H)|map(F, T)];
> map(F, []) when is_function(F, 1) -> [].
>
> This seems like it wouldn't be tail recursive. So does the erlang  
> compiler optimize this somehow?

There is no fundamental reason why it couldn't:

     map(P, [], []).
     map(P, [X|Xs], [Y|Ys]) :-
         call(P, X, Y),
         map(P, Xs, Ys).

is the Prolog equivalent, and it *is* tail recursive.  It would have
to be implemented something like this:

     map/2 (arguments *R, A1, A2):
         if A2 is a pair then
             H := head(A2)
             X := A1(H)
             L := [X|_]
             *R := L
             A2 := := tail(A2)
             R := &tail(L)
             goto map/2
          else if A2 is nil then
             *R := nil
             return
          else
             call no_match_trap

The issue here is the assignment *R := L, which changes a location
in the heap.  It's actually an initialisation, not a "real" assignment,
but the garbage collector has to expect this kind of thing, which the
garbage collector(s) developed for Erlang don't.  So it's not just a
matter of changing the compiler.

>
> Would the following be preferable for transpose?
>
> t([[]|_]) -> [];
> t(M) -> [ [H || [H|_] <- M] | t([T || [_|T] <- M]) ].

Measure the alternatives and find out.
There is NO substitute for measurement.




More information about the erlang-questions mailing list