CSPP 51091
Winter, 2007

Homework 5 Solutions
Due 2/20/07

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

Ex. 6.2.2

datatype 'label btree
  = Empty 
  | Node of 'label * 'label btree * 'label btree;

type ('a, 'b) mapTree = ('a * 'b) btree
val t1 = Node(("a",1),Empty,Empty)
(* t1: (string,int) mapTree *)

Ex. 6.3.2

(a)
exception Missing

(* lookup: ('a * 'a -> bool) -> ('a,'b) mapTree -> 'a -> 'b *)
fun lookup lt Empty a = raise Missing
  | lookup lt (Node((c,b), left, right)) a =
      if lt(a,c) then lookup lt left a
      else if lt(c,a) then lookup lt right a
      else b (* when a=c *)

(b)
(* assign: ('a * 'a -> bool) -> ('a,'b) mapTree -> 'a -> 'b -> ('a,'b) mapTree *)
fun assign lt Empty a b = Node((a,b), Empty, Empty)
  | assign lt (Node((c,d), left, right)) =
      if lt(a,c) then assign lt left a b
      else if lt(c,a) then assign lt right a b
      else Node((a,b), left, right)) (* when a=c *)

Ex. 6.3.5
(* The original preOrder function from Section 6.3.7 *)
(* preOrder : 'a btree -> 'a list *)
fun preOrder(Empty) = nil
  | preOrder(Node(a, left, right)) =
      [a] @ preOrder left @ preOrder right

(* preOrder' : 'a btree -> 'a list *)
(* we accumulate the result list in the second argument of
 * preOrder1, but the elements are accumulated in the reverse
 * order by consing, so we call preOrder1 on the right subtree first,
 * then on the left subtree, and finally we cons on the current label
 * value. *)
fun preOrder'(t : 'a btree) =
  let fun preOrder1(Empty, l) = l
        | preOrder1(Node(a, left, right), l) = 
            a::preOrder1(left, preOrder1(right, l))
   in preOrder1(t,nil)
  end


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

Ans:

  fun smap f Snil = Snil
    | smap f (Scons(x,s)) = Scons(f x, (fn () => smap f (s())))


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

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

Ans:

  fun sfilter f Snil = Snil
    | sfilter f (Scons(x,s)) =
	if f x then Scons(x, (fn () => sfilter f (s())))
        else sfilter f (s())


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

  val fileToStream : TextIO.instream -> char stream

Ans:

  fun fileToStream (ins : TextIO.instream) : char stream =
      (case TextIO.input1 ins
	 of NONE => Snil
	  | SOME c => Scons(c, (fn () => fileToStream ins))


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

Ans:

  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

Ans:

  fun interleave(Snil, Snil) = Snil
    | interleave(Scons(x,s1),s2) =
	Scons(x, (fn() => interleave(s2,s1())


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

Ans:

First we define a function that takes to streams and produces
a stream of streams, where each stream element is pairs an
element from the first stream with all elements of the second
stream.

  fun pairStreams (s1,s2) = smap (fn x => smap (fn y => (x,y)) s2) s1

Now we define a function that will interleave all the elements
in a stream of streams.

  fun enumerate Snil = Snil
    | enumerate (Scons(Snil,s)) = enumerate(s())
    | enumerate (Scons(Scons(x,s1),s2)) =
        Scons(x, interleave(enumerate(s2()), s1()))

Now we define prod in terms of pairStreams and enumerate:

  fun prod(s1,s2) = enumerate(pairStreams(s1,s2))


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();

Ans: This produces the stream consisting of the members of the
Fibonacci sequence:

- stake (a, 10);
val it = [1,1,2,3,5,8,13,21,34,55] : int list


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.

Ans:

  fun sift p = sfilter (fn n => n mod p <> 0)

  fun sieve (Scons(p,s)) = Scons(p, (fn () => sieve (sift p (s()))))

  val primes = sieve (from 2)


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

Consider, for instance, the use of streams in the revised parser
for Ex 5.7.2 in Homework 6.