Trees in Functional Programming

Notes:

1. Why Trees?

When data has a natural hierarchy, a tree is usually the simplest faithful model. File systems arrange folders within folders; graphical user interfaces nest components within containers; and arithmetic expressions combine sub‑expressions to form larger ones. Functional programming encourages us to represent these hierarchies directly. We do this with algebraic data types, which let us say, in a single sentence, what a structure can be.

Thinking in trees is a shift in perspective. Rather than imagining a sequence of instructions, we describe a shape: a value is either a simple leaf or it is built by combining smaller trees. That description is already a recipe for computation, because functions can follow the same shape when they operate on the data. This is why trees feel so natural in FP: the data definition and the program structure line up.

Hierarchical data fits tress naturally (files, GUIs, expressions).
ADTs + pattern matching align data and program structure.
Think in shapes: leaves and nodes guide computation.

2. Tree Shapes and Their Meanings

A binary tree captures the idea of “two subparts or a single value.” In a language like Haskell, we might say: a tree of a’s is either a leaf holding an a, or a node holding two subtrees. Nothing in this shape commits us to a particular meaning—one application might interpret the left subtree as “smaller” and the right as “larger,” producing a binary search tree; another might treat the two subtrees as the left and right halves of an expression. The same shape can carry many semantics.

Some hierarchies are not naturally binary. A rose tree (also called an n‑ary tree) allows each node to have a list of children. Abstract syntax trees for programming languages, outlines for documents, and menu systems all fit this model well. The key idea is that the type captures the branching pattern, while the meaning comes from how we use it.

Binary tree: two subparts or a single value.
Size, height, and leaf list follow the same pattern
Structural induction proves correctness naturally

3. Structural Recursion and Induction

Once we describe a tree’s shape, the most reliable way to compute with it is to mirror that shape in our functions. This is structural recursion: write one case for leaves, one case for nodes, and combine the results from the subtrees in the node case. Computing the size of a tree, its height, or the list of leaf values all follow this pattern. Because each step strictly reduces the structure, the recursion terminates exactly when we reach the leaves.

This same correspondence makes reasoning about correctness straightforward. Structural induction proves properties about trees by showing they hold for the leaf case and are preserved when two smaller proofs are combined at a node. The program structure and the proof structure are two sides of the same coin.

4. Traversals: Reading a Tree in Different Orders

Traversals are simply conventions for the order in which we visit nodes. Preorder touches a node before its subtrees; inorder visits the left subtree, then the node, then the right; postorder waits until both subtrees have been visited before the node itself. Each order highlights something different. For binary expression trees, inorder looks like infix notation we are familiar with from algebra; prefix and postfix correspond to the notations used by certain compilers and stack‑based calculators.

Choosing a traversal is not just cosmetic. If we want to serialize a tree, a preorder walk preserves the idea of “a node introduces its structure.” If we plan to evaluate an expression using a stack, a postorder walk delivers the operands before the operators. The order embodies an intention.

5. Mapping and Folding: Reusing the Same Pattern

Two general tools capture most tree computations. A map over trees applies a function to every stored value while leaving the shape unchanged. This is useful when we want to transform labels—turning integers into strings, or annotating each value with extra information—without touching the structure.

A fold over trees (sometimes called a catamorphism) takes the next step: it reduces a tree to a single result by specifying what to do at a leaf and how to combine the results from the two subtrees at a node. With one well‑chosen fold, many seemingly different functions become instances. If a leaf contributes one and a node adds the two answers, we get the size. If a leaf contributes one and a node adds one to the maximum of its two answers, we get the height. If a leaf contributes a singleton list and a node concatenates its two lists, we get all the leaf values in order. And if leaves hold numbers and nodes hold operators, the fold is simply “evaluate the operator on the two sub‑results,” giving us expression evaluation.

The practical payoff is large: instead of writing many bespoke recursive functions, we write one fold and describe particular behaviours by plugging in small building blocks.

mapTree transforms labels, preserving shape.
- Just like mapping onto a list
foldTree reduces a tree by leaf/node recipes
- Many functions become fold instances (size, height, leaves, eval).

6. The Haskell View: Instances and Laziness

Haskell formalizes these ideas with type class instances. A custom Tree type can be made an instance of Functor, which provides the standard map operation under the name fmap. The Functor laws—identity and composition—state, in effect, that mapping preserves structure and behaves like normal function composition. A Foldable instance expresses that a tree can be reduced to a summary using general combinators such as sum or toList.

Laziness complements this design. Because Haskell computes values only when they are needed, a traversal or a fold will touch exactly the parts of a tree that contribute to the result being demanded. If we take only the first few elements of a list produced by traversing a large tree, the unreachable parts are never evaluated. This demand‑driven behaviour lets us reason about very large or even conceptually infinite structures in a disciplined way.

Functor gives fmap (mapTree) with identity/composition laws.
Foldable expresses generic reductions (sum, toList).
Laziness traversals touch only demanded parts.
- Only what is needed when the traversal touches it

7. Applications and Design Considerations

Trees are not just a textbook exercise. Expression trees model arithmetic and logical formulas; a single fold both evaluates them and pretty‑prints them in a chosen notation.

Decision trees represent a branching sequence of questions; evaluating such a tree walks a path determined by input features. Tries—or prefix trees—organize strings by their shared prefixes, making certain lookups and aggregations fast and structurally transparent.

The shape of the tree matters. A balanced tree offers predictable performance and shallow recursion; a skewed tree can degenerate into a linear chain. In functional programming, we treat shape as an explicit design choice, which encourages careful constructors, balancing strategies, or alternative representations when performance requires it.

Expression trees, decision trees, tries are natural fits
Shape affects performanceL balanced vs skewed.
Treat shape as an explicit design choice in FP.

8. Connections to Earlier Material

From Week 5, polymorphism and type classes show up again: tree functions are naturally generic in the element type, and instances like Functor and Foldable let us reuse a rich library of abstractions. From Week 6, laziness explains why we can traverse just enough of a large structure to answer the question at hand—no more, no less. Trees, in this sense, are the natural continuation of thinking about structure and evaluation together.

Week 5: polymorphism, type classes -> generic tree code.
- With polymorphism you can create the same tree based on anything
Week 6: laziness demand-driven traversals

9. Closing Perspective

Trees give us a language for hierarchy that aligns beautifully with the functional style. By defining data with algebraic types and writing functions that follow the same shape, we get programs that are clear, correct by construction, and easy to reason about. Mapping and folding are not tricks; they are the distilled form of many algorithms. With purity and laziness in the background, Haskell turns these ideas into everyday practice.

Trees align with FP: clear shapes, clear programs.
Map and fold are the distilled forms of many algorithms.
Purity and laziness make tree work predictable

10. Readings (Learn You a Haskell)

To deepen today’s discussion, consult these chapters from Learn You a Haskell for Great Good!:

Chapter 2 (“Starting Out”) for list foundations like ranges and take/drop;
Chapter 5 (“Recursion”) for the shape-driven style we apply to trees;
Chapter 6 (“Higher-Order Functions”) for reusable patterns that generalize to tree traversals and folds;
Chapter 8 (“Making Our Own Types and Typeclasses”) for algebraic data types and pattern matching (define your own Tree);
Chapter 10 (“Functionally Solving Problems”) for fold-centric design;• Chapter 11 (“Functors, Applicative Functors and Monoids”) to connect mapTree with fmap and the Functor laws; and
Chapter 14 (“Zippers”) as an optional look at navigating and updating trees structurally.