Algorithmic lists

[Thomas Arts]

Ulf Wiger wrote:
> 
> Here's a thought:
> 
> We (a few lunatics at AXD 301) would like to see the lists module
> support an alternative formulation of lists.
> 
> A list could be expressed in the following manner:
> 
> [Head | fun(Head, F)]

I don't really like that notation, since the tail of a list is
no longer a list now (but a function returning a list). I find
it more natural to return a tuple, a kind of continuation. 

Basically you try to introduce lazy evaluation in an eager
language. I think this is indeed sometimes needed (I wrote
a lazy version of "all subsets of a set" recently). When
dealing with the create and filter paradigm, one basically
wants to generate a list and drop all items that do not
respect a certain filter function. That's the same here,
except that instead of just removing it from the list,
you add a side-effect.

It would be nice if this could be established by a smart,
lazy list-comprehension:

[ X || X<-seq(1,5), condition(X) ]

where condition(X) is

condition(X) ->
  io:format("-- ~p~n", [X]), 
  false.

The result would be the empty list, but (as far as I recall
the Erlang semantics) the list seq(1,5) is generated before
the tests on the arguments is performed. It would be nice to have
a lazy list-comprehension as well. An element is computed, the
filter is applied and so on. Syntax could be basically the same, as
long as no side-conditions are allowed in the generators, I 
think the execution of the strict and the eager variant should be
the same.
Solving it this way, would keep your code more readable ;0).
Implementation in the compiler seems not so hard to me, but let
a compiler writer comment on that.

With respect to your solution, why not using the tuple construct:
implicitely defining the continuation type:

+deftype continuation(T) = {} | {T, fun(T,continuation(T)) -> continuation(T)}.



+type seq(int(),int()) -> continuation(int()).

seq(Start, Stop) when Start < Stop ->
    {Start , fun(N, F) when N == Stop ->
                     {};
                (N, F) ->
                     {N+1 , F}
             end].

+type foreach(fun(A) -> B, continuation(A)) -> void().

foreach(F, {}) ->
  void;
foreach(F, {H,C}) ->
  F(H),
  foreach(F, C(H, C)).

Sure, overloading of foreach needs the two lines

> foreach(F, []) ->
>     [];
> foreach(F, [H|T]) ->
>     F(H),
>     foreach(F, T);

as well, because of Erlang's structure.

Implementing it within Erlang in this way has the disadvantage
that you need to program quite a lot, which is not the case if 
it would have been given as a language primitive.

/Thomas



> 
> 
> Example:
> 
> -module(alglists).
> -author('etxuwig@REDACTED').
> 
> -export([seq/2, foreach/2]).
> 
> %%-export([Function/Arity, ...]).
> 
> seq(Start, Stop) when Start < Stop ->
>     [Start | fun(N, F) when N == Stop ->
>                      [];
>                 (N, F) ->
>                      [N+1 | F]
>              end].
> 
> foreach(F, []) ->
>     [];
> foreach(F, [H|T]) when list(T) ->
>     F(H),
>     foreach(F, T);
> foreach(F, [H|T]) when function(T) ->
>     F(H),
>     foreach(F, T(H, T)).
> 
> Eshell V4.8.2.7  (abort with ^G)
> 
> 1> lists:foreach(fun(X) -> io:format("-- ~p~n", [X]) end,
> lists:seq(1,5)).      -- 1
> -- 2
> -- 3
> -- 4
> -- 5
> ok
> 2> c(alglists).
> {ok,alglists}
> 3> alglists:foreach(fun(X) -> io:format("-- ~p~n", [X]) end,
> alglists:seq(1,5)).
> -- 1
> -- 2
> -- 3
> -- 4
> -- 5
> ok
> 
> (Perhaps to avoid breaking half the Erlang programs in the universe,
> functions in lists should not return lists on this form, but should be
> able to process them.)
> 
> Let me briefly tell you why we'd like to do this:
> 
> On several occasions, we've rewritten code that generates a large
> list on the heap and then traverses it. It's a shame from one
> perspective, because the new code (which usually uses ets:next/2) is
> not FP-style, and less elegant -- but it is more well behaved from a
> memory management perspective, which is its one (but vital) merit.
> We'd like to keep the concept of list processing, but avoid the large
> lists, which cause havoc in the GC.
> 
> What'ya think? Awful? Elegant?
> 
> BTW, Joe already posted something like this on the erlang-questions
> list in March '99, but he was using zero-argument funs.
> 
> http://www.erlang.org/ml-archive/erlang-questions/199903/msg00013.html
> 
> /Uffe
> --
> Ulf Wiger                                    tfn: +46  8 719 81 95
> Strategic Product & System Management        mob: +46 70 519 81 95
> Ericsson Telecom AB,              Datacom Networks and IP Services
> Varuvägen 9, Älvsjö,                    S-126 25 Stockholm, Sweden