CSPP 51091

Homework 2 Solutions
Due 1/30/07

Chapter 3

Section 3.3.7 (Page 74)
3.3.1 b:
fun cycle [] = []
  | cycle (y as [x]) = y      (* redundant, but slightly more efficient)
  | cycle (x::xs) = xs @ [x]

3.3.1 c:
(* quadratic version -- see 3.5.2 below for linear version *)
fun cyclen (_,nil) = nil
  | cyclen (0,l) = l
  | cyclen (i,x::xs) = cyclen(i-1, xs@[x])

3.3.1 e:
fun exp(x,0) = 1.0
  | exp(x,n) = x * exp(x,n-1)

3.3.2
fun flip2 (x::y::xs) = y::x::flip2 xs
  | flip2 (y as [x]) = y
  | flip2 nil = nil

3.3.3
(* delete ith element of a list, indexing from 1.
 * diverges if i < 1, returns unchanged list if i > length of list *)
fun delete(nil,i) = nil
  | delete(x::xs,1) = xs
  | delete(x::xs,i) = x::delete(xs,i-1)

3.3.4
fun sumLists nil = 0
  | sumLists (nil::YS) = sumLists YS
  | sumLists ((x::xs)::YS) = x + sumLists(xs::YS)

sumLists([[1,2],nil,[3]])
  x = 1, xs = [2], YS = [nil,[3]] (equation 3)
  => 1 + sumList([[2],nil,[3]])
     x = 2, xs = nil, YS = [nil,[3]] (equation 3)
     => 1 + 2 + sumList([nil,nil,[3]])
        YS = [nil,[3]] (equation 2)
        => 1 + 2 + sumlist([nil,[3]])
           YS = [[3]] (equation 2)
           => 1 + 2 + sumList([[3]])
              x = 3, xs = nil, YS = nil (equation 3)
              => 1 + 2 + 3 + sumList([nil])
                 YS = nil (equation 2)
	         => 1 + 2 + 3 + sumList nil (equation 1)
                    => 1 + 2 + 3 + 0  ... => 6

3.3.5 b
Yes: x = "a", y = "b", zs = nil, w = 4.5

3.3.6
This problem is broken, because [(x,y),zs] cannot match the 
expression [((1,2),3)]. The pattern has the type ('a * 'b) list
for some 'a and 'b, while the expression has the type 
((int * int) * int) list, so the types are compatible
('a |-> int * int, 'b |-> int), but a value matching the 
pattern must be a list of length exactly 2, and the expression
is a list of length 1.  We can correct this so that the expression
matches the pattern by changing the expression to [(1,2),(3,4)].

See file fig3_3_6.pdf for the matching diagram for this modified
version. 

3.3.9
fun isVowel (#"a"::_) = true
  | isVowel (#"e"::_) = true
  | isVowel (#"i"::_) = true
  | isVowel (#"o"::_) = true 
  | isVowel (#"u"::_) = true
  | isVowel _ = false

Or, equivalently, using SML/NJ OR-patterns:

fun isVowel ((#"a" | #"e" | #"i" | #"o" | #"u")::_) = true
  | isVowel _ = false

---------------
3.3.11 b
fun delete(x,nil) = nil
  | delete(x,y::ys) = 
    if x = y then ys else y :: delete(x,ys)

Note that this will have the equality polymorphic type

  val delete = fn : ''a * ''a list -> ''a list

because of the unavoidable use of equality in the second
clause of the function definition.  So delete will not work
on lists of functions, for instance.  The member and insert
functions also depend on equality of members, and so will
also have equality polymorphic types.

3.3.16
fun sumPairs nil = 0
  | sumPairs((x,y)::zs) = x + y + sumPairs zs;
val sumPairs = fn : (int * int) list -> int

In the first clause the return value of 0 indicates that
sumPairs is a list returning int, and the nil argument
pattern indicates that the argument type is a list type.
In the second clause, the argument pattern indicates
that the argument type must be a list of pairs of type
('X * 'Y) list for some types 'X and 'Y such that
x: 'X and y: 'Y. We know the rhs of this rule:

    (x + y) + sumPairs zs

must have type int to agree with the first rule, so the
top-level + operator (the second one) must be integer
+ : int * int -> int. So its first argument, the expression
(x + y) must have type int, meaning that this is also the
integer + operator. This in turn implies that x and y must
have type int, i.e. 'X = int and 'Y = int. So the argument
type is determined to be (int * int) list, and the type
of sumPairs is therefore (int * int) list -> int.


Section 3.4.5 (Page 83)

3.4.2
fun split nil = (nil,nil)
  | split [a] = ([a],nil)
  | split (a::b::cs) = 
    let val x = split cs
     in (a :: (#1 x), b :: (#2 x))
    end

3.4.4
[There is a typo in the exercise: it refers to 
exercise 3.2.1(e), but this should be 3.2.1(f)]
fun max (nil: real list) = raise Fail "max nil"  (* for completeness *)
  | max [x] = x
  | max (x::xs) = 
    let val m = max xs
     in if x > m then x else m
    end 

Here is a tail recursive version:

fun max (nil: real list) = raise Fail "max nil"  (* for completeness *)
  | max (x::xs) = 
    let fun search(y,z::zs) =
              if z > y then search(z,zs) else search(y,zs)
          | search(y,nil) = y
     in search(x,xs)
    end 

3.4.6
fun sumPairs1 nil = (0,0)
  | sumPairs1((x,y)::zs) =
    let val (sx,sy) = sumPairs1 zs
     in (x + sx, y + sy)
    end;
val sumPairs1 = fn : (int * int) list -> int * int


Section 3.5.5 (Page 88)
3.5.2
(* linear, tail recursive version *)
fun cyclen (i,l) =
    let val k = i mod (length l)
            (* don't need to cycle more than length l places *)
	fun cyc(n,nil,ys) = nil
	  | cyc(0,xs,nil) = xs
	  | cyc(0,xs,ys) = xs @ (rev ys)
	  | cyc(n,x::xs,ys) = cyc(n-1,xs,x::ys)
     in cyc(k,l,nil)
    end

(* version using library functions drop and take *)
fun cyclen (i,l) = (* assume i >= 0 *)
    let val k = i mod (length l)  (* 0 <= k <= length l - 1 *)
     in if k = 0 then l else drop(l,k) @ take(l,k)
    end

Section 3.6.7 (Page 98)
3.6.3
(* Horner's algorithm: *)

fun evalPoly(nil,a:real) = 0.0
  | evalPoly(c::cs, a) = c + a * evalPoly(cs,a)


Chapter 4

Section 4.1.5 (Page 107)

4.1.2 (see Example 3.10, Page 59)

fun combpr(n,m) = 
    let fun comb(n,m) =
	if m = 0 orelse m = n then 1
	else comb(n-1,m) + comb(n-1,m-1)
     in print(concat["n = ",Int.toString n,", m = ",Int.toString m,
                     "\ncomb(n,m) = ",Int.toString(comb(n,m)),"\n"])
    end;


Section 4.2.8 (Page 115)
4.2.1 c:
TextIO.inputN(in2,5);
(or, if TextIO has been opened)
inputN(in2,5);

4.2.1 e:
TextIO.input(in4);
(or, if TextIO has been opened)
input(in4);

4.2.1 f:
valOf(TextIO.lookahead TextIO.stdIn);
(or, if TextIO has been opened)
valOf(lookahead stdIn);  (* raises Option if no character available *)

4.2.2 b
- val x = input1 infile;
val x = SOME #"a" : elem option
- val x = input1 infile;
val x = SOME #"b" : elem option
- val x = input1 infile;
val x = SOME #"c" : elem option
- val x = input1 infile;
val x = SOME #"\n" : elem option
- val x = input1 infile;
val x = SOME #"d" : elem option
- val x = input1 infile;
val x = SOME #"e" : elem option
- val x = input1 infile;
val x = SOME #"\n" : elem option
- val x = input1 infile;
val x = SOME #"f" : elem option
- val x = input1 infile;
val x = SOME #"\n" : elem option
- val x = input1 infile;
val x = NONE : elem option
- 

4.2.3 b:
SOME 123 : int option

4.2.3 d:
fun f() = SOME true;
val f = fn : unit -> bool option

Section 4.3.4 (Page 118)
4.3.1 b:
TextIO.openAppend "/usr/spool/mail/fred";

4.3.1 c:
TextIO.closeOut out1;

Section 4.4.6 (Page 126)

4.4.2
fun makeList1(infile, NONE) = nil
  | makeList1(infile, SOME c) = 
      c :: makeList infile

and makeList infile = makeList1(infile, input1(infile));

val makeList1 = fn : instream * elem option -> elem list
val makeList = fn : instream -> elem list