CSPP 51091
Winter, 2007

Homework 5
Due 2/20/07

1. Read Chapter 6 and do Exercise 6.2.2, 6.3.2, 6.3.5.

2. Infinite streams:

We can create infinite data structures. The most common example
is a stream. A stream is like a list, but with potentially
infinitely many members.

datatype 'a stream = Snil | Scons of 'a * (unit -> 'a stream)

Here are some basic operations on streams:

(* snull : 'a stream -> bool *)
fun snull Snil = true
  | snull _ = false

(* shd : 'a stream -> 'a *)
fun shd Snil = raise Empty (* same as for lists *)
  | shd (Scons(x,_)) = x

(* stl : 'a stream -> 'a stream *)
fun stl Snil = raise Empty (* same as for lists *)
  | stl (Scons(_,f)) = f()

(* scons: 'a * 'a stream -> 'a stream *)
fun scons(x,s) = Scons(x,(fn () => s))

The append function for streams.

(* sappend: 'a stream * 'a stream -> 'a stream *)
fun sappend (Snil,s) = s
  | sappend (Scons(x,s),s') = Scons(x, (fn () => (sappend(s,s'))))

Here is a function that turns a list into a stream:

(* fromList : 'a list -> 'a stream *)
fun fromList l = foldr scons Snil l

The following function produces an infinite stream
consisting of the ascending sequence of integers
starting from k.

(* from : int -> int stream *)
fun from (k:int) = Scons(k, (fn () => from(k+1)))

Here is a function that takes a function and a
base value and produces the stream generated by
applying the function repeatedly to the base value.

(* iterate : ('a -> 'a) -> 'a -> 'a stream *)
fun interate f i = Scons(i, (fn () => interate f (f i))

fun stake (s,0) = nil
  | stake (Snil,k) = nil
  | stake (Scons(x,s),k) = x :: stake(s(),k-1)

2a: Define a smap function for streams analogous to
the map function for lists.

  val smap: ('a -> 'b) -> 'a stream -> 'a stream

2b: Define a sfilter function to filter a stream,
analogous with the filter function for lists.

  val sfilter: ('a -> bool) -> 'a stream -> 'a stream

2c: Define a function that transforms a TextIO.instream
into char stream.

  val fileToStream : TextIO.instream -> char stream

2d: Define a function to add two int streams, element
by element (what is a natural thing to do if one of
the streams terminates before the other?).

  val splus : int stream * int stream -> int stream

  fun splus(Snil,s) = s
    | splus(s,Snil) = s
    | splus(Scons(x1,s1), Scons(x2,s2)) = Scons(x1+x2, (fn() => splus(s1(),s2())));

2e: Define a function that interleaves (shuffles) two
streams, beginning with the first element of the first
stream.

  val interleave : 'a stream * 'a stream -> 'a stream

2g: Define a function sprod that takes two streams and
produces the stream of all ordered pairs of elements from
the first stream and the second stream.
 
  val sprod: 'a stream * 'b stream -> ('a * 'b) stream

2h: What is the stream a defined by:

  fun s () = Scons(1,
                  (fn () => Scons(1,
                                  (fn () => 
				      let val s' = s()
				       in (splus(s', stl s'))
				      end))));

  val a = s();

2i: [Bonus: Sieve of Eratosthenes]. Give a definition of a
stream consisting of all prime numbers in ascending order
(i.e. the stream should start with 1, 2, 3, 5, 7, 11, 13, 17, 19,
...).  Hint: You will want to use filters of the form

   sfilter (fn n => n mod k <> 0)

for each prime number k (k >= 2) to remove the composite numbers.

2j: [Bonus] Think up some more interesting operations on, or
applications of streams.