## Csci 4651 Problem set 5

### Problem 1: ML version of traverse (25 points)

The function `traverse` defined below is analogous to the Scheme `traverse` function.

``````

let rec traverse combine action seed = function
| [] -> seed
| x :: xs -> combine (action x) (traverse combine action seed (xs));;
``````

`do` is a reserved word in ML so the corresponding parameter is called `action`.

Below are two examples of using `traverse` to define functions on ML lists. Note that, unlike in Scheme, in ML * is an operator, not a function, so you cannot pass it as an argument to `traverse`. Instead we define a simple function `mult` and pass it as a parameter. The same needs to be done for +, -, and ::.

``````
let comb x y = x :: y;;
let mult x = x * x;;
let mapsquare = traverse comb mult [];;
mapsquare [1; 5; 7; -2];;

let comb x y = x + y;;
let act x = 1;;
let count x = (traverse comb act 0) x;;
``````

Note a different syntax used to define `count` (x is used in the definition). This syntax makes a function that can be applied to a list of any type.

Your task is to define the following functions by passing appropriate parameters to `traverse`:

1. `sumlist` to sum up elements of an integer list
2. `remove5` to remove all 5s from an integer list
3. `min` to find a minimum of a list integers (you must use `traverse`). It should return a very large number for an empty list
4. `reverse` to reverse any list (try it on a list of strings and a list of integers). You may use `append` function in the lab for this problem.

### Writing and using a traverse function for a tree type

You are given the following definition of a tree type and two sample trees:

``````
(* tree type and two sample trees *)

type 'a tree = Empty | Node of 'a * 'a tree * 'a tree;;

let intTree = Node (5, Node (3, Empty, Empty),
Node (6, Node (7, Empty, Empty), Empty));;

let strTree = Node ("apples", Empty, Node ("bananas",
Node ("oranges", Empty, Node ("grapes", Empty, Empty)), Empty));;
``````

#### Question 1

Draw a picture of the two given trees.

#### Question 2

Write a function `traversetree` which takes three parameters, `combine, action,` and `seed`, and returns a function to perform an operation on a tree, the same way as `traverse` returns a function that works on lists. Here are more details:

• `combine` takes 3 parameters: the result of `action` on a Node and the result of two recursive calls: to the left and to the right subtrees.
• `action` is applied to the value of a Node
• `seed` is returned from an empty tree

Use the `traversetree` function to define the following functions:

1. `addtree` to add all elements in a tree of integers
2. `concattree` to concatenate all strings in a tree of strings. The operation `^` performs string concatenation.
3. `flattentree` to return a list of all elements in a tree. For instance, for the first tree above it should return `[5; 3; 6; 7]` The order of elements in the list does not matter. Important: the function should work on trees of any type. See `count` example above for the correct syntax.
4. Extra credit: `find` that takes a tree and an element and returns true if the element is in the tree and false otherwise. Hint: `action` should perform the check.
Note: this is a difficult problem, do not spend too much time on it.

#### Problem 2 (12 points): type inference.

Apply the type inference algorithm to the examples below. Show all your work. Write down the resulting type for the function `f` in each case (or demonstrate a type mismatch if the function does not have a valid type). Feel free to use the OCaml interpreter to check your types.

``````
(* Question 1 *)
let f x y = if x < 2 then x :: [] else x :: [y];;

(* Question 2 *)
let f x = fst x :: snd x ;;

(* Question 3 *)
let f x = match x with
(y, []) -> y
|(z, w) -> z + w;;

(* Question 4 *)
let rec f x = match x with
[] -> []
|y :: ys -> (not (y < 2)) :: f ys;;
``````

#### Problem 3 (5 points).

In the following Java program please point out all L-values (expressions that are used to denote a memory location) and R-values (expressions used to denote a value in memory).
``````
import java.awt.Point;

public class LRValues {

public static void main(String [] args) {
int x = 0;
x++;
boolean y = (x == 0);
if (y) {
y = !y;
}
int [] A = {1, 2, 3};
for (int i = 0; i < 2; ++i) {
A[i] = A[i+1];
}
Point thePoint = new Point();
thePoint.x = thePoint.x + 1;
}

}
``````

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.