The goal of this lecture note is to explore the pattern of structural recursion for binary trees where the payloads are stored in the leaves:
type 'a binary_tree =
| Leaf of 'a
| Node of 'a binary_tree * 'a binary_tree;;
Any structurally recursive function over binary trees follows the inductive structure of binary trees – base case and induction step:
let ... t_init =
let rec climb t =
match t with
| Leaf v ->
...
| Node (t1, t2) ->
let ih2 = climb t2
and ih1 = climb t1
in ...
in climb t_init;;
Let us functionally abstract what to do in the base case and what to do in the induction step. The result is what is called the fold function for binary trees:
let fold_binary_tree leaf_case node_case t_init =
(* fold_binary_tree : ('a -> 'b) -> ('b -> 'b -> 'b) -> 'a binary_tree -> 'b *)
let rec climb t =
match t with
| Leaf v ->
leaf_case v
| Node (t1, t2) ->
let ih2 = climb t2
and ih1 = climb t1
in node_case ih1 ih2
in climb t_init;;
Sometimes one prefers to uncurry node_case to precisely reflect the structure of the binary trees:
let fold_binary_tree_uncurried leaf_case node_case t_init =
(* fold_binary_tree_uncurried : ('a -> 'b) -> ('b * 'b -> 'b) -> 'a binary_tree -> 'b *)
let rec climb t =
match t with
| Leaf v ->
leaf_case v
| Node (t1, t2) ->
let ih2 = climb t2
and ih1 = climb t1
in node_case (ih1, ih2)
in climb t_init;;
Given a leaf case leaf_specific, a node case node_specific, and a binary tree:
Node (Node (Leaf v1,
Node (Leaf v2,
Leaf v3)),
Node (Leaf v4,
Leaf v5))
fold_binary_tree_uncurried precisely yields the result of evaluating:
node_specific (node_specific (leaf_specific v1,
node_specific (leaf_specific v2,
leaf_specific v3)),
node_specific (leaf_specific v4,
leaf_specific v5))
In words, the result of fold_binary tree_uncurried is a series of nested applications of node_specific that precisely reflects the nested occurrences of the original constructor Node in the given binary tree.
In practice, OCaml encourages curried functions, and so we use fold_binary_tree, which, in this example, yields the result of evaluating:
node_specific (node_specific (leaf_specific v1)
(node_specific (leaf_specific v2)
(leaf_specific v3)))
(node_specific (leaf_specific v4)
(leaf_specific v5))
Here is how we had defined the unparsing function for polymorphic binary trees:
let show_binary_tree show_yourself t_init =
let rec visit t =
match t with
| Leaf v ->
"Leaf " ^ (show_yourself v)
| Node (t1, t2) ->
let ih2 = visit t2
and ih1 = visit t1
in "Node (" ^ ih1 ^ ", " ^ ih2 ^ ")"
in visit t_init;;
By instantiating leaf_case to be (fun v -> "Leaf " ^ (show_yourself v)) and node_case to be (fun (ih1, ih2) -> "Node (" ^ ih1 ^ ", " ^ ih2 ^ ")"), we make fold_binary_tree emulate the computation of the unparsing function for binary trees:
let show_binary_tree_alt show_yourself t_init =
fold_binary_tree (fun v -> "Leaf " ^ (show_yourself v))
(fun ih1 ih2 -> "Node (" ^ ih1 ^ ", " ^ ih2 ^ ")")
t_init;;
Here is how we had defined a function to count the number of leaves in a binary tree:
let number_of_leaves t_init =
let rec count t =
match t with
| Leaf _ ->
1
| Node (t1, t2) ->
let ih2 = count t2
and ih1 = count t1
in ih1 + ih2
in count t_init;;
By instantiating leaf_case to be (fun _ -> 1) and node_case to be (fun (ih1, ih2) -> ih1 + ih2), we make fold_binary_tree emulate the counting of leaves in any given binary tree:
let number_of_leaves_alt t_init =
fold_binary_tree (fun _ -> 1)
(fun ih1 ih2 -> ih1 + ih2)
t_init;;
Here is how we had defined a function to count the number of nodes in a binary tree:
let number_of_nodes t_init =
let rec count t =
match t with
| Leaf _ ->
0
| Node (t1, t2) ->
let ih2 = count t2
and ih1 = count t1
in succ (ih1 + ih2)
in count t_init;;
By instantiating leaf_case to be (fun _ -> 0) and node_case to be (fun (ih1, ih2) -> succ (ih1 + ih2)), we make fold_binary_tree emulate the counting of nodes in any given binary tree:
let number_of_nodes_alt t_init =
fold_binary_tree (fun _ -> 0)
(fun ih1 ih2 -> succ (ih1 + ih2))
t_init;;
Here is how we had defined a function computing the height of any given binary tree of integers:
let height t_init =
let rec measure t =
match t with
| Leaf n ->
0
| Node (t1, t2) ->
let ih2 = measure t2
and ih1 = measure t1
in succ (max ih1 ih2)
in measure t_init;;
Instantiate leaf_case and node_case to emulate the height measuring for any given binary tree.
Here is how we had defined a function computing the mirror of any given binary tree:
let mirror t_init =
let rec mirror_mirror t =
match t with
| Leaf n ->
Leaf n
| Node (t1, t2) ->
let ih2 = mirror_mirror t2
and ih1 = mirror_mirror t1
in Node (ih2, ih1)
in mirror_mirror t_init;;
Instantiate leaf_case and node_case to emulate the mirroring for any given binary tree.
As a continuation of Exercise 29, implement a function that tests whether a given binary tree of integers represents a well-balanced mobile, using fold_binary_tree.
Implement map_binary_tree using fold_binary_tree.
As a followup to Exercise 30, implement the corresponding fold-right function for polymorphic binary trees where the payload is in the nodes, and express the corresponding mirror function using this fold-right function.
As a followup to Exercise 31, implement the corresponding fold-right function for polymorphic binary trees where the payload is in the leaves and in the nodes, and using this fold-right function, express the corresponding function that tests whether such a given binary tree of integers represents a well-balanced mobile.
Curried the node parameter in the definition of fold_binary_tree [08 Apr 2020]
Regrouped [24 Mar 2020]
Fixed a typo, thanks to Yunjeong Lee’s eagle eye [11 Jun 2019]
Added the interlude [31 Mar 2019]
Fixed a typo in the statement of Exercise 32, thanks to Upaasna Parankusam’s eagle eye [30 Mar 2019]
Completed with exercises [30 Mar 2019]
Created [28 Mar 2019]