-module(ns).

-author('tobbe@erix.ericsson.se').
%%-export([start/0]).
-compile(export_all).

%% return 'lazy' X
-define( return(X) , fun() -> X end ).

%% force evaluation of X
-define( force(X) , (X())).

%% Bind variable X to 'forced' D in K and force K
-define( bind(X, D, K) , fun() -> X=?force(D), ?force(K) end ).

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

%% lazy nil
-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.
    

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




