# Algorithmic lists

Thomas Arts <>
Mon Oct 16 13:08:54 CEST 2000

```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:
>

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,

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.
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)).

> 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('').
>
> -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

```