LAB AND HOMEWORK 1 CSE 121/131, Spring, 1996

Due on Monday, Jan. 29, 9:30AM

Numbered questions are to be turned in by the date and time specified to the TA in charge of homework grading coordination (TBA). Questions marked with 's are for personal consideration or laboratory discussion.

General trees as a recursive polymorphic datatype. General trees arise when we wish to consider the situation in which a node can have more, or less, than exactly two subtrees (or ``children'' according a widely used terminology inspired by family trees), as was the case with binary trees. In our representation, we group the children of a node into a list. We will not need to consider leaves separately from nodes: the list of children of a node may simply be empty. In addition, we make no commitment about the type of the content of each node, using a type variable, and hence defining a type polymorphic trees. The declaration is compact and elegant: 

datatype 'a tree  =  Node of 'a * ('a tree) list

The constructor Node together with the constructors for lists allow us to easily define values of this type, which are general trees: 

val atree = Node(3,[Node(2,[]),
                    Node(4,[Node(8,[]),
                            Node(11,[])]),
                    Node(5,[])])
val atree = Node (3,[Node (#,#),Node (#,#), Node (#,#)]) : int tree

The purpose of this exercise is to write traversal functions, that is, functions of type 'a tree -> 'a list that produce a list of the contents of tree nodes in a specific order.

In depth-first traversal, a node n and all its descendants are visited before visiting the nodes that follow n in the list of siblings to which n belongs. In breadth-first traversal, the nodes of an entire sibling list are visited before any descendants of these nodes. Note that these definitions identify uniquely the list produced by a breadth-first traversal, while for depth-first traversal we need to further specify whether the content of a node is listed before or after that of its descendants.

  1. Write in SML the following functions:

    Turn in: The three traversal functions. The result of running them on a general tree with about 20 nodes.

(For additional fun.) In a general tree, a level is defined as the set of all nodes that have the same distance to the root. The breadth of the tree is defined as the number of nodes in its largest level. Write a function that calculates the breadth of a general tree.

Structures and signatures. You must be careful to load signatures and structures in a order that ensures each name is mentioned only after it is declared. A common problem is introducing a structure before its signature. Another is mentioning a structure that has not been loaded into the current environment.

  1. Suppose we are given the signature COMPLEX and the structure CartComplex that were defined in the lecture. Implement a structure ProductComplex that has the following signature: 
    signature PRODUCTCOMPLEX =
  sig 
    val product : CartComplex.complex list -> CartComplex.complex
  end
    where product is a function that takes a list of complex numbers and computes their product. For instance: 
    ProductComplex.product [CartComplex.descartes (1.0, 2.0), 
                        CartComplex.descartes (3.0, ~1.0)]
    returns the product of 1.0+2.0i and 3.0-1.0i. You do this by filling in the code in an expression like the following one: 
    structure ProductComplex : PRODUCTCOMPLEX =
  struct
    fun product ...
  end
    To compile your module, you must have both COMPLEX and CartComplex in your environment. Create a file that has an example in it and write a script to load the files holding the declarations and example to produce a transcript of your function in use.

    Turn in: your structure, your script, and an example of the use of your interface function on a list with at least three elements.

This process may seem somewhat tedious for the example above, but when your program is large it may be the only practical way to proceed.

Exploiting linear orders. A linear order is a binary relation that satisfies four properties. First, it is reflexive: x x. Second, it is anti-symmetric: x y and y x implies x=y. Third, it is transitive: x y and y z implies x z. Fourth, it is linear: either x y or y x. In SML, it is natural to represent a linear ordering on elements of a type t as a function of type t * t -> bool. Linear orderings are often useful in optimizing searches.

What are some examples of linear orders? What are some examples of function having type t * t -> bool that are not linear orders?

We also need to talk about equality. It is not always possible to tell if two elements of a type are equal. For instance, this is `counter-recommended' for real values (because of possible rounding error) and impossible for function spaces.

Why is it impossible to tell whether two functions of type int -> int are equal even though it is possible to tell if two elements of type int are equal? What do we mean by ``tell'' in the previous two sentences?

Is it possible to give a linear ordering for the functions of type int -> int? Why is it dangerous to use vague formulations like ``give'' in the previous sentence and ``tell'' in the previous paragraph when we try to express precise facts?

SML has a distinguished notation for type variables ranging over types on which equality is defined. These are marked with two quote symbols, ''a, rather than the more general case, 'a, that uses only one.

  1. Build a structure GroupBy to implement the following signature: 
    signature GROUPBY =
  sig
    val eq : 'a list * ('a -> ''b) -> (''b * 'a list) list
    val comp : a' list * ('a -> 'b) * ('b * 'b -> bool) -> ('b * 'a list) list
  end
    by filling in the necessary code in the following structure declaration: 
    structure GroupBy : GROUPBY =
  struct
    fun eq ...
    fun com ...
  end
    The semantics of the two interface operations is described as follows. Applying the function eq to a pair (l, f ) returns a list of pairs (x, f -1 (x)) such that x is an element of type ''b and f -1(x) is a non-empty list of all of the elements from l that f maps to x. For example, 
    GroupBy.eq ([1,4,6,7,9,45,32], even)
    gives 
    [(true, [4,6,32]), (false, [1,7,9,45])]
    and 
    GroupBy.eq (["one", "two", "three", "four", "five", "six",
             "seven", "eight", "nine", "ten", "eleven"],
            size)
    gives 
    [(6, ["eleven"]),
 (3, ["one", "two", "six", "ten"]),
 (4, ["four", "five", "nine"]),
 (5, ["three", "seven", "eight"])]
    The function comp is essentially the same, but it is given a third parameter which is assumed to be a linear ordering on the type 'b. You must find a way to use this additional parameter in order to achieve a more efficient implementation than eq.

    Turn in: Your structure and examples illustrating the use of the eq and comp functions in its interface.

What might happen if the the third parameter of GroupBy.comp failed to be a linear order?