Time Info

In Fall 2019, students self-reported spending a median of 5.0 hours on this assignment.

Tools: Learn Emacs and SML/NJ

Take some time to read through our introductions to Emacs and SML/NJ. Emacs and SML Mode provide great support for working with SML programs and the SML interpreter, including features like clicking on errors to jump to their source code line, plus clear syntax highlighting and indentation.

Tasks

1. First Functions (10 points)

Write your code in the file first.sml.

Define a function squm that takes a nonnegative integer n and sums the squares of all numbers from 1 to n inclusive. The snippet below shows a call to squm in the SML REPL. The first line is an expression from the user; the second is output from the REPL. The REPL always binds your expression to the variable it, unless you write out a whole binding yourself. Don’t forget to type ; at the end of each line, otherwise the REPL thinks you are still entering your expression, continuing on the next line.
```
- squm (4);
val it = 30 : int
- squm (5);
val it = 55 : int
```

Define a function duplisty that takes an element e of any type and a non-negative integer n and returns a list containing n copies of e.

- duplisty ("Waban", 4);
val it = ["Waban","Waban","Waban","Waban"] : string list
- duplisty (1, 2);
val it = [1,1] : int list
- duplisty (duplisty("whale", 2), 2);
val it = [["whale","whale"],["whale","whale"]] : string list list

2. Types (25 points)

Write your responses in comments in the file types.sml.

Explain the ML type for each of the following bindings:
```
fun f1 (x,y) = 4 * x + y - x div 4
fun f2 (x,y) = y * y / 2.0
fun f3 (f,x) = case x of NONE => NONE | SOME y => f y
fun f4 (f,x) = f(f(x))
fun f5 (x,y,b) = if b(y) then x else y
```
Try to determine the type yourself, but feel free to check using the sml REPL. In addition to giving the type, you must also explain in detail why the type is correct and how you determined the type.

Note:
- 2.0 has the type real (floating point)
- the multiplication operator works either on two ints or two reals.
- div is integer division.
- / is floating point division (on reals).
What is the type of the following ML function?
```
fun append (xs,ys) =
    case xs of
      [] => ys
    | x::xs' => append (xs',ys)
```
Write one or two sentences to explain succinctly and informally why append has the type you give. This function is intended to append one list onto another. However, it has a bug. How might knowing the type of this function help the programmer to find the bug?

3. Racket to SML (25 points)

Interpreting type-checker error messages

Interpreting SML type-checker error messages takes some practice. Often they are easy to decipher, but sometimes, due to the way that type inference works, the place the error is caught is very far away from the true source of the error. Get help from the course staff if messages make no sense!

Common sources of confusing errors:

Mixing up = and => in case expressions, fun bindings, and fn definitions.
Precedence gotchas with nested case expressions. (Parenthesize!)
Missing parentheses around patterns: parenthesize all patterns in fun bindings. The structure of case patterns and syntax allows looser parenthesization without issues, but fun f x::xs = is parsed as something like fun (f x)::xs, not what you meant! Parenthesize: fun f (x::xs) =.

Rewrite some familiar functions in SML. Feel free to refer to your Racket solutions. Write your code in the file translated.sml.

Write a recursive function bits : int -> int list that takes a non-negative integer n and returns a list of the bits (0s and 1s) in the binary representation of n.

- bits (0)
val it = [] : int list
- bits (1)
val it = [1] : int list
- bits (2)
val it = [1, 0] : int list
- bits (4)
val it = [1, 0, 0] : int list
- bits (5)
val it = [1, 0, 1] : int list
- bits (10)
val it = [1, 0, 1, 0] : int list
- bits (11)
val it = [1, 0, 1, 1] : int list

Write a recursive function rev : 'a list -> 'a list that takes a list xs and reverses its order. Use tail recursion, not @.

- rev [1, 2, 3];
val it = [3, 2, 1] : int list
- rev [1, 2];
val it = [2, 1] : int list
- rev [1];
val it = [1] : int list

Assume that the elements of a list are indexed starting with 1. Write a function alts : 'a list -> 'a list * 'a list that takes a list of integers xs and returns a pair of lists, the first of which has all the odd-indexed elements (in the same relative order as in xs) and the second of which has all the even-indexed elements (in the same relative order as in xs).
```
- alts [7, 5, 4, 6, 9, 2, 8, 3];
val it = ([7, 4, 9, 8], [5, 6, 2, 3]) : (int list) * (int list)
- alts [5, 4, 6, 9, 2, 8, 3];
val it = ([5, 6, 2, 3], [4, 9, 8]) : (int list) * (int list)
- alts [4, 6, 9, 2, 8, 3];
val it = ([4, 9, 8], [6, 2, 3]) : (int list) * (int list)
- alts [3];
val it = ([3], []) : (int list) * (int list)
```
Hint: There is no need to treat even-length and odd-length cases differently, nor is there any need to treat the singleton list specially.
An association list is a list of pairs that represents a mapping from key to value. For example, the association list:
```
[("Waban", 4), ("whale", 2), ("warbler", 7)]
```
maps the key "Waban" to the value 4, the key "whale" to the value 2, and the key "warbler" to the value 7. Notice that, in SML, typing of association lists is stricter than in Racket.

Write a function lookup : (''a * 'b) list * ''a -> 'b option that takes a key k and an association list associations and returns:
- NONE if no mapping with key k was found in the list; or
- SOME (v) where v is the first value in a key-value pair in the list whose key is key.
The ''a type indicates that only types supporting the = operation are allowed.
```
- lookup ([("Waban", 4), ("whale", 2), ("warbler", 7)], "walrus");
val it = NONE : int option
- lookup ([("Waban", 4), ("whale", 2), ("warbler", 7)], "warbler");
val it = SOME 7 : int option
- lookup ([("Waban", 251), ("Waban", 4), ("whale", 2), ("warbler", 7)], "Waban");
val it = SOME 251 : int option
```
Ignore any warnings about polyEqual. We will discuss the meaning of this warning soon.
Implement a function forall : ('a -> bool) * 'a list -> bool that a one-argument predicate function f : 'a -> bool and a list xs : 'a list and:
- returns true if (f x) returns true for all x in xs;
- returns false if (f x) returns false for any x in xs, where f is defined on all elements preceding x in xs; and
- is otherwise undefined.
You may use recursion or higher-order functions.
```
- forall (fn (x) => x > 7, [34, 42, 12, 8, 73]);
val it = true : bool
- forall (fn (x) => x < 9, []);
val it = true : bool
- forall (fn (x) => 8 div x > 3, [2, 0]);
(* error *)
- forall (fn (x) => 2 = 8 div x, [8, 4, 2, 0]);
val it = false : bool
```

4. Zipping (15 points)

Write the function zip : 'a list * 'b list -> ('a * 'b) list to compute the product of two lists of arbitrary length. You should use pattern matching to define this function. If the lists have different lengths, zip should raise an exception.
```
- zip ([1,3,5,7], ["a","b","c","de"]);
val it = [(1,"a"),(3,"b"),(5,"c"),(7,"de")] : (int * string) list
```

Write the inverse function, unzip : ('a * 'b) list -> 'a list * 'b list, which behaves as follows:

- unzip [(1,"a"),(3,"b"),(5,"c"),(7,"de")];
val it = ([1,3,5,7], ["a","b","c","de"]) : int list * string list

Is it possible to write a function zip_any that takes a list of any number, n, of L-length lists and zips them into a single L-length list of n-tuples?
- If so, write such a function: zip_any [list1,list2,...,listn] should return a list of n-tuples no matter what n is.
- If not, explain why not.

Submission

Submit: The course staff will collect your work directly from your hosted repository. To submit your work:

Test your source code files one last time. Make sure that, at a minimum, submitted source code is free of syntax errors and any other static errors (such as static type errors or name/scope errors). In other words: the code does not need to complete the correct computation when invoked, but it must be a valid program. We will not grade files that do not pass this bar.
Make sure you have committed your latest changes.
```
$ git add ...
$ git commit ...
```
Run the command cs251 sign to sign your work and respond to any assignment survey questions.
```
$ cs251 sign
```
Push your signature and your latest local commits to the hosted repository.
```
$ git push
```

Confirm: All local changes have been submitted if the output of git status shows both:

Your branch is up to date with 'origin/master', meaning all local commits have been pushed
nothing to commit, meaning all local changes have been committed

Resubmit: If you realize you need to change something later, just repeat this process.

You will be SMLated.

Contents