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
:
sumlist
to sum up elements of an integer listremove5
to remove all 5s from an integer listmin
to find a minimum of a list integers (you must
use traverse
). It should
return a very large number for an empty listreverse
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.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));;
Draw a picture of the two given trees.
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 Nodeseed
is returned from an empty tree
Use the traversetree
function to define the following
functions:
addtree
to add all elements in a tree of integersconcattree
to concatenate all strings in a tree of
strings. The operation ^
performs string
concatenation.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.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.
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;;
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;
}
}