Lazy lists - an implementation.
Richard Carlsson
richardc@REDACTED
Tue Oct 17 17:55:30 CEST 2000
On Tue, 17 Oct 2000, Ulf Wiger wrote:
> OK, since noone complained too much, here's a hack of lists.erl,
> where most functions have been enhanced to operate on both eager
> and lazy lists.
And here is my first version of a lazy lists library. Seems to work ok.
Nothing is evaluated unless necessary. Note, though, that my
interpretation of a lazy list is (like in the example that Tobbe gave, due
to Phil Wadler) a fun:
LazyList :: () -> [] | [term() | LazyList]
This makes things easier. The way Ulf implemented them can be seen as
using an explicit push-back buffer for an initial number of known
elements, but this makes programming with fully lazy lists more difficult,
because many more cases must be handled. (In my implementation, you can
push stuff back using e.g. `cons(H, T)' when necessary.) Also, in Ulfs
current implementation, either a list is empty or the first element has
been computed. (This could be fixed, though.)
/Richard
Richard Carlsson (richardc@REDACTED) (This space intentionally left blank.)
E-mail: Richard.Carlsson@REDACTED WWW: http://www.csd.uu.se/~richardc/
-------------- next part --------------
%% ===============================================================
%% Lazy lists
%%
%% Copyright (C) 2000 Richard Carlsson
%%
%% This library is free software; you can redistribute it and/or
%% modify it under the terms of the GNU Lesser General Public
%% License as published by the Free Software Foundation; either
%% version 2 of the License, or (at your option) any later
%% version.
%%
%% This library is distributed in the hope that it will be useful,
%% but WITHOUT ANY WARRANTY; without even the implied warranty of
%% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
%% GNU Lesser General Public License for more details.
%%
%% You should have received a copy of the GNU Lesser General
%% Public License along with this library; if not, write to the
%% Free Software Foundation, Inc., 59 Temple Place, Suite 330,
%% Boston, MA 02111-1307 USA
%%
%% Author contact: richardc@REDACTED
%% ===============================================================
-module(lazy_lists).
-vsn('$Id: lazy_lists.erl,v 1.1 2000/10/17 15:26:28 richardc Exp $').
-author('richardc@REDACTED').
-copyright('Copyright (C) 2000 Richard Carlsson').
-export([append/2, cons/2, constant/1, duplicate/2, eval/1,
filter/2, first/2, foldl/3, foldr/3, foreach/2,
integers/1, lazy/1, map/2, member/2, merge/3, nil/0,
nth/2, nthtail/2, random/0, random_integers/1, seq/2,
seq/3, sublist/3]).
%% The type of the lists defined below is:
%%
%% LazyList :: () -> [] | [term() | LazyList]
%%
%% A lazy list is thus always a fun. One advantage is that if a
%% producer has side effects (e.g., if it reads elements from a
%% file), we need never trigger the next effect unless we really
%% want to see the next element. Also, programming becomes very
%% straightforward. Let's hope for better compilers to make this
%% sort of programming more efficient.
%% ===============================================================
%% The following functions compute new lazy lists without forcing
%% evaluation of their input.
%% The empty list
nil() -> fun () -> [] end.
%% The list consisting of H followed by all elements of L.
cons(H, T) -> fun () -> [H | T] end.
%% Completely evaluates a lazy list. Make sure never to pass an
%% infinite list to this function!
eval(L) ->
case L() of
[H | T] ->
[H | eval(T)];
[] ->
[]
end.
%% Turns a proper normal list into a lazy list.
lazy(L) ->
fun () ->
case L of
[H | T] ->
[H | lazy(T)];
[] ->
[]
end
end.
%% The list of all elements of L1 followed by all elements of L2.
append(L1, L2) ->
fun () ->
case L1() of
[] ->
L2();
[H | T] ->
[H | append(T, L2)]
end
end.
%% The list of integers in the interval [From, To], in ascending
%% order.
seq(From, To) ->
seq(From, To, 1).
%% The list of integers [From, From + D, From + 2*D, ..., From +
%% D*((To - From) mod D)]. The interval is empty if D does not
%% have the same sign as the difference To - From.
seq(From, To, D) when integer(From), integer(To),
From < To, D > 0 ->
fun () -> [From | seq(From + D, To, D)] end;
seq(From, To, D) when integer(From), integer(To),
To < From, D < 0 ->
fun () -> [From | seq(From + D, To, D)] end;
seq(From, To, D) when integer(From), integer(To), To == From ->
fun () -> [From | nil()] end;
seq(From, To, D) ->
nil().
%% The list of integers starting at N.
integers(N) ->
fun () -> [N | integers(N + 1)] end.
%% The infinite list of elements X.
constant(X) ->
fun () -> [X | constant(X)] end.
%% The list of length N, where each element is X.
duplicate(N, X) when integer(N) ->
fun () ->
if N > 0 ->
[X | duplicate(N - 1, X)];
N == 0 ->
[]
end
end.
%% An infinite list of random floating-pint numbers in the
%% interval [0.0, 1.0]. `random:seed' must be used (by the same
%% process) to set the seed for the random number generator before
%% this function is called.
random() ->
fun () -> [random:uniform() | random()] end.
%% An infinite list of random integers in the interval [0, Max].
%% See `random' above for details.
random_integers(Max) when Max >= 1 ->
fun () -> [random:uniform(Max) | random_integers(Max)] end.
%% The list consisting of the first N elements of L, or the list L
%% if the length of L is not greater than N.
first(0, L) -> nil();
first(N, L) when integer(N), N > 0 ->
fun () ->
case L() of
[H | T] ->
[H | first(N-1, T)];
[] ->
[]
end
end.
%% The list [EN, EN+1, ..., EN+D], if L is [E1, E2, ...].
sublist(N, D, L) when N > 0, D >= 0 ->
if N > 1 ->
fun () ->
case L() of
[H | T] ->
(sublist(N - 1, D, T))();
[] ->
[]
end
end;
true ->
first(D, L)
end.
%% The list [F(E1), F(E2), F(E3), ...] if L is [E1, E2, E3, ...].
map(F, L) ->
fun () ->
case L() of
[H | T] ->
[F(H) | map(F, T)];
[] ->
[]
end
end.
%% The list of all elements E in L (in the same order) for which
%% P(E) returns `true'. P must return either `true' or `false' for
%% all elements in L.
filter(P, L) ->
fun () ->
case L() of
[H | T] ->
case P(H) of
true ->
[H | filter(P, T)];
false ->
(filter(P, T))()
end;
[] ->
[]
end
end.
%% Returns the list of elements in L1 and L2 where the respective
%% relative order of elements is preserved, and each element Y of
%% L2 is ordered before the first possible X of L1 such that P(X,
%% Y) yields `false'. P(X, Y) must yield either `true' or `false'
%% for all X in L1 and Y in L2. (P can be read as "less than".)
merge(P, L1, L2) ->
fun () ->
case L1() of
[H1 | T1] ->
case L2() of
[H2 | T2] ->
case P(H1, H2) of
true ->
[H1 | merge(P, T1,
cons(H2, T2))];
false ->
[H2 | merge(P, cons(H1, T1),
T2)]
end;
[] ->
[H1 | T1]
end;
[] ->
L2()
end
end.
%% ===============================================================
%% All functions below may evaluate all or part of their input.
%% Returns `true' if X is in the list L, and `false' otherwise.
member(X, L) ->
case L() of
[H | T] ->
if H == X -> true;
true -> member(X, T)
end;
[] -> false
end.
%% Returns the Nth element of list L.
nth(N, L) ->
L1 = L(),
if N > 1 ->
nth(N - 1, tl(L1));
true ->
hd(L1)
end.
%% Returns the list [AN+1, AN+2, ...] if L is [A1, A2, ..., AN,
%% AN+1, AN+2, ...].
nthtail(N, L) when N > 1 ->
nthtail(N - 1, tl(L()));
nthtail(0, L) ->
L.
%% Computes (...((A F E1) F E2)... F EN), if L is [E1, E2, ...,
%% EN] and F is a binary function (here written as an infix
%% operator).
foldl(A, F, L) ->
case L() of
[H | T] ->
foldl(F(A, H), F, T);
[] ->
A
end.
%% Computes (E1 F ...(EN-1 F (EN F A))...), if L is [E1, E2, ...,
%% EN] and F is a binary function (here written as an infix
%% operator).
foldr(L, F, A) ->
case L() of
[H | T] ->
F(H, foldr(T, F, A));
[] ->
A
end.
%% Evaluates F(E1), F(E2), ..., if L is [E1, E2, ...]. Always
%% returns `ok'.
foreach(F, L) ->
case L() of
[H | T] ->
F(H),
foreach(F, T);
[] ->
ok
end.
%% ===============================================================
More information about the erlang-questions
mailing list