This problem set has three parts. You should
write your solution to each part in a separate file: warmup.ml
, diff.ml
,
and expression.ml
. To help get you started,
we have provided a stub file for each part on CMS. You should download and
edit these files. Once you have finished, submit your solution using CMS,
linked from the course website.
Note: Unless otherwise mentioned, you may not use the rec
keyword in this problem set. You may find the standard List module functions, namely fold_left, particularly useful. You should consider making your solution tail-recursive, as points will be taken off if your function stack-overflows with large input. Points will also be deducted for abuse of the @ operator. Side effects are not allowed.
prepend_all : 'a list list -> 'a -> 'a list list
that takes in a list of lists of any
type and an element of that type and returns all of the lists with that
element added to the front of the list. For example:
prepend_all [[2; 4; 5]; []; [3; 10]] 1 = [1; 2; 4; 5]; [1]; [1; 3; 10]]
union_lists : 'a list -> 'a list -> 'a list
that takes in two lists of the same type
and returns a list which contains the union of the elements of the two
lists (i.e. there should be no duplicates in the list returned)
You may assume that the argument lists are already valid sets.lcs : 'a list -> 'a list -> 'a list list
that takes two lists and computes
the longest common subsequence (LCS) of the elements in the two lists. This
function should return a list of lists, and which contains all possible
LCS in case of a tie. Note that a subsequence is not the same as a substring. If a sequence has some of its elements removed without the order of the remaining ones changed, then the resulting sequence is a subsequence of the original sequence. For example, [A; C] is a subsequence of [A; B; C; D]. The LCS of two lists is then the longest subsequence that is in both lists.
The general algorithm for doing computing the LCS is described below.
Consider two nonempty lists, lst1 and lst2. Let
fin1 be the last element in lst1 and
start1 be the rest of lst1, and fin2
and start2 be the same for lst2.
Say that we want to find the LCS of lst1 and lst2. If
fin1 = fin2, then this element must be in subsequence,
and the rest of the subsequence can be found by recursing on start1
and start2. If fin1 <> fin2, then they
cannot both be in the LCS. Therefore,
we take the best out of three cases:
lcs [A; G; C; A; T] [G; A; C] = [[A; C]; [G; C]; [G; A]]
rec
keyword for this problem. programming programming language using ocaml programming is language awesome! ocaml is awesome!and get this output:
"+ using" "+ programming"This is a bit bothersome, as it is clear that the first two lines in the new file are the ones that were added, not the second and third. We are not concerned about this, but there are some diff-erent algorithms that do a better job of handling it. If you are interested in learning more you can find an example here. Exceptional diff implementations may receive karma.
The objective of this part is to build a language that can
differentiate and evaluate symbolically represented mathematical
expressions that are functions of a single variable x
. Symbolic
expressions consist of numbers, variables, and standard functions
(plus, minus, times, divide, sin, cos, etc). To get
you started, we have provided the datatype that defines the
abstract syntax for such expressions.
(* abstract syntax tree *) (* Binary Operators *) type bop = Add | Sub | Mul | Div | Pow (* Unary Operators *) type uop = Sin | Cos | Ln | Neg type expr = Num of float | Var | BinOp of bop * expr * expr | UnOp of uop * expr
This datatype provides an internal representation of an expression
that the user might type in. The constructor
Var
represents the single variable x
, and
UnOp (Ln, Var)
represents the natural logarithm of x.
Neg
refers to unary negation and is denoted by the symbol ~.
(the symbol - is only used for subtraction). The meaning of the others
should be clear.
Mathematical expressions can be constructed using the
constructors in the above datatype definition. For example, the expression
x^2 + sin(~x)
would be
represented internally as:
BinOp (Add, BinOp (Pow, Var, Num 2.0), UnOp (Sin, UnOp (Neg, Var)))
This represents a tree in which nodes are the type constructors and the children of each node are an operator and the arguments of that operator. Such a tree is called an abstract syntax tree (or AST for short).
For your
convenience, we have provided a function parse_expr
which
translates a string in infix form (such as x^2 +
sin(~x)
) into a value of type expr
.
The parse_expr
function
parses according to the standard precedence of operations, so
5 + x * 8
will be read as
5 + (x * 8)
. We have also provided two functions
to_string
and to_string_smart
that print expressions in a readable form
using infix notation. The former produces a fully-parenthesized
expression so you can see how the parser parsed the expression,
whereas the latter omits unnecessary parentheses.
# let e = parse_expr "x^2 + sin(~x)";; val e : Expression.expr = BinOp (Add, BinOp (Pow, Var, Num 2.), UnOp (Sin, UnOp (Neg, Var))) # to_string e;; - : string = "((x^2.)+(sin((~(x)))))" # to_string_smart e;; - : string = "x^2.+sin(~(x))"
For full credit, only use rec
in your implementation of fold_expr.
Do not use rec
in evaluate and derivative.
fold_expr : (expr -> 'a) -> (uop -> 'a
-> 'a) -> (bop -> 'a -> 'a -> 'a) -> expr -> 'a
such that
fold_expr atom unary binary expr
performs a postorder traversal of
expr
. During the traversal, it applies atom :
expr -> 'a
to every leaf node (i.e. Var
or
Num
). It applies unary : uop -> 'a -> 'a
to every unary expression. The first argument to unary
is the unary operator and the second is the result of applying
fold_expr
recursively to that expression's operand. Finally,
fold_expr
applies binary : bop -> 'a -> 'a ->
'a
to every binary expression. The arguments to
binary
are the binary operator and the results of
recursively applying fold_expr
to the left and right operands.
fold_expr
to
determine whether the given expression contains a variable.
let contains_var : expr -> bool = let atom = function | Var -> true | _ -> false in let unary op x = x in let binary op l r = l || r in fold_expr atom unary binary
fold_expr
, write a function eval : float
-> expr -> float
such that eval x e
evaluates
e
, setting Var
equal to the value
x
. For full credit, do not use rec in evaluate.
eval 2.0 (BinOp (Add, Num 2.0, Var)) = 4.0
.fold_expr
, write a function derivative :
expr -> expr
that returns the derivative of an expression with
respect to Var
. The expression it returns need not be
simplified. For full credit, do not use rec in derivative.
derivative (BinOp (Pow, Var, Num 2.0))
= BinOp (Mul, Num 2., BinOp (Mul, Num 1., BinOp (Pow, Var, BinOp (Sub,
Num 2., Num 1.))))
When implementing this function, recall the chain rule from your freshman calculus course:
This rule tells how to form the derivative of the composition of two functions if we know the derivatives of the two functions. With the help of this rule, we can write the derivatives for all the operators in our language:
There are two cases provided for calculating the derivative of f(x) ^ g(x)
,
one for where g(x) = h
does not contain any variables, and
one for the general case.
The first is a special case of the second, but it is useful to treat
them separately, because when the first case applies, the second case
produces
unnecessarily complicated expressions.