code Trees for data and program representation via algebraic datatypes and pattern-matching, plus random art

Assign: Tuesday, 8 October
Due: 11:59pm Friday, 18 October
Policy: Pair graded synthesis assignment
Partner search: Find a partner here.
Code: cs251 start art
Submit: git commit, cs251 sign, and git push your completed code.
Reference:

Tasks

Note: the first SML assignment was smaller than previous assignments. This one will take more time than the first SML assignment.

1. Binary Trees (35 points)

Write code for this part in the file trees.sml.

Binary trees can be represented by the following datatype in ML:

datatype 'a bintree = Empty | Node of 'a * 'a bintree * 'a bintree

For example, this tree has root 7, internal nodes 1 and 9, and leaves (from left to right) 3, 8, 21. It also happens to be a binary search tree.

val bt = Node (7,
               Node (1,
                     Empty,
                     Node (3, Empty, Empty)),
               Node (9,
                     Node (8, Empty, Empty),
                     Node (21, Empty, Empty)))

Write a function bintree_sum : int bintree -> int that sums all node values in the given binary tree.
```
- bintree_sum bt;
val it = 49 : int
- bintree_sum Empty;
val it = 0 : int
```

Write a function bintree_map : ('a -> 'b) * 'a bintree -> 'b bintree that takes a mapping function and a binary tree and returns a new binary tree of the same shape, where each element is the result of applying the mapping function to the corresponding element in the original tree.

- bintree_map (String.size, (Node ("like",
                                   Node ("I", Empty, Empty),
                                   Node ("pattern matching", Empty, Empty))));
val it = Node (4, Node (1, Empty, Empty), Node (16, Empty, Empty)) : int bintree

Write a function bintree_inorder : 'a bintree -> 'a list that takes a binary tree and returns a list of its values according to an inorder (left to right) traversal. Do not use list append operations. Use only :: to construct lists.
```
- bintree_inorder bt;
val it = [1,3,7,8,9,21] : int list
- bintree_inorder (Node (3, Node (4, Empty, Empty), Empty));
val it = [4,3] : int list
- bintree_inorder (Node (251, Empty, Empty));
val it = [251] : int list
- bintree_inorder Empty;
stdIn:4.1-4.14 Warning: type vars not generalized because of
    value restriction are instantiated to dummy types (X1,X2,...)
val it = [] : ?.X1 list
```
The strange type and accompanying warning in the last case show that the type checker cannot infer the concrete element type of the binary tree Empty, since there is no carried data. As a result the type of bintree_inorder Empty is not concrete either. It might seem that the empty tree or list should should have type 'a bintree or 'a list and be usable for any binary tree or list type, but there is an interesting reason this is not safe. We will study this reason (and the resulting value restriction) later. For now, we can avoid this with:
```
- bintree_inorder (Empty : int bintree);
val it = [] : int list
```

Write a function bintree_fold_inorder : ('a * 'b -> 'b) * 'b * 'a bintree -> 'b, where the result of fold_inorder (combine, init, tree) is equivalent to the result of applying foldl with the same combine and init to the result of bintree_inorder tree. Your bintree_fold_inorder implementation may not use foldl, bintree_inorder, or any equivalent function. You may not produce an intermediate list. You must fold following the structure of the tree alone.

- bintree_fold_inorder ((op+), 1, Empty);
val it = 1 : int
- bintree_fold_inorder ((op+), 1, bt);
val it = 50 : int
- bintree_fold_inorder (fn (elem, (prev, ordered)) => (elem, ordered andalso prev < elem), (0, true), bt);
val it = (21, true) : bool
- bintree_fold_inorder (fn (elem, acc) => acc ^ " " ^ (Int.toString elem), "Inorder:", bt);
val it = "Inorder: 1 3 7 8 9 21" : string
- bintree_fold_inorder (fn (elem, acc) => (elem + 1)::acc, [], bt);
val it = [22, 10, 9, 8, 4, 2] : int list

Write a function bintree_forall : ('a -> bool) * 'a bintree -> bool that returns true if the given 'a -> bool predicate function returns true on every value in the tree. Note that boolean AND is andalso and boolean OR is orelse in SML. The order of traversal is unspecified. You may not use the function bintree_inorder or any intermediate list.
```
- bintree_forall (fn x => x > 0, bt);
val it = true : bool
- bintree_forall (fn x => x > 0, Node (2, Node (~1, Empty, Empty), Empty));
val it = false : bool
- bintree_forall (fn x => x > 0, Empty);
val it = true : bool
```

2. Binary Search Trees (20 points)

Write code for this part in trees.sml.

In this part you will extend the use of binary trees as binary search trees, represented by the following ML type, based on our binary tree type from above.

(* Type for binary trees *)
datatype 'a bintree = Empty | Node of 'a * 'a bintree * 'a bintree

(* Type for binary search trees *)
type 'a bst = ('a * 'a -> order) * 'a bintree

Here, 'a bst is simply an alias for another type. A binary search tree is a pair of an ordering function and a binary tree. The ordering function is of type 'a * 'a -> order. It takes two elements of type 'a and returns a value of type order to indicate how the first element relates to the second element in the ordering. The built-in order type is defined as:

datatype order = LESS | EQUAL | GREATER

For example, using the bt binary tree defined above, we could define a binary search tree bst using standard integer ordering with the built-in Int.compare function.

val bst = (Int.compare, bt)

Note that SML may show the type of BST values or function arguments with ('a * 'a -> order) * 'a bintree appearing where you would expect 'a bst, since these mean the same thing. You may use the explicit typing : 'a bst if you wish. The same is true of concrete types that instantiate 'a, e.g., int bst.

Within the bst functions you write below, all comparisons of tree elements must be done using the ordering function, not with =, etc.

Use pattern matching of function arguments to your advantage. For example, here is a function of type 'a bst -> 'a list that returns and inorder list of BST elements:

fun bst_inorder (compare, tree) = bintree_inorder tree

This function takes advantage of the fact a value of type 'a bst is just a tuple of type ('a * 'a -> order) * 'a bintree. The function pattern matches this tuple to pull out the tree component to pass to bintree_inorder. Note, we could also give a wildcard pattern for the ordering function, since we do not need to use it:

fun bst_inorder (_, tree) = bintree_inorder tree

Write a function bst_valid : 'a bst -> bool that takes a binary search tree and returns true if it is a valid (well-ordered) binary search tree with no duplicates according to the ordering function, or false otherwise.

Hint: the simplest approach is to reuse one of the basic binary tree functions above.

- bst_valid bst;
val it = true : bool
- bst_valid (Int.compare, Empty);
val it = true : bool
- bst_valid (Int.compare, Node (3, Node (4, Empty, Empty), Empty));
val it = false : bool
- bst_valid (Int.compare, Node (3, Empty, Node (4, Node (1, Empty, Empty), Empty)));
val it = false : bool
- bst_valid (Int.compare, Node (3, Empty, Node (4, Node (3, Empty, Empty), Empty)));
val it = false : bool

Write a function bst_contains : 'a bst * 'a -> bool that takes a binary search tree and an element and returns true if that element is an element of the binary search tree (as determined by the ordering function yielding EQUAL) and false otherwise.

Assume (but do not check) that the argument BST is valid, by the specification of bst_valid.
```
- bst_contains (bst, 7);
val it = true : bool
- bst_contains (bst, 10);
val it = false : bool
- bst_contains ((Int.compare, Empty), 3);
val it = false : bool
```
Write a function bst_insert : 'a bst * 'a -> 'a bst that takes a binary search tree and an element and returns a new binary search tree with the new element inserted into the old tree according to the standard binary search tree rules.

Assume (but do not check) that the argument BST is valid, by the specification of bst_valid. If the given element is already present (i.e., the ordering function indicates it is EQUAL to an existing element), this function should produce a tree identical to the original. The result BST must also be valid. Do not allow duplicates.
```
- bst_insert ((Int.compare, Empty), 7);
val it = (fn, Node (7, Empty, Empty)) : int bst
- bst_insert (it, 1);
val it = (fn, Node (7, Node (1, Empty, Empty), Empty)) : int bst
- bst_insert (it, 9);
val it = (fn, Node (7, Node (1, Empty, Empty), Node (9, Empty, Empty))) : int bst
- bst_insert (it, 21);
val it = (fn, Node (7, Node (1, Empty, Empty), Node (9, Empty, Node (21, Empty, Empty)))) : int bst
```

Write a function bst_remove : 'a bst * 'a -> 'a bst that takes a binary search tree and an element and returns a new binary search tree with the element removed.

Assume (but do not check) that the argument BST is valid, by the specification of bst_valid. The result BST must also be valid.

- bst_remove ((Int.compare, Empty), 7);
val it = (fn, Empty) : int bst
- bst_remove (bst, 8);
val it = (fn, Node (7, Node (1, Empty, Node (3, Empty, Empty)), Node (9, Empty, Node (21, Empty, Empty)))) : int bst
- bst_remove (bst, 1);
val it = (fn, Node (7, Node (3, Empty, Empty), Node (9, Node (8, Empty, Empty), Node (21, Empty, Empty)))) : int bst
- bst_remove (bst, 7);
val it = (fn, Node (8, Node (1, Empty, Node (3, Empty, Empty)), Node (9, Empty, Node (21, Empty, Empty)))) : int bst
- bst_remove ((Int.compare, Node (3, Node (1, Empty, Empty), Node (9, Node (5, Empty, Node (7, Node (6, Empty, Empty), Empty)), Empty))), 3);
val it = (fn, Node (5, Node (1, Empty, Empty), Node (9, Node (7, Node (6, Empty, Empty), Empty), Empty))) : int bst

Optional extra fun: Implement a new data type and associated functions for contains, insert, and remove on red-black trees, AVL trees, or binary heaps. (For binary heaps, include a remove_min function.)

3. Random Art¹ (45 points)

Your job is to write an ML program to construct, evaluate, and plot randomly generated functions from a simple expression language, resulting in the generation of random art. This program will apply ideas in grammars, parse trees, and their representation as ML datatypes. You will implement a very simple interpreter for a small language of plottable functions as well as generators of programs in this language.

See a gallery of prior CS 251 student art.

The language of expressions can be described by a simple grammar:

$e ::= \texttt{x}\ \Big|\ \texttt{y}\ \Big|\ \sin (\pi e)\ \Big|\ \cos (\pi e)\ \Big|\ \frac{e + e}{2.0}\ \Big|\ e e$

Any expression generated by this grammar is implicitly a function over the two coordinate variables x and y. When x and y are given real values in the range $[-1.0,1.0]$, evaluation of expressions in this language yields a result in the same range.

We can characterize expressions in this grammar with the following ML datatype:

datatype expr = VarX
              | VarY
              | Sine     of expr
              | Cosine   of expr
              | Average  of expr * expr
              | Times    of expr * expr

Note how this definition mirrors the formal grammar given above; for instance, the constructor Sine represents the application of the sin function to an argument multiplied by π. Interpreting abstract syntax trees is much easier than trying to interpret terms directly.

Complete the following tasks in the file art.sml.

Printing Expressions: Write a function exprToString : expr -> string to generate a printable version of an expression. For example:
```
- exprToString (Times(Sine(VarX),Cosine(Times(VarX,VarY))))
val it - "sin(pi*x)*cos(pi*x*y)" : string
```
The exact formatting is left to you. String concatenation is performed with the ^ operator in SML. Test this function on a few sample inputs before moving to the next part.
Evaluating Expressions: Write the function eval : expr -> real*real -> real to evaluate the given expression at the given (x, y) location. Note that eval is in curried form. You may want to use the functions Math.cos and Math.sin, as well as the floating-point value Math.pi. (Note that an expression tree represented, e.g., as Sine(VarX) corresponds to the mathematical expression sin πx, and the eval function must be defined appropriately.

Test this function on several sample inputs before moving on to the next part. Here are a couple to start (try lots more):
```
- eval (Sine(Average(VarX,VarY))) (0.5,0.0);
val it = 0.707106781187 : real
- eval sampleExpr (0.1,0.1);
val it = 0.569335014033 : real
```
Driver Code: The art.sml file includes the doRandomGray and doRandomColor functions, which generate grayscale and color bitmaps respectively. These functions need to iterate over all the pixels in a (by default) 301 by 301 square, which naturally would be implemented by nested for loops. In art.sml, complete the definition of the function
```
for : int * int * (int -> unit) -> unit
```
The argument triple contains a lower bound, an upper bound, and a function; your code should apply the given function to all integers from the lower bound to the upper bound, inclusive. If the greater bound is strictly less than the lower bound, the call to for should do nothing. Implement this function using tail recursion.

The type unit describes a singleton value (), which is pronounced unit and is used wherever no value is needed. Wherever unit occurs, side effects are most likely involved. For example, the print function has type string -> unit. It prints a string as a side effect and returns (). The () value is necesary because ML has no “statements,” only expressions: every function must return some value.

The SML expression e1; e2 is the sequencing expression. Like (), this expression appears only where side effects are desired. Its evaluation rule is:
- Evaluate e1 to a value and discard it.
- Then evaluate e2 to a value and use its result as the result of the whole expression.
Test your code with a call like the following:
```
for (2, 5, (fn x => (print ((Int.toString(x)) ^ "\n"))));
```
It should print out the numbers 2,3,4, and 5.

Note: The type inferred for your for function may be more general than the type described above. How could you force it to have the specified type, and why might it be useful to do that? (You don’t need to submit an answer to this, but it is worth understanding.)

Test your implementation by producing a grayscale picture of the expression sampleExpr: call the emitGrayscale function from the REPL. Look at doRandomGray to see how this function is used. An uncaught exception OutOfRange while producing a picture indicates that your eval function is returning a number outside the range [-1,1].
Viewing Pictures:

You can view .pgm files, as well as the .ppm files described below, by converting the file to PNG format with the following command in the terminal (in the normal shell, not in the SML interpreter):
```
$ convert art.pgm art.png
```
The convert utility supports many image formats.
Generating Random Expressions and Art: Your next programming task is to complete the definition of a function that builds random expressions recursively:
```
build : int * randgen -> expr
```
The first argument to build is a maximum nesting depth for the resulting expression. A bound on the nesting depth keeps the expression to a manageable size. When you reach the cut-off point (i.e., depth is 0), you can simply return an expression with no sub-expressions, such as VarX or VarY. If not yet at the cut-off, randomly select one of the forms of expr and recursively create its subexpressions.

The second argument to build is a function of type randgen. As defined at the top of art.sml, the type randgen is simply a type abbreviation for a function that takes two integers and returns an integer:
```
type randgen = int * int -> int
```
Given a function rand of type randgen, call rand (l,h) to get a number in the range l to h, inclusive. Successive calls to that function will return a sequence of random values. Documentation in the code describes how to make a randgen function with makeRand. You may wish to use this function while testing your build function.

Once you have completed build, you can generate pictures by calling the function:
```
doRandomGray : int * int * int -> unit
```
Given three arguments – a maximum expression tree depth and two seeds for the random number generator – this function generates a random expression tree and evaluates it on the $(x,y)$ coordinates of each pixel in a grid to determine the grayscale value for that pixel, producing an image in the file art.pgm.

You may also run:
```
doRandomColor : int * int * int -> unit
```
Given the same arguments as doRandomGray, this function creates three random expression trees (one each for red, green, and blue), and evaluates them on the $(x,y)$ coordinates of each pixel in a grid to determine the color of that pixel, producing an image in the file art.ppm. (Note the different filename extension).

A few notes:
- A maximum expression tree depth of 8 to 12 is reasonable to start, but experiment to see what you think is best.
- If you find your art to be “boring,” consider this: If every sort of expression can occur with equal probability at any depth in the overal expression tree, it is relatively likely that the random expression you get will be either VarX or VarY, or something small like Times(VarX,VarY). Since small expressions tend to produce “boring” pictures, find some way to prevent or discourage expressions with no subexpressions from being chosen “too early.” There are many options for doing this. Experiment and pick one that gives you good results.
- The two seeds for the random number generators determine the eventual picture, but are otherwise completely arbitrary.
Augmenting the Expression Language: Extend the expr datatype with constructors for at least three more expression forms. Add corresponding cases to exprToString, eval, and build. The new expression forms are subject to these constraints:
- Evaluation of the new expression forms must yield a value in the range $[-1.0,1.0]$, assuming all their subexpressions evaluate to values in this same range.
- At least one of the new expression forms must be constructed out of 3 subexpressions, i.e., one of the new constructors for expr must carry at least expr * expr * expr.
- Each new expression forms must describe functions that cannot be emulated by composing other expression forms in the language.
There are no other constraints; the new functions need not even be continuous. Be creative!

Make sure to document your extensions with comments.
Gallery Selections: Submit your changes to the provided files and also git add a couple of your favorite random art pictures.

Submission

Don’t forget to git add some of your random art images!

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

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.

The Random Art assignment is lightly adapted from a version by Steve Freund, based on versions by M. Dresner and Chris Stone. ↩

Expressionist Art

Contents

Tasks

1. Binary Trees (35 points)

2. Binary Search Trees (20 points)

3. Random Art¹ (45 points)

Submission

Contents

Tasks

1. Binary Trees (35 points)

2. Binary Search Trees (20 points)

3. Random Art1 (45 points)

Submission

3. Random Art¹ (45 points)