Part A

Write a function in Ocaml

type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree fold_inorder : ('a -> 'b -> 'a) -> 'a -> 'b tree -> 'a 

That does a inorder fold of the tree. For example,

fold_inorder (fun acc x -> acc @ [x]) [] (Node (Node (Leaf,1,Leaf), 2, Node (Leaf,3,Leaf))) = [1;2;3]

In [ ]:

type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree let rec fold_inorder f acc t = (* YOUR CODE HERE *) raise (Failure "Not implemented") 

In [ ]:

assert (fold_inorder (fun acc x -> acc @ [x]) [] (Node (Node (Leaf,1,Leaf), 2, Node (Leaf,3,Leaf))) = [1;2;3])

part B

use Ocaml to write the function.

The usual recursive formulation of fibonacci function

let rec fib n = if n = 0 then 0 else if n = 1 then 1 else fib (n-1) + fib (n-2) 

has exponential running time. It will take a long time to compute fib 50. You might have to interrupt the kernel if you did try to do fib 50 in the notebook.

But we know that fibonacci number can be computed in linear time by remembering just the current cur and the previous prev fibonacci number. In this case, the next fibonacci number is computed as the sum of the current and the previous numbers. Then the program continues by setting prev to be cur and cur to be cur + prev.

Implement a tail recursive function fib_tailrec that uses this idea and computes the nth fibonacci number in linear time.

fib_tailrec : int -> int 

In [ ]:

let fib_tailrec n = (* YOUR CODE HERE *) raise (Failure "Not implemented") 

In [ ]:

assert (fib_tailrec 50 = 12586269025)