Streams/lazy lists
Richard Carlsson
<>
Wed Oct 18 16:55:28 CEST 2000
Well, if anyone is still keen on playing around with these things, I
edited the implementation a bit: now called "streams" and uses tuples
instead of cons cells. Enjoy.
/Richard
Richard Carlsson () (This space intentionally left blank.)
E-mail: WWW: http://www.csd.uu.se/~richardc/
-------------- next part --------------
%% ===============================================================
%% Lazy streams
%%
%% 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:
%% ===============================================================
-module(streams).
-vsn('$Id: streams.erl,v 1.2 2000/10/18 13:58:07 richardc Exp $').
-author('').
-copyright('Copyright (C) 2000 Richard Carlsson').
-export([append/2, constant/1, drop/2, duplicate/2, empty/0,
filter/2, first/2, foldl/3, foldr/3, foreach/2,
integers/1, map/2, member/2, merge/3, nth/2, nthtail/2,
push/2, random/0, random_integers/1, seq/2, seq/3,
stream/1, subsequence/3, to_list/1]).
%% The type of the streams defined below is:
%%
%% Stream :: () -> {} | {term(), Stream}
%%
%% A stream 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 streams without forcing
%% evaluation of their input.
%% The empty stream
empty() -> fun () -> {} end.
%% The stream consisting of H followed by all elements of T.
push(H, T) -> fun () -> {H, T} end.
%% Converts a stream into a list. Make sure never to pass an
%% infinite stream to this function!
to_list(S) ->
case S() of
{H, T} ->
[H | to_list(T)];
{} ->
[]
end.
%% Turns a proper normal list into a stream.
stream(L) ->
fun () ->
case L of
[H | T] ->
{H, stream(T)};
[] ->
{}
end
end.
%% The stream of all elements of S1 followed by all elements of
%% S2.
append(S1, S2) ->
fun () ->
case S1() of
{} ->
S2();
{H, T} ->
{H, append(T, S2)}
end
end.
%% The stream of integers in the interval [From, To], in ascending
%% order.
seq(From, To) ->
seq(From, To, 1).
%% The stream 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, empty()} end;
seq(From, To, D) ->
empty().
%% The stream of integers starting at N.
integers(N) ->
fun () -> {N, integers(N + 1)} end.
%% The infinite stream of elements X.
constant(X) ->
fun () -> {X, constant(X)} end.
%% The stream 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 stream of random floating-point 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 stream 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 stream consisting of the first N elements of S, or the
%% stream S if the length of S is not greater than N.
first(0, S) -> empty();
first(N, S) when integer(N), N > 0 ->
fun () ->
case S() of
{H, T} ->
{H, first(N - 1, T)};
{} ->
{}
end
end.
%% The stream [EN+1, EN+2, ...], if S is [E1, ..., EN, EN+1, ...].
drop(0, S) -> S;
drop(N, S) when integer(N), N > 0 ->
fun () ->
case S() of
{H, T} ->
(drop(N - 1, T))();
{} ->
{}
end
end.
%% The stream [EN, EN+1, ..., EN+D], if S is [E1, E2, ...].
subsequence(N, D, S) when N > 0, D >= 0 ->
first(D, drop(N, S)).
%% The stream [F(E1), F(E2), F(E3), ...] if S is [E1, E2, E3,
%% ...].
map(F, S) ->
fun () ->
case S() of
{H, T} ->
{F(H), map(F, T)};
{} ->
{}
end
end.
%% The stream of all elements E in S (in the same order) for which
%% P(E) returns `true'. P must return either `true' or `false' for
%% all elements in S.
filter(P, S) ->
fun () ->
case S() of
{H, T} ->
case P(H) of
true ->
{H, filter(P, T)};
false ->
(filter(P, T))()
end;
{} ->
{}
end
end.
%% Returns the stream of elements in S1 and S2 where the
%% respective relative order of elements is preserved, and each
%% element Y of S2 is ordered before the first possible X of S1
%% such that P(X, Y) yields `false'. P(X, Y) must yield either
%% `true' or `false' for all X in S1 and Y in S2. (P can be read
%% as "less than".)
merge(P, S1, S2) ->
fun () ->
case S1() of
{H1, T1} ->
case S2() of
{H2, T2} ->
case P(H1, H2) of
true ->
{H1, merge(P, T1,
push(H2, T2))};
false ->
{H2, merge(P, push(H1, T1),
T2)}
end;
{} ->
{H1, T1}
end;
{} ->
S2()
end
end.
%% ===============================================================
%% All functions below may evaluate all or part of their input.
%% Returns `true' if X is in the stream S, and `false' otherwise.
member(X, S) ->
case S() of
{H, T} ->
if H == X -> true;
true -> member(X, T)
end;
{} -> false
end.
%% Returns the Nth element of stream S.
nth(N, S) ->
S1 = S(),
if N > 1 ->
nth(N - 1, tl(S1));
true ->
hd(S1)
end.
%% Returns the stream [AN+1, AN+2, ...] if S is [A1, A2, ..., AN,
%% AN+1, AN+2, ...].
nthtail(N, S) when N > 1 ->
nthtail(N - 1, tl(S()));
nthtail(0, S) ->
S.
%% Computes (...((A F E1) F E2)... F EN), if S is [E1, E2, ...,
%% EN] and F is a binary function (here written as an infix
%% operator).
foldl(A, F, S) ->
case S() of
{H, T} ->
foldl(F(A, H), F, T);
{} ->
A
end.
%% Computes (E1 F ...(EN-1 F (EN F A))...), if S is [E1, E2, ...,
%% EN] and F is a binary function (here written as an infix
%% operator).
foldr(S, F, A) ->
case S() of
{H, T} ->
F(H, foldr(T, F, A));
{} ->
A
end.
%% Evaluates F(E1), F(E2), ..., if S is [E1, E2, ...]. Always
%% returns `ok'.
foreach(F, S) ->
case S() of
{H, T} ->
F(H),
foreach(F, T);
{} ->
ok
end.
%% ===============================================================
More information about the erlang-questions
mailing list