This problem set has three parts. You should
write your solution to each part in a separate file:
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 listthat 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; 3; 10]]
union_lists : 'a list -> 'a list -> 'a listthat 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 listthat 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]]
reckeyword 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
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
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).
convenience, we have provided a function
translates a string in infix form (such as
sin(~x)) into a value of type
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
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 -> 'asuch that
fold_expr atom unary binary exprperforms a postorder traversal of
expr. During the traversal, it applies
atom : expr -> 'ato every leaf node (i.e.
Num). It applies
unary : uop -> 'a -> 'ato every unary expression. The first argument to
unaryis the unary operator and the second is the result of applying
fold_exprrecursively to that expression's operand. Finally,
binary : bop -> 'a -> 'a -> 'ato every binary expression. The arguments to
binaryare the binary operator and the results of recursively applying
fold_exprto the left and right operands.
fold_exprto 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 -> floatsuch that
eval x eevaluates
Varequal 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 -> exprthat 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
unnecessarily complicated expressions.