efficiency, deep lists

[Luke Gorrie]

Ulf Wiger <etxuwig@REDACTED> writes:

> I've been playing around with continuation passing style when 
> processing lists of lists. It does seem to be a bit cheaper than
> the alternative styles. If funs are optimized in R8, it should be
> even more so.

I'll throw in another continuation-based version (for any-depth
lists):

  incr5(L) -> incr55(L, []).

  %% incr55(DeepList, [Continuation])
  incr55([H|T], C) when list(H) ->
      incr55(H, [T|C]);
  incr55([H|T], C) ->
      [H+1|incr55(T, C)];
  incr55([], [C|Cs]) ->
      incr55(C, Cs);
  incr55([], []) ->
      [].

The basic difference here is the trick that most of the time you can
use a data structure instead of a fun for a continuation - which is
perhaps a bit easier to read in crash reports :-). I think that if you
did the any-depth implementation with funs, you'd have a chain of them
each calling the next, which is the same basic thing as my list of
continuations - which is fine too.

I don't know about the relative efficiency, timer:tc is giving me wide
ranges of numbers today. I would *guess* it's slightly cheaper since
it conses instead of making a fun, and makes a local call instead of
calling a fun.

-- 
Favourite Haiku error: Three things are certain:
                       Death, taxes, and lost data.
                       Guess which has occurred.