-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathfold_tree.ml
More file actions
68 lines (54 loc) · 1.78 KB
/
fold_tree.ml
File metadata and controls
68 lines (54 loc) · 1.78 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
(* api
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>
val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>
val all : bool list -> bool = <fun>
val any : bool list -> bool = <fun>
val map : ('a -> 'b) -> 'a list -> 'b list = <fun>
val copy : 'a list -> 'a list = <fun>
val append : 'a list -> 'a list -> 'a list = <fun>
val split : ('a * 'b) list -> 'a list * 'b list = <fun>
val concat : 'a list list -> 'a list = <fun>
type 'a tree = Lf | Br of 'a * 'a tree * 'a tree
val fold_tree : ('a -> 'b -> 'b -> 'b) -> 'b -> 'a tree -> 'b = <fun>
val tree_size : 'a tree -> int = <fun>
val tree_sum : int tree -> int = <fun>
val tree_preorder : 'a tree -> 'a list = <fun>
val tree_inorder : 'a tree -> 'a list = <fun>
val tree_postorder : 'a tree -> 'a list = <fun>
*)
let rec fold_left f a l =
match l with
[] -> a
| h::t -> fold_left f (f a h) t
let rec fold_right f l a =
match l with
[] -> a
| h::t -> f h (fold_right f t a)
let all l = fold_left ( && ) true l
let any l = fold_left ( || ) false l
let map f l =
fold_right (fun e a -> f e :: a) l []
let copy l =
fold_right (fun e a -> e :: a) l []
let append x y =
fold_right (fun e a -> e :: a) x y
let split l =
fold_right
(fun (x, y) (xs, ys) -> (x :: xs, y :: ys))
l
([], [])
let concat l = fold_left ( @ ) [] l
type 'a tree =
Lf
| Br of 'a * 'a tree * 'a tree
let rec fold_tree f e t =
match t with
Lf -> e
| Br (x, l, r) -> f x (fold_tree f e l) (fold_tree f e r)
let tree_size t =
fold_tree (fun _ l r -> 1 + 1 + r) 0 t
let tree_sum t =
fold_tree (fun x l r -> x + 1 + r) 0 t
let tree_preorder t = fold_tree (fun x l r -> [x] @ l @ r) [] t
let tree_inorder t = fold_tree (fun x l r -> l @ [x] @ r) [] t
let tree_postorder t = fold_tree (fun x l r -> l @ r @ [x]) [] t