Csci 4651 Problem set 5

Due Friday March 9th at midnight

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:

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;
    }

}


CSci 4651 course web site