22 Trees with Map and Fold

Map and fold also make sense with trees!

type 'a tree =
	| Leaf
	| Node of 'a * 'a tree * 'a tree
	
let t =
	Node (1,
		Node (2, Leaf, Leaf),
		Node (3, Leaf, Leaf))

type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree

val t : int tree = Node (1, Node (2, Leaf, Leaf), Node (3, Leaf, Leaf))

What if we wanted to map over a tree?

let rec map f = function
	| Leaf -> Leaf
	| Node (v, l, r) -> Node (f v, map f l, map f r)

val map : ('a -> 'b) -> 'a tree -> 'b tree = <fun>

t;;

- : int tree = Node (1, Node (2, Leaf, Leaf), Node (3, Leaf, Leaf))

map string_of_int t;;

- : string tree = Node ("1", Node ("2", Leaf, Leaf), Node ("3", Leaf, Leaf))

map succ t;;

- : int tree = Node (2, Node (3, Leaf, Leaf), Node (4, Leaf, Leaf))

What about folds?

let rec fold acc f = function
	| Leaf -> acc
	| Node (v, l, r) -> f v (fold acc f l) (fold acc f r)

val fold : 'a -> ('b -> 'a -> 'a -> 'a) -> 'b tree -> 'a = <fun>

let sum = fold 0 (fun x y z -> x + y + z)

val sum : int tree -> int = <fun>

sum t;;

- : int = 6

t |> map succ |> sum

- : int = 9