Problem 8: OCAML ONLY!!We have seen the benefits of the 'fold' function for list data structures. In a similar fashion, write a functionfold_inorder:('a->'b->'a)->'a->'btree->'aThat does an inorder fold of the tree. The function should traverse the left subtree, visit the root, and then traverse the right subtree. For example,fold_inorder (fun acc x -> acc @ [x]) [] (Node (Node (Leaf,1,Leaf), 2, Node (Leaf,3,Leaf))) = [1;2;3]In [ ]:letrecfold_inorderfacct=(* YOUR CODE HERE *)In [ ]:assert (fold_inorder (fun acc x -> acc @ [x]) [] (Node (Node (Leaf,1,Leaf), 2, Node (Leaf,3,Leaf))) = [1;2;3]); assert (fold_inorder (fun acc x -> acc + x) 0 (Node (Node (Leaf,1,Leaf), 2, Node (Leaf,3,Leaf))) = 6). Other source code is provided within image... only use OCAML Datatypes:Problems 8-9 are about manipulating tree data structures.In OCaml, you can define a tree data structure using datatype:type 'a tree = Leaf | Node of 'a tree * 'a * 'a treeWe will assume binary search trees in this assignment and can define a bineary search tree insertion function as the following:let rec insert tree x =match tree with| Leaf -> Node (Leaf, x, Leaf)| Node (1, y, r) ->if x = y then treeelse if x < y then Node (insert 1 x, y, r)else Node (1, y, insert r x)We can construct a binary search tree from a list:let construct 1 =List.fold_left (fun acc x -> insert acc x) Leaf 1Problem 8We have seen the benefits of the 'fold' function for list data structures. In a similar fashion, write a functionfold_inorder ('a -> 'b -> 'a) -> 'a -> 'b tree -> 'aThat does an inorder fold of the tree. The function should traverse the left subtree, visit the root, and then traverse the right subtree. For example,fold_inorder (fun acc x -> acc @ [x]) [] (Node (Node (Leaf,1,Leaf), 2, Node (Leaf,3,Leaf))) = [1;2;3]In [ ]: let rec fold_inorder f acc t =(* YOUR CODE HERE *)=In [ ]: assert (fold_inorder (fun acc x -> acc @[x]) [] (Node (Node (Leaf, 1, Leaf), 2, Node (Leaf, 3, Leaf)))assert (fold_inorder (fun acc x -> acc + x) (Node (Node (Leaf,1,Leaf), 2, Node (Leaf,3,Leaf))) = 6)[1;2;3]);

The fold_inorder function is a recursive function that takes three arguments:f: A function that…

Answered: Problem 8: OCAML ONLY!! We have seen…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Problem 8: OCAML ONLY!!

We have seen the benefits of the 'fold' function for list data structures. In a similar fashion, write a function

fold_inorder:('a->'b->'a)->'a->'btree->'a

That does an inorder fold of the tree. The function should traverse the left subtree, visit the root, and then traverse the right subtree. For example,

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

In [ ]:

letrecfold_inorderfacct=(* YOUR CODE HERE *)

In [ ]:

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

Other source code is provided within image... only use OCAML

Datatypes:
Problems 8-9 are about manipulating tree data structures.
In OCaml, you can define a tree data structure using datatype:
type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree
We will assume binary search trees in this assignment and can define a bineary search tree insertion function as the following:
let rec insert tree x =
match tree with
| Leaf -> Node (Leaf, x, Leaf)
| Node (1, y, r) ->
if x = y then tree
else if x < y then Node (insert 1 x, y, r)
else Node (1, y, insert r x)
We can construct a binary search tree from a list:
let construct 1 =
List.fold_left (fun acc x -> insert acc x) Leaf 1
Problem 8
We have seen the benefits of the 'fold' function for list data structures. In a similar fashion, write a function
fold_inorder ('a -> 'b -> 'a) -> 'a -> 'b tree -> 'a
That does an inorder fold of the tree. The function should traverse the left subtree, visit the root, and then traverse the right subtree. For example,
fold_inorder (fun acc x -> acc @ [x]) [] (Node (Node (Leaf,1,Leaf), 2, Node (Leaf,3,Leaf))) = [1;2;3]
In [ ]: let rec fold_inorder f acc t =
(* YOUR CODE HERE *)
=
In [ ]: assert (fold_inorder (fun acc x -> acc @[x]) [] (Node (Node (Leaf, 1, Leaf), 2, Node (Leaf, 3, Leaf)))
assert (fold_inorder (fun acc x -> acc + x) (Node (Node (Leaf,1,Leaf), 2, Node (Leaf,3,Leaf))) = 6)
[1;2;3]);

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 4 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions