Prime number generator with lazy evaluation in Erlang: See http://erlang.org/pipermail/erlang-questions/1999-March/000176.html

p3.erl

%%% Prime number sieve code with lazy evaluation by Joe Armstrong
%%% (very slightly modified for syntax check)
%%% http://erlang.org/pipermail/erlang-questions/1999-March/000176.html

-module(p3).

-export([from/1,filter/2,sift/2,sieve/1,primes/0, first/1]).

%% This generates a lazy sequence starting from K.
%% from(K) ->
%%    fun() ->
%%    [K| from(K+1)]
%%    end.

from(K) -> [K|fun()->from(K+1)end].


%% This applies the Pred to each element of the list and returns a list
%% containing those elements which satisfies Pred.

filter(_,[]) -> [];
filter(Pred,[H|Tl]) ->
    case Pred(H) of
	true ->
	    [H|fun() -> filter(Pred,Tl()) end];
	false ->
	    filter(Pred,Tl())
    end.

%% This function simply calls filter/2.
sift(P,L) -> filter(fun(N) -> N rem P /= 0 end,L).

%% This generates a lazy list after removing all the multiples of H.
sieve([H|Tl]) -> 
    [H|fun() -> sieve(sift(H,Tl())) end].

%% This generates the list of prime numbers.
primes() -> sieve(from(2)).

first(N) -> first(N, primes()).

first(0, _) -> true;
first(N, [X|P]) ->
    io:format("generated:~p~n",[X]),
    P1 = P(),
    first(N-1, P1).

primes.ghc.prolog

%%% Prime number generator in Guarded Horn Clauses
%%% Source:
%%% Kazunori Ueda, "Guarded Horn Clauses", Section 4.6.2 "Generating Primes", p. 66,
%%% PhD Thesis at the University of Tokyo, 1986,
%%% http://www.ueda.info.waseda.ac.jp/~ueda/pub/GHCthesis.pdf

primes(Max,Ps) :- true | gen(2,Max,Ns), sift(Ns,Ps).

gen(N,Max,Ns) :- N=<Max | Ns=[N|Ns1], N1:=N+1, gen(N1,Max,Ns1).
gen(N,Max,Ns) :- N> Max | Ns=[].

sift([P|Xs],Zs) :- true | Zs=[P|Zs1], filter(P,Xs,Ys), sift(Ys,Zs1).
sift([], Zs)    :- true | Zs=[].

filter(P,[X|Xs],Ys) :- X mod P=:=0 |             filter(P,Xs,Ys).
filter(P,[X|Xs],Ys) :- X mod P=\=0 | Ys=[X|Ys1], filter(P,Xs,Ys1).
filter(P,[], Ys)    :- true        | Ys=[].

See also https://github.com/videlalvaro/erlang-prime-sieve