streams module

streams.erl

-module(streams).
-author('[email protected]').
%%
%% Author: Torbjorn Tornkvist
%% http://forum.trapexit.org/viewtopic.php?p=22424#22424
%%
%% Date: 27 Nov 1995 
%% 
%% Try this:
%%
%% 1> streams:first(10,streams:map(fun(X)-> round(X) end,streams:scale(100,streams:random_numbers(random:seed())))).
%% [9,44,72,95,50,31,60,92,67,48]
%%
%% 2> streams:first(10, streams:primes()).
%% [2,3,5,7,11,13,17,19,23,29]
%%
%% 3> hd(lists:reverse(streams:first(2000, streams:pi()))).
%% 3.14399
%%

%%-export([start/0]).
-compile(export_all).

-define( cons_stream(H,T) , [H|fun() -> T end] ).

head(S) -> hd(S).
tail(S) -> NS=tl(S),NS().

first(0,_) -> [];
first(N,S) -> [head(S)|first(N-1,tail(S))].

all([]) -> [];
all(S)  -> [head(S)|all(tail(S))].

nth(0,S) -> head(S);
nth(N,S) -> nth(N-1,tail(S)).

map(F,S) ->
    ?cons_stream(F(head(S)),map(F,tail(S))).

scale(C,S) ->
    map(fun(X) -> X*C end,S).

double(S) -> scale(2,S).

naturals() -> integers_starting_from(0).

integers_starting_from(N) ->
    ?cons_stream(N,integers_starting_from(N+1)).

filter(Pred,S) ->
    HS = head(S),
    case Pred(HS) of
        true ->
            ?cons_stream(HS,filter(Pred,tail(S)));
        _ ->
            filter(Pred,tail(S))
    end.

primes() -> sieve(integers_starting_from(2)).

sieve(S) ->
    HS = head(S),
    Pred = fun(X) -> 'not'(divisible(X,HS)) end,
    ?cons_stream(HS,sieve(filter(Pred,tail(S)))).

divisible(X,Y) ->
    if
        X rem Y == 0 -> true;
        true -> false
    end.
    
'not'(true) -> false;
'not'(_) -> true.


gcd(A,0) -> A;
gcd(A,B) -> gcd(B,A rem B).


random_numbers(Seed) ->
    ?cons_stream(random:uniform(),random_numbers(Seed)).
    

cesaro_stream() ->
    F = fun(R1,R2) -> case gcd(R1,R2) of 1 -> true; _ -> false end end,
    map_successive_pairs(F,map(fun(X)-> round(X) end,scale(100,random_numbers(random:seed())))).

map_successive_pairs(F,S) ->
    ?cons_stream(F(head(S),head(tail(S))),
                 map_successive_pairs(F,tail(tail(S)))).

monte_carlo(ExperimentS,Nt,Nf) ->
    Next = fun(Nnt,Nnf) -> 
               ?cons_stream(Nnt/(Nnt+Nnf),
                            monte_carlo(tail(ExperimentS),Nnt,Nnf)) 
           end,
    case head(ExperimentS) of
        true  -> Next(Nt+1,Nf);
        false -> Next(Nt,Nf+1)
    end.

%% An approximation of pi.
%% We will use the fact that the probability that
%% two integers choosen at random will have no factors
%% in common (i.e their GCD is 1) is 6/pi**2. The 
%% fraction of times the test is passed gives us an 
%% estimate of this probability. So the further you 
%% look into the stream, the better approximation you'll get.
pi() ->
    map(fun(P) -> math:sqrt(6/P) end,
        monte_carlo(cesaro_stream(),0,0)).