1. Complete the definitions of `move_botleft` and `move_right_or_up` from the same-fringe solution in the [[week11]] notes. Test your attempts against some example trees to see if the resulting `make_fringe_enumerator` and `same_fringe` functions work as expected. type 'a tree = Leaf of 'a | Node of ('a tree * 'a tree) type 'a starred_tree = Root | Starring_Left of 'a starred_pair | Starring_Right of 'a starred_pair and 'a starred_pair = { parent : 'a starred_tree; sibling: 'a tree } and 'a zipper = { tree : 'a starred_tree; filler: 'a tree };; let rec move_botleft (z : 'a zipper) : 'a zipper = (* returns z if the targetted node in z has no children *) (* else returns move_botleft (zipper which results from moving down and left in z) *) YOU SUPPLY THE DEFINITION let rec move_right_or_up (z : 'a zipper) : 'a zipper option = (* if it's possible to move right in z, returns Some (the result of doing so) *) (* else if it's not possible to move any further up in z, returns None *) (* else returns move_right_or_up (result of moving up in z) *) YOU SUPPLY THE DEFINITION let new_zipper (t : 'a tree) : 'a zipper = {tree = Root; filler = t} ;; let make_fringe_enumerator (t: 'a tree) = (* create a zipper targetting the root of t *) let zstart = new_zipper t in let zbotleft = move_botleft zstart (* create a refcell initially pointing to zbotleft *) in let zcell = ref (Some zbotleft) (* construct the next_leaf function *) in let next_leaf () : 'a option = match !zcell with | None -> (* we've finished enumerating the fringe *) None | Some z -> ( (* extract label of currently-targetted leaf *) let Leaf current = z.filler (* update zcell to point to next leaf, if there is one *) in let () = zcell := match move_right_or_up z with | None -> None | Some z' -> Some (move_botleft z') (* return saved label *) in Some current ) (* return the next_leaf function *) in next_leaf ;; let same_fringe (t1 : 'a tree) (t2 : 'a tree) : bool = let next1 = make_fringe_enumerator t1 in let next2 = make_fringe_enumerator t2 in let rec loop () : bool = match next1 (), next2 () with | Some a, Some b when a = b -> loop () | None, None -> true | _ -> false in loop () ;;