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_given =
let rec climb t =
match t with
| Leaf v ->
...
| Node (t1, t2) ->
let ih2 = climb t2
and ih1 = climb t1
in ...
in climb t_given;;
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 binary_tree_fold leaf_case node_case t_given =
(* binary_tree_fold : ('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_given;;
Sometimes one prefers to uncurry node_case to precisely reflect the structure of the binary trees:
let binary_tree_fold_uncurried leaf_case node_case t_given =
(* binary_tree_fold_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_given;;
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))
binary_tree_fold_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 binary_tree_fold, 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_v t_given =
let rec visit t =
match t with
| Leaf v ->
"Leaf " ^ (show_v v)
| Node (t1, t2) ->
let ih2 = visit t2
and ih1 = visit t1
in "Node (" ^ ih1 ^ ", " ^ ih2 ^ ")"
in visit t_given;;
By instantiating leaf_case to be (fun v -> "Leaf " ^ (show_v v)) and node_case to be (fun ih1 ih2 -> "Node (" ^ ih1 ^ ", " ^ ih2 ^ ")"), we make binary_tree_fold emulate the computation of the unparsing function for binary trees:
let show_binary_tree_alt show_v t_given =
binary_tree_fold
(fun v -> "Leaf " ^ (show_v v))
(fun ih1 ih2 -> "Node (" ^ ih1 ^ ", " ^ ih2 ^ ")")
t_given;;
And since the name t_given has no raison d’être anymore, we can rename it to t:
let show_binary_tree_alt show_v t =
binary_tree_fold
(fun v -> "Leaf " ^ (show_v v))
(fun ih1 ih2 -> "Node (" ^ ih1 ^ ", " ^ ih2 ^ ")")
t;;
Here is how we had defined a function to count the number of leaves in a binary tree:
let number_of_leaves t_given =
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_given;;
By instantiating leaf_case to be (fun _ -> 1) and node_case to be (fun ih1 ih2 -> ih1 + ih2), we make binary_tree_fold emulate the counting of leaves in any given binary tree:
let number_of_leaves_alt t_given =
binary_tree_fold
(fun _ -> 1)
(fun ih1 ih2 -> ih1 + ih2)
t_given;;
And since the name t_given has no raison d’être anymore, we can rename it to t:
let number_of_leaves_alt t =
binary_tree_fold
(fun _ -> 1)
(fun ih1 ih2 -> ih1 + ih2)
t;;
Here is how we had defined a function to count the number of nodes in a binary tree:
let number_of_nodes t_given =
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_given;;
By instantiating leaf_case to be (fun _ -> 0) and node_case to be (fun ih1 ih2 -> succ (ih1 + ih2)), we make binary_tree_fold emulate the counting of nodes in any given binary tree:
let number_of_nodes_alt t_given =
binary_tree_fold
(fun _ -> 0)
(fun ih1 ih2 -> succ (ih1 + ih2))
t_given;;
And since the name t_given has no raison d’être anymore, we can rename it to t:
let number_of_nodes_alt t =
binary_tree_fold
(fun _ -> 0)
(fun ih1 ih2 -> succ (ih1 + ih2))
t;;
As a continuation of Exercise 02, implement a function that computes the least integer contained in a given binary tree of integers, using binary_tree_fold.
As a continuation of Exercise 03, implement a function that computes the largest integer contained in a given binary tree of integers, using binary_tree_fold.
As a continuation of Exercise 04, implement a function that computes the weight of a given binary tree of positive integers (i.e., the sum of the integers in its leaves), using binary_tree_fold.
Here is how we had defined a function computing the height of any given binary tree of integers:
let height t_given =
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_given;;
Implement height in terms of binary_tree_fold.
The height function was specified inductively, following the structure of binary trees:
base case:
given any integer n, the height of Leaf n is 0
induction step:
given any tree t1 of height h1 (which is the left induction hypothesis) and given any tree t2 of height h2 (which is the right induction hypothesis), the height of Node (t1, t2) is the maximum of h1 and h2, plus 1
So by instantiating leaf_case to be (fun _ -> 0) and node_case to be (fun ih1 ih2 -> succ (max ih1 ih2)), we make binary_tree_fold emulate the computation of the height of any given binary tree:
let height_alt t_given =
binary_tree_fold
(fun _ -> 0)
(fun ih1 ih2 -> succ (max ih1 ih2))
t_given;;
And since the name t_given has no raison d’être anymore, we can rename it to t:
let height_alt t =
binary_tree_fold
(fun _ -> 0)
(fun ih1 ih2 -> succ (max ih1 ih2))
t;;
Here is how we had defined a function computing the mirror of any given binary tree:
let mirror t_given =
let rec visit t =
match t with
| Leaf n ->
Leaf n
| Node (t1, t2) ->
let ih2 = visit t2
and ih1 = visit t1
in Node (ih2, ih1)
in visit t_given;;
Implement mirror in terms of binary_tree_fold.
As a continuation of Exercise 09, implement a function that tests whether a given binary tree of integers represents a well-balanced mobile, using binary_tree_fold.
Implement map_binary_tree (described in the section about The map function over polymorphic binary trees) using binary_tree_fold (which is the topic of the present chapter).
As a followup to Exercise 10, implement the corresponding fold function for polymorphic binary trees where the payload is in the nodes, and express the corresponding mirror function using this fold function.
As a followup to Exercise 11, implement the corresponding fold function for polymorphic binary trees where the payload is in the leaves and in the nodes, and using this fold function, express the corresponding function that tests whether such a given binary tree of integers represents a well-balanced mobile.
Created [15 Oct 2022]