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