Carefully read the entire document before you start coding. This assignment is entirely about functional programming in OCaml.
Note: All functions, unless otherwise specified, should be polymorphic (i.e., they should work with any data type). For example, if you are writing a method that should work for lists, the type must be ‘a list, and not int list.
1 Recursion
In this section, you may not use any functions available in the OCaml library that already solves all or most of the question. For example, OCaml provides a List.rev function, but you may not use that in this section.
1. Write a recursive function float_pow, which takes two integer parameters x and n, and returns xn, but for x being a float.
returns true if and only if the functions f and g have identical behavior on every element of lst.
# let f i = i * i;;
val f : int -> int =
val g : int -> int =
– : bool = true
# equiv f g [1;2;3];;
– : bool = false
2. Write a functions called pairwisefilter with two parameters: (i) a function cmp that compares two elements of a specific T and returns one of them, and (ii) a list lst of elements of that same type T. It returns a list that applies cmp while taking two items at a time from lst. If lst has odd size, the last element is returned “as is”.
# pairwisefilter min [14; 11; 20; 25; 10; 11];; – : int list = [11; 20; 10]
# (* assuming that shorter : string * string -> string =
# pairwisefilter shorter [“and”; “this”; “makes”; “shorter”; “strings”; “always”; “win”];; – : string list = [“and”; “makes”; “always”; “win”]
3. Write the polynomial function, which takes a list of tuples and returns the polynomial function corre- sponding to that list. Each tuple in the input list consists of (i) the coefficient, and (ii) the exponent.
# let f = polynomial [3, 3;; -2, 1; 5, 0];;
val f : int -> int =
# f 2;; (* f is the polynomial function f(x) = 3x^3 – 2x + 5 *) – : int = 25
3 Data Types
1. Let us define a language for expressions in Boolean logic: type bool_expr =
| Lit of string
| Not of bool_expr
| And of bool_expr * bool_expr | Or of bool_expr * bool_expr
Using this language, we can write logical expressions in prefix notation. For example, (a ∧ b) ∨ ( ¬ a) can be written as Or(And(Var(“a”), Var(“b”)), Not(Var(“a”))).
Write a function called truth_table, which takes as input a logical expression in two literals, and returns its truth table as a list of triples. Each triple being a tuple of the form:
Higher-order Functions
2
1. Write a function called equiv_on, which takes three inputs: two functions f and g, and a list lst. It
(truth-value-of-first-literal, truth-value-of-second-literal, truth-value-of-expression).
For example,
# (* the outermost parentheses are needed for OCaml to parse the third argument
correctly as a bool_expr *)
# truth_table “a” “b” (And(Lit(“a”), Lit(“b”)));;
– : (bool * bool * bool) list = [(true, true, true); (true, false, false);
(false, true, false); (false, false, false)]
2. Recall that a binary tree can be defined recursively as follows:
A binary tree is either empty or it is composed of a root element and two successors, which are binary trees themselves.
Just like the type bool_expr was defined in the previous question, define a polymorphic type binary_tree using the above definition. Each element of the tree must be a Node, or be Empty. For example, a complete binary tree with three levels, and incremental integer values in the nodes, would be defined as
Figure 1: This binary tree should have the string representation “0(1(3,4),2(,5(6,)))”.
let a_tree = Node(1, Node(2, Node(4, Empty, Empty), Node(5, Empty, Empty)), Node(3, Node(6, Empty, Empty), Node(7, Empty, Empty)));;
3. Write a function called tree2str to obtain the string representation of a binary tree as shown in Fig. 1.