CSCI 384 FALL 2021

HOMEWORK 4:

SML lists and datatypes

Exercises 1, 2, 3, and 4 Due: Monday, 9/27 at 3pm.
Exercises 5, 6, and 7 Due: Wednesday, 9/29 at 3pm.
Exercise 8 Due: Monday, 10/4 at 3pm.

The exercises below test your understanding of SML’s list type and SML’s datatype facility. You will be asked to define several (typically recursive) functions as prescribed by each problem. In one case, you will also devise a datatype.

For all of these, feel free to work from my sample code hw4start.sml, either by cutting and pasting its code, or by loading its definitions into SML before loading them in. The command

rlwrap sml hw4start.sml exercise1.sml

will load the definitions in hw4start.sml before loading the definitions in exercise1.sml. Within that starting SML source, I’ve included the definitions of map, foldl, foldr, and filter, the datatype definitions of bstree and arith, and sample code that works with these two datatypes.

You might be tempted, now and then, to use map, etc. in the definitions of your functions. This is a good instinct, and one that you can follow, though you don’t have to. You can write all the functions (and/or any helper functions you’d like to support them) recursively. But it is also common practice to use map, fold, and filter in place of writing hand-built recursive definitions for your functions.

Note: My starting code includes semicolons at the end of each definition. This really shouldn’t be necessary. As a matter of fact, in past teaching I have discouraged the use of these semicolons. But, for some reason, in the latest SML interpreter I have need to included them so that the type report for each definition appears on its own line when SML loads the file. Oh well! Without them, the interpreter seems to keep indenting each report, further and further right.

Exercise 1: removeDuplicates

Write an SML function

removeDuplicates : ''a list -> ''a list

It takes a list of items, with some items possibly repeated, and returns a list of the same collection of items, but with none repeated. So for example

- removeDuplicates [1,1,3,2,1,4,2,3];
val it = [1,3,2,4] : int list
- removeDuplicates ["x","y","y","z","x","w","z"];
val it = ["x","y","z","w"] : string list

To do this, you will have to test whether list elements are equal. Not all types in SML allow for equality testing. For example, you can’t test whether functions f, g : int -> int are equal. And so that is the reason for the “double tick” in the type variable ''a. It stands for any type that has an equality predicate.

When you load the function, you’ll get the warning

Warning: calling polyEqual

This is because SML’s type system notices this type restriction when it works to generalize its understanding of the “polymorphic” aspect of the function’s type. The function is polymorphic in that it works on lots of list types, just not all lists.

Exercise 2: prefixSum and suffixSum

Write two SML functions

prefixSum : int list -> int list
suffixSum : int list -> int list

The prefix sum of the list

[x1, x2, ... , xk]

is the list with

[y1, y2, ... , yk]

where

yi = x1 + x2 + ... + xi

That is to say: the i-th element is the sum of the first i items of the original list.

The prefix sum is similar. It is the list

[z1, z2, ... , zk]

where

zi = xi + ... + xk

That is to say: the i-th element is the sum of the last k - i + 1 items of the original list.

We want

- prefixSum [1,2,3,4,5];
val it = [1,3,6,10,15] : int list
- suffixSum [1,2,3,4,5];
val it = [15,14,12,9,5] : int list

Exercise 3: table

Write an SML function

table : ('a * 'b -> 'c) -> 'a list -> 'b list
            -> ('a * 'b * 'c) list list

The type looks somewhat complicated, so let’s imagine it has this definition to describe it

fun table bop xs ys = ...

The function attempts, using a list of lists, to present a “multiplication table” for a binary operation bop, one whose rows correspond to the elements from a list xs, and one whose columns correspond to the elements from a list ys.

And so the type of bop is such that it is a binary operation that takes elements from the first list xs (on the left) and elements from the second list yson its right. So, if we say that xs is an 'a list and ys is a 'b list, then we expect

bop : 'a * 'b -> 'c

I want the “entries” in the table to be of the form

(x, y, bop(x,y))

that is, a triple consisting of an element of xs, an element of ys, and the result of bop on those two elements.

The result should be a list of lists, i.e.

(('a * 'b * 'c) list) list

where each of the list elements is a row in the table. So for example, we might have this interaction

- table (fn (x,y) => x*10 + y) [1,2,3] [5,6,7,8];
val it =
  [[(1,5,15),(1,6,16),(1,7,17),(1,8,18)],
   [(2,5,25),(2,6,26),(2,7,27),(2,8,28)],
   [(3,5,35),(3,6,36),(3,7,37),(3,8,38)]]
 : (int * int * int) list list
- table (fn (x,y) => x <= y) [1,2,3,4] [1,2,3,4];
val it =
  [[(1,1,true),(1,2,true),(1,3,true),(1,4,true)],
   [(2,1,false),(2,2,true),(2,3,true),(2,4,true)],
   [(3,1,false),(3,2,false),(3,3,true),(3,4,true)],
   [(4,1,false),(4,2,false),(4,3,false),(4,4,true)]]
 : (int * int * bool) list list

Exercise 4: binaries

Write a function

binaries : int -> string list

that, when given a natural number n, lists all the binary strings of length n. For example,

- binaries 3;
val it = ["000","001","010","011","100","101","110","111"]
 : string list

To do this, you should know that string concatenation can be performed with the operator ^, as in:

- "hello" ^ "goodbye";
val it = "hellogoodbye" : string

Exercise 5: without and flatten

• Write a function without that has the type

without : bstree * int -> bstree

It should take a binary search tree and an integer key and return the tree that results from removing that key from it.

- val t = Br (3,Br (1,Lf,Br (2,Lf,Lf)),
                Br (5,Br (4,Lf,Lf),Br (6,Lf,Lf)));
- without (t,5);
val it = Br (3,Br (1,Lf,Br (2,Lf,Lf)),
               Br (4,Lf,Br (6,Lf,Lf))) : bstree

It is possible to tell SML that functions that act on pairs are binary infix operations. The way you do this is with the infix directive. If you look at the starter code, you’ll see that I declare the function withAll to be an infix operation. This means that you can enter

- Lf withAll [3,1,2,5,4,6];
val it = Br (3,Br (1,Lf,Br (2,Lf,Lf)),
         Br (4,Lf,Br (6,Lf,Lf))) : bstree

If you include infix without in your code, you could then enter

- (Lf withAll [3,1,2,5,4,6]) without 5;
val it = Br (3,Br (1,Lf,Br (2,Lf,Lf)),
               Br (4,Lf,Br (6,Lf,Lf))) : bstree

instead.

• Now write a function

flatten : bstree -> int list

that produces the list of the keys stored in a binary search tree, and in their sorted order:

- flatten (Lf withAll [3,1,2,5,4,6]);
val it = [1,2,3,4,5,6] : int list

It is tempting to write this code so that it relies on the list concatenation operation @, shown below:

- [1,2] @ [3] @ [4,5,6];
val it = [1,2,3,4,5,6] : int list

Write the code so that it does not use the @ operation, only the :: operation.

Exercise 6: varsOf

Write a function

varsOf : arith -> string list

that gives a list of all the variables that occur in the arithmetic term it is given. For example:

- varsOf (Negate (Plus (Times (Var "x", Var "z"), Var "x")));
val it = ["x","z"] : string list

Note that it lists each variable only once. Yours should not produce a list with any duplicated variables.

It is okay to use the @ operation to write this function’s code.

Exercise 7: subst

Write a function

subst : string -> arith -> arith

that, when defined like

fun subst x a e = ...

replaces all occurrences of the variable named x with the term a inside of the term e.

- subst "x" (Num 4) (Negate(Plus(Times(Var "x",Var "z"),Var "x")))
val it = (Negate(Plus(Times(Num 4,Var "z"),Num 4)))
 : arith

Exercise 8: isTautology

Invent a new SML datatype called prop that defines terms of logical propositions. It should have constructors for And, Or, Not, Implies and Equiv, corresponding to those logical connectives. It should have an additional constructor

Sym : string -> prop

that represents propositional variables. We know from logic that

(p => q) <=> (~q => ~p)

and that

~(p /\ q) <=> (~p \/ ~q)

The first is a fact about the contrapositive. The second is one of DeMorgan’s laws. These two propositions are tautologies and would be represented by the terms cp and dm given by:

val cpl = Implies(Sym "p",Sym "q")
val cpr = Implies(Not(Sym "q"),Not(Sym "p"))
val cp  = Equiv(cpl,cpr)
val dml = Not(And(Sym "p",Sym "q"))
val dmr = Or(Not(Sym "p"),Not(Sym "q"))
val dm  = Equiv(dml,dmr)

Now write a function:

tautology : prop -> bool

that determines whether or not a proposition is always true.

- tautology cp;
val it = true : bool;
- tautology dm;
val it = true : bool;
- tautology (Equiv (dml,cpl));
val it = false : bool;