COP 4555 - Homework 2

Due Monday, February 14

Solve each of the following SML programming exercises. Remember that you can put comments in your code like this: (* Here's a comment. *). Be sure to include a comment for each of your functions that tells what type SML infers for it.

[Note that Standard ML of New Jersey ordinarily prints only the first 12 items in a list. If you enter the command

  Compiler.Control.Print.printLength := 1000;

it will print the first 1000 items instead.]

Write an SML function revlsts xs that takes a list of lists xs and reverses all the sub-lists:
```
  - revlists [[0,1,1],[3,2],[],[5]];
  val it = [[1,1,0],[2,3],[],[5]] : int list list
```
Note that this is extremely easy to do, using map.
Write an SML function nth (xs, n) that returns the nth element of list xs, counting from 0 as the first element:
```
  - nth (["a","b","c","d","e"], 3);
  val it = "d" : string
```
Don't worry about what happens if n is out of bounds.
By the way, List.nth is actually a built-in function. Needless to say, you aren't allowed to use it in solving this problem!
Write an SML function middle xs that returns the middle element of list xs:
```
  - middle [1,2,3,4,5];
  val it = 3 : int
```
If the list has an even number of elements, return the first element of the second half of the list:
```
  - middle [true, false];
  val it = false : bool
```
Write a curried SML function cartesian xs ys that takes as input two lists xs and ys and returns a list of pairs that represents the Cartesian product of xs and ys. (The pairs in the Cartesian product may appear in any order.) For example,
```
  - cartesian ["a","b","c"] [1,2];
  val it = [("a",1),("a",2),("b",1),("b",2),("c",1),("c",2)]
	   : (string * int) list
```

Here is an SML mergesort program:

  fun merge([], ys) = ys
  |   merge(xs, []) = xs
  |   merge(x::xs, y::ys) =
          if x < y then x::merge(xs, y::ys)
          else y::merge(x::xs, ys)

  fun split []         = ([],[])
  |   split [a]        = ([a],[])
  |   split (a::b::cs) =
        let val (M,N) = split cs in
          (a::M, b::N)
        end

  fun mergesort []  = []
  |   mergesort [a] = [a]
  |   mergesort [a,b] = if a <= b then [a,b] else [b,a]
  |   mergesort L  =
        let val (M,N) = split L
        in
          merge (mergesort M, mergesort N)
        end

Note that mergesort includes three base cases ([], [a], [a,b]) and all are handled correctly.

Suppose we delete the third line of mergesort, so that [a,b] is no longer handled as a base case. You can verify that this change makes no difference in the type of mergesort or in its behavior.

Now suppose we also delete the second line of mergesort, leaving

  fun mergesort []  = []
  |   mergesort L  =
        let val (M,N) = split L
        in
          merge (mergesort M, mergesort N)
        end

What effect does this change have on the type that SML infers for mergesort? You can verify that mergesort no longer works correctly. Explain what has gone wrong, referring explicitly to the three steps in the "Checklist for Programming with Recursion" presented in class.

Back to

smithg@cs.fiu.edu