(* CS 251: Stream examples *)
exception Unimplemented
signature STREAM =
sig
(* A stream is a thunk that, when called, produces a pair of
element and remaining stream. *)
datatype 'a scons = Scons of 'a * (unit -> 'a scons)
type 'a t = unit -> 'a scons
type 'a stream = 'a t
(* Make a new stream where the first element is the given element,
and each element's successor is determined by applying the
given function to the current element. Calling this function
does not expand any stream. *)
val smake : ('a -> 'a) -> 'a -> 'a stream
(* Take the first n elements from a stream, returning a pair of:
- a list of those elements, in stream order; and
- the rest of the stream (as a stream).
Calling this function expands exactly n elements of the given
stream. *)
val stake : 'a stream -> int -> 'a list * 'a stream
(* Make a new stream where each element is the result of applying
the given function to the corresponding element of the given
stream. Calling this function does not expand any stream. *)
val smap : ('a -> 'b) -> 'a stream -> 'b stream
(* Make a new stream containing only those elemesnts of the given
stream (in order) for which the given function returns true.
Calling this function does not expand any stream. *)
val sfilter : ('a -> bool) -> 'a stream -> 'a stream
(* Make a new stream where each element is a pair of elements, one
from each of the given lists, cycling through the elements of
each list in order. Calling this function does not expand any
stream. *)
val scycle : 'a list -> 'b list -> ('a * 'b) stream
end
structure Stream :> STREAM =
struct
(* Stream representation. *)
datatype 'a scons = Scons of 'a * (unit -> 'a scons)
type 'a t = unit -> 'a scons
type 'a stream = 'a t
(* Make a new stream where the first element is init, and each
element's successor is determined by applying succ to the current
element. Calling this function does not expand any stream. *)
fun smake succ init =
let fun f x = Scons (x, fn () => f (succ x))
in fn () => f init end
(* Take the first n elements from a stream, returning a pair of:
- a list of those elements, in stream order; and
- the rest of the stream (as a stream).
Calling this function expands exactly n elements of the given
stream. *)
fun stake stream n = raise Unimplemented
(* Make a new stream where each element is the result of applying f to
the corresponding element of stream. Calling this function does
not expand any stream. *)
fun smap f stream = raise Unimplemented
(* Make a new stream containing only those elemesnts of stream (in
order) for which f returns true. Calling this function does not
expand any stream. *)
fun sfilter f stream = raise Unimplemented
(* Make a new stream where each element is a pair of elements, one
from each of the lists xs and ys, cycling through the elements of
each list in order. Calling this function does not expand any
stream. *)
fun scycle xs ys = raise Unimplemented
end
open Stream
(* A stream of ones. *)
fun ones () = Scons (1,ones)
(* Alternatively *)
val rec ones = fn x => Scons (1, ones)
(* A stream of the natural numbers from 0. *)
val nats =
let fun f x = Scons (x, fn () => f (x+1))
in fn () => f 0 end
(* A stream of powers of two from 1. *)
val powers2 =
let fun f x = Scons (x, fn () => f (x * 2))
in fn () => f 1 end
(* Build streams using smake *)
val nats = smake (fn x => x + 1) 0
val powers2 = smake (fn x => x * 2) 2
(* Count the stream elements until f returns true on one of them. *)
fun firstindex f stream =
let fun help stream ans =
let val Scons (v,s) = stream ()
in
if f v then ans else help s (ans + 1)
end
in
help stream 0
end
val four = firstindex (fn x => x=16) powers2