(* Example: implementing the Sieve of Eratosthenes using first-class structures*)fun divides divisor n = (n mod divisor) = 0;(* the signature "Stream" of structures representing integer streams: a stream is represented as an infinite state process that emits a sequence of integer values*)signature Stream = sig type state; (* states are opaque *) val start: state; (* the initial state *) val next: state -> state; (* the state transition function *) val value: state -> int (* the value of a state *) end;(* the Core function "sift s" takes a packaged stream s and returns the packaged stream obtained by removing all value from s that are divisible by the initial value of s*)fun sift s = let structure S as Stream = s (* open the package s as the structure S*) in [structure (* create a new package from S *) struct val divisor = S.value S.start; fun filter state = if divides divisor (S.value state) then (filter (S.next state)) else state; type state = S.state; val start = filter S.start; fun next state = filter (S.next state); val value = S.value end as Stream] end;(* the implementation of the Sieve *)structure Sieve = struct type state = [Stream]; (* the type of package Streams *) val start = [structure (* the stream 2,3,4,5 .... *) struct type state = int; val start = 2; fun next n = n + 1; fun value state = state end as Stream]; val next = sift; fun value state = let structure S as Stream = state in S.value S.start end end :> Stream;(* the function "nthstate n" returns the nth state of the sieve *)fun nthstate 0 = Sieve.start | nthstate n = Sieve.next (nthstate (n -1));(* the function "nthprime n" returns the nth prime *)val nthprime = fn n => Sieve.value (nthstate n);val primes = let fun primes n state = if n <= 0 then [] else (Sieve.value state) :: (primes (n-1) (Sieve.next state)) in fn n => primes n Sieve.start end;val hundred_primes = primes 100;val test = if primes 5 = [2,3,5,7,11] then "OK" else "FAIL";
(* Example: implementing the Sieve of Eratosthenes
using first-class structures
*)
fun divides divisor n = (n mod divisor) = 0;
(* the signature "Stream" of structures representing integer streams:
a stream is represented as an infinite state process
that emits a sequence of integer values
*)
signature Stream =
sig type state; (* states are opaque *)
val start: state; (* the initial state *)
val next: state -> state; (* the state transition function *)
val value: state -> int (* the value of a state *)
end;
(* the Core function "sift s" takes a packaged stream s
and returns the packaged stream obtained by removing
all value from s that are divisible by the initial value of s
*)
fun sift s =
let structure S as Stream = s (* open the package s as the structure S*)
in
[structure (* create a new package from S *)
struct
val divisor = S.value S.start;
fun filter state =
if divides divisor (S.value state)
then (filter (S.next state))
else state;
type state = S.state;
val start = filter S.start;
fun next state = filter (S.next state);
val value = S.value
end
as Stream]
end;
(* the implementation of the Sieve *)
structure Sieve =
struct
type state = [Stream]; (* the type of package Streams *)
val start = [structure (* the stream 2,3,4,5 .... *)
struct
type state = int;
val start = 2;
fun next n = n + 1;
fun value state = state
end
as Stream];
val next = sift;
fun value state = let structure S as Stream = state
in S.value S.start
end
end :> Stream;
(* the function "nthstate n" returns the nth state of the sieve *)
fun nthstate 0 = Sieve.start
| nthstate n = Sieve.next (nthstate (n -1));
(* the function "nthprime n" returns the nth prime *)
val nthprime = fn n => Sieve.value (nthstate n);
val primes =
let fun primes n state =
if n <= 0
then []
else
(Sieve.value state) :: (primes (n-1) (Sieve.next state))
in fn n => primes n Sieve.start
end;
val hundred_primes = primes 100;
val test = if primes 5 = [2,3,5,7,11] then "OK" else "FAIL";