[erlang-questions] list:join() for erlang?
Fri Sep 14 02:32:40 CEST 2007
Thanks for the very thorough reply... Yeah, "stack-recursive" came out cuz I
couldn't think of the term for "not tail recursive"... so, it's "body
recursive". Thanks for setting me straight.
> I wrote:
>>> join0(X, [Y|Ys]) -> X ++ join0(Y, Ys);
>>> join0(X, ) -> X.
> [join/2, join1/1, join2/3 deleted]
> On 13 Sep 2007, at 10:34 pm, Ben Munat wrote:
>> Out of curiosity -- still feeling my way around erlang and functional
>> programming -- aren't the "helper" functions here stack-recursive
>> (i.e. *not* tail-recursive)?
> I've never heard the term "stack-recursive" before; the normal term
> for calls that are not tail calls is "body" calls (in this case,
> body recursion). Yes, they are body calls. What of that? They are
> what they need to be. As a matter of fact, the Prolog equivalents
> of these *would* be tail recursive:
> join0(, X, X).
> join0([Y|Ys], X, Ans) :-
> append(X, R, Ans),
> join0(Ys, Y, R).
> It would be possible to implement Erlang in such a way that these
> Erlang functions were also tail recursive. It wouldn't even be hard.
> In effect, each function would receive a hidden parameter that was
> the address of where to put the result. This would require a
> different kind of garbage collector, though; the current one can and
> does exploit the fact that there cannot be pointers from "older"
> cells to "newer" ones.
> Tail recursion is nice when you can use it, but in the current
> version of Erlang it would be necessary to build up a result in
> reverse and then reverse it at the end. There are times when that's
> a good idea, but this isn't one of them. Another idea would be not
> to build up the result but to build a stack of lists to be appended.
> Let's see what happens.
> join(, _) -> ;
> join(Xs, ) -> [Last|Stack] = reverse(Xs), join0(Stack, Last);
> join(Xs, [C]) -> [Last|Stack] = reverse(Xs), join1(Stack, Last, C);
> join(Xs, Sep) -> [Last|Stack] = reverse(Xs), join2(Stack, Last, Sep).
> join0([Ys|Yss], Xs) -> join0(Yss, Ys++Xs);
> join0(, Xs) -> Xs.
> join1([Ys|Yss], Xs, C) -> join1(Yss, Ys++[C|Xs], C);
> join1(, Xs, _) -> Xs.
> join2([Ys|Yss], Xs, Sep) -> join2(Yss, Ys++Sep++Xs, Sep);
> join2(, Xs, _ ) -> Xs.
> In effect, this also uses a stack, but it builds the stack as a list
> in the heap. Rather to my surprise, this second version turned out
> to be faster than the previous version. Mind you, you have to make
> the inputs so large, and repeat the operation so many times, to get
> a measurable time, that it's not really a problem.
> I wondered whether unrolling the loops would be worth while, but
> the measurements fluctuated so much it was hard to tell. What
> I'd really like is a high resolution cpu time BIF, which is the
> subject of another thread...
More information about the erlang-questions