new_stuff
[lambda.git] / assignment8.mdwn
1 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.
2
3                 type 'a tree = Leaf of 'a | Node of ('a tree * 'a tree)
4
5                 type 'a starred_tree = Root | Starring_Left of 'a starred_pair | Starring_Right of 'a starred_pair
6                 and 'a starred_pair = { parent : 'a starred_tree; sibling: 'a tree }
7                 and 'a zipper = { tree : 'a starred_tree; filler: 'a tree };;
8
9                 let rec move_botleft (z : 'a zipper) : 'a zipper =
10                         (* returns z if the targetted node in z has no children *)
11                         (* else returns move_botleft (zipper which results from moving down and left in z) *)
12                         YOU SUPPLY THE DEFINITION
13
14
15                 let rec move_right_or_up (z : 'a zipper) : 'a zipper option =
16                         (* if it's possible to move right in z, returns Some (the result of doing so) *)
17                         (* else if it's not possible to move any further up in z, returns None *)
18                         (* else returns move_right_or_up (result of moving up in z) *)
19                         YOU SUPPLY THE DEFINITION
20
21
22                 let new_zipper (t : 'a tree) : 'a zipper =
23                         {tree = Root; filler = t}
24                         ;;
25
26                 let make_fringe_enumerator (t: 'a tree) =
27                         (* create a zipper targetting the root of t *)
28                         let zstart = new_zipper t
29                         in let zbotleft = move_botleft zstart
30                         (* create a refcell initially pointing to zbotleft *)
31                         in let zcell = ref (Some zbotleft)
32                         (* construct the next_leaf function *)
33                         in let next_leaf () : 'a option =
34                                 match !zcell with
35                                 | None -> (* we've finished enumerating the fringe *)
36                                         None
37                                 | Some z -> (
38                                         (* extract label of currently-targetted leaf *)
39                                         let Leaf current = z.filler
40                                         (* update zcell to point to next leaf, if there is one *)
41                                         in let () = zcell := match move_right_or_up z with
42                                                 | None -> None
43                                                 | Some z' -> Some (move_botleft z')
44                                         (* return saved label *)
45                                         in Some current
46                                 )
47                         (* return the next_leaf function *)
48                         in next_leaf
49                         ;;
50
51                 let same_fringe (t1 : 'a tree) (t2 : 'a tree) : bool =
52                         let next1 = make_fringe_enumerator t1
53                         in let next2 = make_fringe_enumerator t2
54                         in let rec loop () : bool =
55                                 match next1 (), next2 () with
56                                 | Some a, Some b when a = b -> loop ()
57                                 | None, None -> true
58                                 | _ -> false
59                         in loop ()
60                         ;;
61