# Algorithmic lists

Torbjorn Tornkvist <>
Mon Oct 16 13:04:59 CEST 2000

```Talking of lazy lists, Phil Waldler once
helped me writing the following stuff.

Cheers /Tobbe

-module(ns).
-author('').
-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)].

```