I/O streams

[Torbjorn Tornkvist]

Talking about streams. Just for the fun of it, here's an old hack that
the great Phil Wadler helped me out with once.

Some examples:

%% Get the first 7 primes
1> S=ns:first(7,ns:primes()).
#Fun<ns.1.125034421>
2> ns:stream_to_list(S).
[2,3,5,7,11,13,17]

%% Example of appending streams
3> ns:stream_to_list(ns:first(8,ns:append(ns:first(5,ns:naturals()),
                                          ns:first(5,ns:naturals())))).
[0,1,2,3,4,0,1,2]

%% Random number generation
4> ns:stream_to_list(
     ns:first(10,
              ns:map(fun(X)-> round(X) end,
              ns:scale(100,ns:random_numbers(random:seed()))))).
[9,44,72,95,50,31,60,92,67,48]

%% Approx. of PI (the further you look into the stream the better approx.)
5> ns:stream_to_list(ns:first(10,ns:pi())).  
[2.44949,
 2.44949,
 2.44949,
 2.82843,
 2.73861,
 3.00000,
 3.24037,
 3.46410,
 3.28634,
 3.16228]

Cheers /Tobbe

-module(ns).
-author('tobbe@REDACTED').
%%-export([start/0]).
-compile(export_all).

-define( return(X) , fun() -> X end ).

-define( force(X) , begin XXXfunnyvar=X, XXXfunnyvar() end ).

-define( vforce(V,X) , begin V=X, V() end ).

-define( bind(X,D,K) , fun() -> X=?vforce(XXXfunnyvar1,D), ?vforce(XXXfunnyvar2,K) end ).

-define( cons(H,T) , ?return({cons,H,T}) ).

-define( nil(), ?return(nil) ).

%% A lazy first...

first(0,_) -> ?nil();
first(N,S) when N>0 ->
    ?bind(S1,S,
           case S1 of
	       nil ->
		   ?nil();
	       {cons,H,T} -> 
		   ?cons(H,first(N-1,T))
           end).

%% 24> statistics(reductions),ns:first(7,ns:primes()),statistics(reductions).   
%% {1705891,61}
%% 25> statistics(reductions),ns:stream_to_list(ns:first(7,ns:primes())),statistics(reductions).
%% {1708314,616}
%% 6> statistics(reductions),streams:first(7,streams:primes()),statistics(reductions).
%% {1712785,576}

nth(0,S) -> 
    case ?force(S) of
	{cons,H,T} -> H
    end;
nth(N,S) when N>0 -> 
    case ?force(S) of
	{cons,_,T} -> nth(N-1,T)
    end.

map(F,S) ->
    ?bind(S1,S,
	  case S1 of
	      nil ->
		  ?nil();
	      {cons,H,T} ->
		  ?cons(F(H),map(F,T))
	  end).

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

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

%% Example:
%%
%% 15> ns:stream_to_list(ns:first(8,ns:append(ns:first(5,ns:naturals()),ns:first(5,ns:naturals())))).
%% [0,1,2,3,4,0,1,2]

%% 77> statistics(reductions),ns:stream_to_list(ns:first(8,ns:append(ns:naturals(),ns:naturals()))),statistics(reductions).
%% {1909897,270}
%% 78> statistics(reductions),ns:lf(8,lists:append(lists:seq(1,500),lists:seq(1,500))),statistics(reductions). 
%% {1919732,1157}
    
append(S,R) ->
    ?bind(S1,S,
	    case S1 of
		nil -> R;
		{cons,H,T} -> ?cons(H,append(T,R))
	    end).

naturals() -> 
    integers_starting_from(0).

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

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

sieve(S) ->
    ?bind(S1,S,
	  (case S1 of
	      nil ->
		  ?nil();
	      {cons,H,T} ->
		  Pred = fun(X) -> 'not'(divisible(X,H)) end,
	          ?cons(H,sieve(filter(Pred,T)))
	  end)).

filter(Pred,S) ->
    ?bind(S1,S,
	  case S1 of
	      nil ->
		  ?nil();
	      {cons,H,T} ->
		  case Pred(H) of
		      true ->
			  ?cons(H,filter(Pred,T));
		      false ->
			  filter(Pred,T)
		  end
	 end).

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

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

%% Try this:
%% 22> ns:stream_to_list(ns:first(10,ns:map(fun(X)-> round(X) end,ns:scale(100,ns:random_numbers(random:seed()))))).
%% [9,44,72,95,50,31,60,92,67,48]

random_numbers(Seed) ->
    ?cons(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) ->
    ?bind(S1,S,
	  case S1 of
	      {cons,H,T} ->
		  case ?force(T) of
		      {cons,H2,T2} ->
			  ?cons(F(H,H2),
				map_successive_pairs(F,T2))
		  end
	  end).

monte_carlo(S,Nt,Nf) ->
    ?bind(S1,S,
	  (case S1 of
	      {cons,H,T} ->
		  Next = fun(Nnt,Nnf) -> 
				 Q = Nnt+Nnf,
				 ?cons(Nnt/Q,monte_carlo(T,Nnt,Nnf))
	                 end,
	          case H of
		      true  -> Next(Nt+1,Nf);
		      false -> Next(Nt,Nf+1)
		  end
	  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)).




%% Converting routines: streams <--> lists

stream_to_list(S) ->
    case ?force(S) of
	{cons,H,T} ->
	    [H|stream_to_list(T)];
	nil ->
	    []
    end.

list_to_stream([H|T]) -> ?cons(H,list_to_stream(T));
list_to_stream([])    -> ?nil().




%% Misc. routines

rv(File,NewFile) when list(File) ->
    M = erl_kernel:file(File),
    {ok,T,_} = erl_kernel:module(M),
    {ok,F} = file:open(NewFile,write),
    erl_kernel:pp(T,F),
    file:close(F).


lf(0,_) -> [];
lf(N,[H|T]) -> [H|lf(N-1,T)].