<figure><img src="image_1.png" /></figure>

HAL
open science

# How to Fold a Tree: Programming Exercises on Calder's Mobiles

Thibaut Balabonski

► To cite this version:

Thibaut Balabonski. How to Fold a Tree: Programming Exercises on Calder's Mobiles. OLIVIER-FEST'25, Oct 2025, Singapour, Singapore. 10.1145/3759427.3760370. hal-05248010

HAL Id: hal-05248010

https://hal.science/hal-05248010v1

Submitted on 10 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# How to Fold a Tree

Programming Exercises on Calder's Mobiles

Thibaut Balabonski

thibaut.balabonski@universite-paris-saclay.fr

Université Paris-Saclay, CNRS, ENS Paris-Saclay, LMF

France

## Abstract

We explore several ways of folding over a binary tree, and illustrate their use to solve programming exercises on Calder's mobiles, focusing on algorithms that perform a single tree traversal. Dedicated to Olivier Danvy on the occasion of his 64th birthday.

**CCS Concepts: Theory of computation → Design and analysis of algorithms; Functional constructs; Social and professional topics → Computing education.**

**Keywords:** Calder's mobiles, trees, folds, applicative iteration

## ACM Reference Format:

Thibaut Balabonski. 2025. How to Fold a Tree: Programming Exercises on Calder's Mobiles. In *Proceedings of the Workshop Dedicated to Olivier Danvy on the Occasion of His 64th Birthday (OLIVIERFEST '25)*, October 12–18, 2025, Singapore, Singapore. ACM, New York, NY, USA, 12 pages. https://doi.org/10.1145/3759427.3760370

## 1 Introduction

Applicative iteration on a data structure, known as “fold”, is a key programming pattern in functional languages. Many data structures libraries come with folding primitives, which provide a controlled way of traversing the structure and computing something along the traversal. Those patterns are also of theoretical importance for various reasons, for instance in that they implement terminating recursions, and are thus related to **for** or **foreach** loops, or to primitive recursion.

However, even for the simplest of the structures, folding can be done in more than one way. For instance, folding over a list `[x₁; x₂; ...; xN]` using a function `f` and an initial element `a` can be done either from left to right

$$f ((f (f a x_1) x_2) \dots) x_N$$

or from right to left

$$f x_1 (f x_2 (\dots (f x_N a)))$$

<figure><img src="image_3.png" /></figure>

This work is licensed under a Creative Commons Attribution 4.0 International License.

OLIVIERFEST '25, Singapore, Singapore

© 2025 Copyright held by the owner/author(s).

ACM ISBN 979-8-4007-2150-2/25/10

https://doi.org/10.1145/3759427.3760370

More complex structures such as trees imply a greater variety of folding patterns. In this paper, we explore a collection of such folding patterns on binary trees, and their relations to each other.

### 1.1 Mobiles

A mobile is formed by a collection of objects that hang under bars which themselves hang in an equilibrium under other bars, the whole structure hanging under a unique suspension point.

<figure><img src="image_4.png" /></figure>

These aerial structures have made american sculptor Alexander Calder famous. They are also an interesting structure here since they have the surprisingly rare property of being a physical real-world object that closely corresponds to the abstract notion of a binary tree<fnref n="1" />. Mobiles are thus a very interesting pedagogical device, for a first exposure of students to the notion of inductive structures and structural induction [1, Chapter 6]. They are also a large supply of programming exercises on trees, which seems to have been less exploited in the literature than what we could expect. Indeed, this example has mostly been used by Olivier Danvy [2, 3], who himself attributes it to Patrick Greussay [8].

In this paper we will consider several tasks on mobiles, and use them as examples to motivate various ways of traversing a tree, some of them similar to the accumulations on trees studied by Jeremy Gibbons [6]. Throughout the paper, we use the words tree, node and leaf interchangeably with mobile, bar and object.

<footnote n="1">¹The main difference between mobiles and binary trees is that the bars of a mobile are supposed to be able to rotate horizontally around their suspension point, blurring the distinction between a left and a right son. We thus obtain an actual binary tree only when looking at a stabilized picture of a mobile.</footnote>
We propose the following inductive definition of mobiles as an algebraic datatype, here written in OCaml [11].

``` OCaml
type mobile =
  | Obj of int (* weight *)
  | Bar of int (* radius *) * mobile * mobile
```

where an object `Obj(w)` is parameterized by its weight `w`, and a bar `Bar(r, m1, m2)` is parameterized by the distance `r` between the center and an extremity. For the sake of keeping simple the statement of the tasks, we assume that:

* each bar hangs by its middle, and thus has a “radius” `r` which is the half of its total length, and is balanced if and only if the left and right submobiles have the same weight,

* bars, and other ropes or hanging material does not weigh anything, and thus only leaf objects matter when computing the weight of a mobile,

* objects have a radius given by the square root of their weight, and ropes at each level have a uniform length, in such manner that all objects or bars at the same logical level actually hang at the same altitude when the mobile is balanced, and never overlap with an element of another level.

## 1.2 Dear Reader...

... before reading on, take some time and try to solve each of the following tasks in a single traversal of a mobile, and compare the various flows of information.

* Check whether a mobile is balanced. This means: under each bar, the left and right submobiles have exactly the same weight.

* Take a mobile that might not be balanced, and return a mobile of the same shape, whose object weights have been adjusted to ensure perfect balance.

* Compute the list of the coordinates of all the leaf objects, from (logical) left to right.

* Check that the lengths of the bars allow drawing the mobile without any two elements (objects, bars or ropes) to overlap.

* Take a mobile that might not be drawing without overlaps, and return a mobile of the same shape, whose bar lengths have been adjusted to ensure drawability. Bonus: minimize bar lengths.

In some way, the “in a single traversal” restriction corresponds to “using a unique call to an appropriate folding function”. Bonus: are you able to solve all of these using a unique, expressive enough folding pattern?

## 1.3 Outline

After reviewing the traditional folds on linked lists and some of their uses in Section 2, we focus successively on four different folding patterns for binary trees. Section 3 presents a bottom-up, map-reduce style pattern (structural fold), with

applications to the computation of aggregate values on trees. Section 4 introduces an opposite, downward pattern, with applications to rendering structural information of trees. Section 5 proposes left-to-right scanning patterns that provide different ways of computing aggregate values. Section 6 finally defines a richer folding pattern, which is expressive enough to simulate all the previous patterns as well as to implement some algorithms that seem to be out of reach of the others. Section 7 hints at some additional patterns that traverse a tree level by level. Please also take note that, while the folds defined in this paper are all purely functional, they are sometimes applied to functions that produce side-effects or raise exceptions. Outside of this, the paper uses mostly elementary programming constructs, shared by most functional languages.

## 2 Folds on Lists

We review briefly the two standard ways of folding lists, and some non-straightforward uses of these folds. An in-depth analysis of these folds can also be found in a recent paper by Olivier Danvy [4].

**Left fold.** The left fold iterates on the elements of a list, from left to right. It corresponds to the most immediate form of a **for** loop, and can be implemented by a simple tail-recursive function using an accumulator for the value to be computed.

``` OCaml
let left_fold
  (f: 'a -> 'b -> 'b) (init: 'b) (l: 'a list)
  : 'b =
let rec fold l acc = match l with
  | []      -> acc
  | x::tl   -> acc |> f x |> fold tl
  in
fold l init
```

Some reader may remark that the order of the arguments differs from the usual `fold_left` from OCaml's standard library. This inessential variation makes the function consistent with the other folds presented in the paper. The implementation also illustrates the coding style of the paper, where:

* we use a local recursive function `fold` to avoid repeating the higher-order parameters at each call,

* we use the reverse application operator `|>`, also known as “pipeline”, when several successive function calls are chained, to make the sequence and its information flow explicit. Here for instance,

``` OCaml
acc |> f x |> fold tl
```

is equivalent to

``` OCaml
fold tl (f x acc)
```

Although this is not required by OCaml, we always provide explicit type annotations for our folding functions, on a documentation purpose.
An instructive use-case of the left fold is a constant-stack space implementation of the function rev that reverses a list.

```h
let rev l = leftFold (fun x acc -> x :: acc) [] l
```

**Right fold.** The right fold follows the inductive structure of the list: it first computes an intermediate result on the tail of the list, and then combines it with the head element. Its most natural implementation is not tail-recursive.

```h
let rightFold
    (f: 'a -> 'b -> 'b) (init: 'b) (l: 'a list)
  : 'b =
let rec fold = function
  | []      -> init
  | x::tl   -> f x (fold tl)
in
fold l
```

Compared to the left fold, it is interesting to observe that this version naturally preserves the order of the elements. For instance, it can be used to implement a map function.

```h
let map f l =
    rightFold (fun x acc -> f x :: acc) [] l
```

**There and Back Again.** Solve with only one fold a task that seemingly requires two. With this technique introduced by Olivier Danvy and Mayer Goldberg [3, 5], an accumulator initialized at the last recursive call introduces a second data structure, which is traversed iteratively at return time. We reproduce here an example computing the symbolic convolution $[(x_1, y_N); (x_2, y_{N-1}); ...; (x_N, y_1)]$ of two lists $l_1 = [x_1; x_2; ...; x_N]$ and $l_2 = [y_1; y_2; ...; y_N]$ of same length. In this example, the fold is performed on $l_1$, and the structure traversed at return time is $l_2$.

```h
let convolution l1 l2 = rightFold
    (fun x (acc, l') -> ((x, hd l') :: acc, tl l'))
    ([], l2) l1
|> fst
```

**Parsing.** The accumulator used in a left fold may be used to thread a lot of information along the computation. As an example, consider the following problem: take as input a list `l` of integers, and try to build a mobile whose object weights are precisely the integers of `l`, in the same order (we do not care about bar lengths for now). This is a parsing problem, that can be solved with a stack. The solution below is based on a left fold, whose accumulator contains a stack of already built submobiles and their weights. This fold calls on each new element a function `merge`, which puts the element on top of the stack and merges it with further elements down the stack while they have an appropriate weight. The construction of a mobile succeeds if the whole list is consumed, and the stack is reduced to a unique mobile.

```h
exception Unbalanced
let rec merge m1 w1 stack =
    match stack with
    | [] -> [m1, w1]
    | (m2, w2) :: tl ->
        if w1 < w2 then
            (m1, w1) :: stack
        else if w1 = w2 then
            merge (Bar(1, m2, m1)) (w1+w2) tl
        else raise Unbalanced

let calderize weights =
    match leftFold
        (fun w stack -> merge (Obj(w)) w stack)
        [] weights
    with
        | [m, _] -> Some m
        | _ -> None
        | exception Unbalanced -> None
```

Once this technique is known, it is fairly easy to add width information for each submobile and deduce meaningful bar lengths. More on geometry in Section 3.

The temporal complexity of calderize is linear in the size of the list weights, despite repeated calls to the auxiliary recursive function merge, since each recursive call to merge consumes the top element of stack and creates a bar, and the total number of bars of a full mobile is equal to the number of leaf objects minus one. A similar effect could be achieved with a right fold, using the same auxiliary merge function.

## 3 Structural Fold

Let us now consider possible folding patterns on trees. We start with a pattern that is similar in essence to the right fold on lists, in that it follows the inductive structure of mobiles: at any given node Bar(r, m1, m2) it computes intermediate results for the submobiles m1 and m2 and combine them using the folding function bar. A specific function obj provide initial values at leaves.

```h
let structuralFold
    (bar: int -> 'a -> 'a -> 'a) (obj: int -> 'a)
    (m: mobile)
  : 'a =
let rec fold = function
  | Obj(w)      -> obj w
  | Bar(r, m1, m2) -> bar r (fold m1) (fold m2)
in
fold m
```

This structural fold, similarly to rightFold on lists, is not tail-recursive when written in direct style<fnref n="2" />.

<footnote n="2">²Of course, we could easily devise a variant where the fold is written in continuation-passing style, to use heap space instead of stack space.</footnote>
**Basic examples.** This fold is appropriate for computations where information flows from the leaves to the root, and in particular to compute aggregate values following a map/reduce style. Simple examples are various examples of computations of the dimensions of a mobile.

```h
let size = structuralFold
    (fun _ x y -> x+y) (fun _ -> 1)
let weight = structuralFold
    (fun _ x y -> x+y) (fun x -> x)
let height = structuralFold
    (fun _ h1 h2 -> 1 + max h1 h2) (fun _ -> 0)
```

There are some tasks however for which this fold is a poor choice. For instance, computing the list of the weights of the leaves with a structural fold requires concatenating the sublists `l1` and `l2` obtained for the respective submobiles `m1` and `m2`, which is needlessly costly.

```h
let fringe_poor = structuralFold
    (fun _ l1 l2 -> l1 @ l2)
    (fun k -> [k])
```

**Checking balance.** Checking the balance of a mobile is based on an upward flow of information: at each node we have to check local balance by comparing the weights of the two submobiles. As such it should be a good fit for our structural fold.

Let us start with the following straightforward algorithm, which is a poor solution since it abusively recomputes the weight of subtrees after checking their balance.

```h
let rec balanced_poor = function
  | Obj(w) -> true
  | Bar(r, m1, m2) ->
      balanced_poor m1
      && balanced_poor m2
      && weight m1 = weight m2
```

Interestingly, this poor algorithm cannot be written that easily using the structural fold. Indeed, computing `weight m1` and `weight m2` requires access to the subtrees `m1` and `m2`. However, a “vanilla” structural fold only gives access to the aggregates values computed on `m1` and `m2`. If one insists on implementing this version using a structural fold, it becomes necessary to include `m1` and `m2` in the scope of the folding function.

```h
let balanced_poor m = structuralFold
    (fun r (m1, b1) (m2, b2) ->
       (Bar(r, m1, m2),
        b1 && b2 && weight m1 = weight m2))
    (fun w -> (Obj(w), true))
    m
    |> snd
```

This need of building a copy of the mobile during the fold is a clear indication that our poor algorithm contains more than a simple traversal of the mobile. Moreover, this version

does not benefit enough from the laziness of the conjunction operator `&&`, since the value of the second Boolean parameter `b2` is computed (which means, the right submobile is explored) even when the left submobile is not balanced.

A better version consists in simply computing the weight of the mobile (bottom-up, using the structural fold), checking local balance on the fly, and interrupting the computation whenever an imbalance is detected.

```h
let balanced m =
    try let _ = structuralFold
        (fun _ w1 w2 ->
           if w1 <> w2 then raise Unbalanced;
           w1+w2)
        (fun w -> w)
    m
    in true
    with Unbalanced -> false
```

**Enforcing balance.** If the total weight `w` of a mobile is known, there is a unique way of assigning weights to the leaf objects in such manner that the mobile is balanced, and this assignment can be easily computed: if the mobile is a bar with two submobiles `m1` and `m2`, then each of `m1` and `m2` should have weight `w/2`. This process contains a downward flow of information, since the expected weight of each submobile is deduced from the expected weight of the whole. As such it does not seem to fit in this section that focuses on upward computation.

However, if we want to use the previous algorithm to assign balanced weights to the leaf objects of a given mobile, we first have to determine the total expected weight `w`. The smallest possible weight for a mobile of a given shape is a power of 2 related to the height of the mobile, which is most naturally computed by a structural fold.

Thus we need to perform an upward computation of height/total expected weight, followed by a downward propagation of the weights, which allows the final (upward) construction of the balanced mobile. To solve this using a unique structural fold we compute for each submobile both a local minimal weight `w`, and a continuation `k` which, given the definitive expected weight, will build a corresponding balanced submobile. Thus the case for a bar combines the two continuations that are intended to build the two submobiles, to produce a new continuation for the whole. After this upward computation, the continuation `k` is simply called on the global expected weight to actually build the result.

```h
let normalize m =
    let k, w = structuralFold
        (fun _ (k1, w1) (k2, w2) ->
           (fun w -> Bar(w/2, k1 (w/2), k2 (w/2))),
           2*(max w1 w2))
        (fun _ -> (fun w -> Obj(w)), 1)
    m
    in k w
```
Notice that the above code sets not only the weights of the objects, but also the lengths of the bars in a way that guarantees that no elements of the mobile will overlap. It does so by assigning a uniform length to every bar at a given level, corresponding to the largest possible mobile of the given weight, as pictured here:

<figure><img src="image_5.png" /></figure>

**Enforcing planar geometry.** The structural fold also supports more subtle approaches to setting the bar lengths of a mobile in such a way that its elements do not overlap. We derive here in two steps an algorithm that is reminiscent of the tree drawing algorithms by Andrew Kennedy [10] and Jeremy Gibbons [7].

As a first step, we reserve for each submobile the smallest rectangular region that contains it, and glue these regions together as in the picture below.

<figure><img src="image_6.png" /></figure>

This can be implemented efficiently (in linear time) using a structural fold, which computes a triple (1, m, r) where m is a mobile with appropriate bar lengths, and l (resp. r) is the horizontal distance between the farthest extremity of the leftmost (resp. rightmost) element of the mobile and the hanging point. We assume an (integer) sqrt function used here to take into account the radius of leaf objects. Take note that the left and right distances need not be equal. Also, the same principles can be used to write a geometrically sound version of the function calderize of Section 2.

```h
let set_geometry m =
  let (-, m', _ ) = structuralFold
    (fun _ (l1, m1, r1) (l2, m2, r2) ->
     let r = (r1 + l2 + 1)/2 in
      (max (l1+r) (l2-r),
       Bar(r, m1, m2),
       max (r2+r) (r1-r)))
    (fun w -> (sqrt w, Obj(w), sqrt w))
    m
  in
  m'
```

We now improve the above algorithm to allow interweaving the submobiles following their exact shape.

<figure><img src="image_7.png" /></figure>

We still compute a triple, but now the leftmost and rightmost distances are replaced by left and right profiles, which are lists of left (resp. right) distances at each level. At any level, the left distance is positive when there is an element to the left of the hanging point, and negative when the leftmost element at that level is actually to the right of the hanging point. Similarly, the right distance is positive at levels where there is an element to the right of the hanging point.

<figure><img src="image_8.png" /></figure>

The smallest possible length of a bar Bar(_, m1, m2) is determined by comparing the right profile of the left submobile m1 and the left profile of the right submobile m2, which is done using an auxiliary function max_sum. A second auxiliary function max_p is used to merge the profiles of two submobiles.

```h
let rec max_sum l1 l2 = match l1, l2 with
  | [], l | l, [] -> 0
  | x1::tl1, x2::tl2 -> max (x1+x2) @@ max_sum tl1 tl2
let rec max_p l1 l2 = match l1, l2 with
  | [], l | l, [] -> l
  | x1::tl1, x2::tl2 -> max x1 x2 :: max_p tl1 tl2
let set_geometry m =
  let (-, m', _ ) = structuralFold
    (fun _ (pl1, m1, pr1) (pl2, m2, pr2) ->
     let r = (max_sum pr1 pl2 + 1)/2 in
      (r :: max_p (map ((+)r) pl1) (map ((-)r) pl2),
       Bar(r, m1, m2),
       r :: max_p (map ((-)r) pr1) (map ((+)r) pr2)))
    (fun w -> ([sqrt w], Obj(w), [sqrt w]))
    m
  in m'
```

Observe that this improved algorithm is not of linear complexity anymore, due to the repeated calls to the auxiliary recursive functions max_sum and max_p. Remark also that the minimization of bar lengths is local and greedy, and does not necessarily produce a mobile of minimal width. Indeed, Supowit and Reingold showed that width minimization of the drawing of a binary tree is more difficult than that [14].
## 4 Downward Fold

Since the structural fold above gives a tree counterpart of the usual right fold on lists, let us now turn to the question of what could be a tree equivalent of a left fold.

Recall that a left fold starts with an initial value, then goes down the recursive structure of the list and computes a new intermediate value with each element of the list. The accumulator then contains the intermediate value computed from the head of the list to the current point, and the final result is the value obtained after reaching the last element of the list. Transposing this to a tree, we can start from the root with the initial value, then propagate an independent computation down each branch. Then the accumulator contains the intermediate value computed along the path from the root to the current point. Ultimately, this would produce one result per leaf in the tree, which raises questions about what to return. In this section, we choose to conclude each branch with a unit computation, which means our downward fold is intended for computations that produce side effects.

In the code below, the fold is parameterized by two functions `left` and `right`, used to update the accumulator in the respective subtrees. The final computation at the leaf objects is given by the third parameter function `obj`.

```hcl
let downwardFold
    (left: int -> 'a -> 'a) (right: int -> 'a -> 'a)
    (obj: int -> 'a -> unit) (init: 'a) (m: mobile)
: unit =
let rec fold m acc = match m with
| Obj(w) -> obj w acc
| Bar(r, m1, m2) ->
  fold m1 (left r acc); fold m2 (right r acc)
in
fold m init
```

**Printing descriptions of mobiles.** We show here several printing functions for mobiles based on a downward fold, where information about the current position relative to the root is threaded along the computation using the accumulator of the fold. For printing the depth of each leaf object, it is enough to count the number of bars encountered on the way down (we make no difference between left and right).

```hcl
let print depths m = downward fold
 fun _ -> (+) 1
 fun _ -> (+) 1
 fun _ -> print int) 0 m
```

For printing the coordinates of each element, assuming the root suspension point has coordinates `(0, 0)`, we enrich the previous function by taking into account horizontal displacement. The `left` and `right` functions are now distinguished for two reasons. Obviously the horizontal displacement has not the same direction on both sides. Moreover we also print information about each bar, but only once.

```hcl
let print pos m = downward fold
 fun r (x, y) ->
    printf "Bar%d_at_%d(%d, %d)\n" r x y; (x-r, y+1))
 fun r (x, y) -> (x+r, y+1))
 (fun w (x, y) -> printf "Obj%d_at_%d(%d, %d)\n" w x y)
 (0, 0) m
```

The following final example of downward fold used for printing renders the full logical structure of the mobile in ASCII on the standard output, one element per line with an indent proportional to its depth, and with bars pictured vertically. It does not respect the lengths of the bars. On the example of the first page, this could produce the following output.

```
+--02
+--B1
|  +--02
+--B3
|  |  +--01
|  |  +--B1
|  |  |  +--01
|  +--B2
|  +--02
+--B4
|  +--04
+--B2
|  +--01
|  +--B1
|  |  +--01
+--B2
+--02
```

The accumulator is a pair made of a side flag, and a prefix string that gives the appropriate indent and the bar segments that are “above” the element (above in the actual mobile, and thus to the left in this mirrored rendering). The side indication is used to decide when to draw a bar: the general rule is that any element is below a bar when it is in the left part of a right submobile, or in the right part of a left submobile. This flag is initialized at the special value `Root` since the root is neither a left nor a right submobile of anything.

```hcl
type side = Root | Left | Right
let print vertical m = downward fold
 fun _ (side, prefix) ->
  (Left,
   match side with
    | Right -> prefix ^ "|__"
    | _ -> prefix ^ "__"))
 (fun r (side, prefix) ->
  printf "%s++--B%d\n" prefix r;
  (Right,
   match side with
    | Left -> prefix ^ "|__"
    | _ -> prefix ^ "__"))
 (fun w (_, prefix) -> printf "%s++--0%d\n" prefix w)
 (Root, ""))
m
```
**Checking and searching.** An alternative use of this downward fold which produces unit values is to check a property of the tree, or search for some pattern, and raise an exception whenever something is found. Here is an example of checking that the lengths of the bars strictly decrease along each branch.

```kotlin
exception Unordered
let check_decreasing_length s m =
    try let _ = downwardFold
        (fun r a -> if a <= r then raise Unordered; r)
        (fun r a -> if a <= r then raise Unordered; r)
        (fun _ _ ->())
    max_int m
in true
with Unordered -> false
```

This second example searches an object whose weight is more than one, and returns a path to this object, encoded as a list of sides (restricted to “left” and “right”).

```kotlin
exception Found of side list
let find_heavy_object m =
    try let _ = downwardFold
        (fun _ path -> Left::path)
        (fun _ path -> Right::path)
        (fun w path -> if w>1 then raise (Found path))
    [] m
in None
with Found path -> Some(rev path)
```

## 5 Scanning Folds

The two previous folds made information flow either upward (structural fold) or downward (downward fold). Let us now consider a family of folds that make information flow from left to right<fnref n="3" />. Now the initial value is used to launch an accumulator from the left end of the tree, which means just before the leftmost leaf. A parameter function obj again describes the computation to be performed at a leaf object, here the computation of a new value of the accumulator. Then at each node (bar), the value computed by the fold on the left subtree is passed as initial value to the fold on the right subtree. In the simplest version, this takes only objects into account.

```kotlin
let leafFold
    (obj: int -> 'a -> 'a) (init: 'a') (m: mobile)
: 'a =
    let rec fold m acc =
        match m with
        | Obj(w)      -> acc |> obj w
        | Bar(_, m1, m2) -> acc |> fold m1 |> fold m2
    in
    fold m init
```

This new fold enables a more reasonable implementation of the fringe function seen in Section 3. Here the obj function accumulates each new object weight in a list, which is passed to the next subtree.

```kotlin
let fringe m =
    leafFold (fun w acc -> w :: acc) [] m
    |> rev
```

Remark that we could write a straightforward variant of this fold, propagating information from right to left. While using this variant, the final reversal of the list seen in the code fringe would not be needed.

**In/pre/postfix folds.** This basic scanning fold can then be enriched with an additional parameter bar, for inserting computations at the bars. As it is classical with nodes in tree walks, this computation on the bars can be inserted either between the folds on their two subtrees (infix fold), or before them (prefix fold), or after them (postfix fold). For instance:

```kotlin
let postfixFold
    (bar: int -> 'a -> 'a') (obj: int -> 'a -> 'a)
    (init: 'a') (m: mobile)
: 'a =
    let rec fold m acc =
        match m with
        | Obj(w) -> acc |> obj w
        | Bar(r, m1, m2) ->
            acc |> fold m1 |> fold m2 |> bar r
    in
    fold m init
```

Infix, prefix and postfix folds can solve the same problems whenever the bar function commutes with itself and with the obj function. This is however not always the case, and each variant may have its own applications.

Postfix fold can for instance be used for an alternative implementation of the balance check discussed in Section 3. In this version, we use as accumulator a stack of the weights of the subtrees to the left of the current scanning point. The postfix treatment consists in checking that the top two values of the stack (which means, the weights of the two subtrees of the considered node) are equal, and replace them with a combined weight.

```kotlin
let balanced m =
    try let _ = postfixFold
        (fun _ (w1::w2::stack) ->
            if w1 <> w2 then raise Unbalanced;
            w1+w2 :: stack)
        (fun w stack -> w :: stack)
    [] m
    in true
    with Unbalanced -> false
```

Notice that the stack is only traversed or modified as a consequence of the fold itself, that it is guaranteed that it will

<footnote n="3">³Variants that work from right to left, or whose direction depends on a Boolean parameter, could be deduced straightforwardly.</footnote>
always contain the two required elements when the bar function is called, and that it contains only one value at the end of the fold. This stack is reminiscent of the traditional stack used for storing intermediate results in an evaluator for arithmetic expressions. Take note that this technique is general enough for encoding any structural fold: these encodings are detailed in Section 6.

**Mobiles of great height.** Remark that the folds seen in this section so far can cause a stack overflow error, due to too many nested recursive calls, when applied to a mobile of excessive height. This issue is sometimes disregarded in simple exercises on trees, since “nice” trees are expected to have a small height-to-size ratio. There are however several ways of building a mobile that fits in memory but features such “pathological” height<fnref n="4" />. Here are two examples.

* Consider a string-shaped mobile, where each bar has an object as left son and a string-shaped mobile as right son. Such a mobile has a height of *N* for *N* + 1 objects of weights ranging from 1 to 2*N*⁻¹. This is feasible using a library for big integers instead of OCaml’s `int` (quadratic space footprint), or by representing weights only by their exponent (linearithmic space footprint).

* Another approach leverages the fact that immutable data can be shared: we can represent a mobile of height *N* with 2*N* objects of weight 1 by allocating only one object and *N* bars (linear space footprint).

Thus we believe it can be worth exploring some alternative implementations of the folds, where recursion is only done through tail calls.

**Tail-recursive implementations.** Our prefix fold, which propagates information linearly, could be rewritten in a tail-recursive way, which would allow execution using constant stack space. The fold then works on a list (conceptually, a stack) of subtrees, which basically corresponds to all the subtrees to the right of the current point, and contains the information that would be present in the call stack in a direct recursive version. Trading heap space for stack space this way does not change the order of the global space usage, but ensures the absence of stack overflow.

```hkl
let prefixFold
  (bar: int -> 'a -> 'a) (obj: int -> 'a -> 'a)
  (init: 'a) (m: mobile)
  : 'a =
let rec fold l acc = match l with
  | [] -> acc
  | Obj(w) :: tl -> acc |> obj w |> fold tl
  | Bar(r, m1, m2) :: tl ->
      acc |> bar r |> fold (m1 :: m2 :: tl)
in
fold [m] init
```

The same technique can be used for writing a tail-recursive variant of `leafFold`, by removing the parameter `bar` and its call. The `Bar` case then becomes:

```hkl
| Bar(_, m1, m2) :: tl ->
  acc |> fold (m1 :: m2 :: tl)
```

This tail-recursive implementation of the leaf fold is appropriate to get a constant-stack space implementation of the functions `size` and `weight` seen in Section 3, as well as the function `fringe`.

```hkl
let size = leafFold (fun _ -> (+)1) 0
let weight = leafFold (+) 0
```

The tail-recursive prefix fold also allows writing a constant-stack space implementation of height<fnref n="5" />. Here the accumulator contains the maximal depth of a leaf object seen so far, as well as a stack that mirrors the stack of submobiles by giving the depths of their roots (the -1 is a sentinel value that avoids a special case for the empty list, that will not be used).

```hkl
let height m = prefixFold
  (fun _ (max_d, d::st) -> (max_d, (d+1>::(d+1)::st))
   (fun _ (max_d, d::st) -> (max d max_d, st))
  (0, [0; -1]) m
  |> fst
```

The technique used for the tail-recursive implementations of `leafFold` and `prefixFold` can be enriched to provide a tail-recursive implementation of `infixFold`. For this, we use an additional stack to remember the values attached to the internal nodes. The fold then alternately uses elements from the main stack (containing right subtrees) and values from the auxiliary stack (containing parent nodes information), thanks to two mutually (tail-)recursive functions.

```hkl
let infixFold
  (bar: int -> 'a -> 'a) (obj: int -> 'a -> 'a)
  (init: 'a) (m: mobile)
  : 'a =
let rec fold l lr acc = match l with
  | [] -> acc
  | Obj(w) :: tl -> acc |> obj w |> aux tl lr
  | Bar(r, m1, m2) :: tl ->
      acc |> fold (m1 :: m2 :: tl) (r :: lr)
and aux l lr acc = match lr with
  | [] -> acc
  | r :: tl -> acc |> bar r |> fold l tl
in
fold [m] [] init
```

This use of stacks to remember information about parent nodes and sibling branches is somehow related to a zipper

<footnote n="4">⁴Also, uniformly random binary trees tend to have a fairly large height [12].</footnote>

<footnote n="5">⁵Finding the height of a binary tree while guaranteeing the absence of stack overflow is a “simple” yet surprisingly creative exercise proposed to me by Jean-Christophe Fillliâtre.</footnote>
structure [9]. Here however, we take advantage of our knowledge of the exploration pattern to discard the parts of the structure that will not be used anymore.

By lack of a meaningful problem on mobiles that could be solved specifically by `infixFold` and not by the other scanning variants, let us generalize for the end of this section only, and use our `mobile` type as support for binary search trees, where the values in the trees are encoded as bar lengths. Our tail-recursive `infix` fold gives a constant-stack space algorithm for checking that such a tree is indeed ordered.

```h
exception Unordered
let bst_check m =
  try let _ = infixFold
    (fun r a -> if a > r then raise Unordered; r)
    (fun _ a -> a)
    min_int m
  in true
with Unordered -> false
```

## 6 One Fold to Run Them All

Consider now the problem of checking that the lengths of the bars of a balanced mobile permit a planar drawing. For any given node Bar(r, m1, m2) it is enough to compute the right profile of the left submobile m1 and the left profile of the right submobile m2, and check that those do not overlap when their roots are 2r apart. Following the previous description, this geometry check could be implemented with a structural fold and some auxiliary functions for dealing with profiles. Such a version however would have a supralinear temporal complexity, in particular due to the repeated computations and comparisons of the profiles, which both have an execution time proportional to the height of the tree.

**A scanning algorithm for geometry check.** A better implementation scans the tree from left to right, while maintaining the profile of every element of the tree on the left of the current point. This combines several directions of information flow: downward propagation of horizontal displacement information, left-to-right propagation of profiles and upward extension of profiles. We first show a direct implementation, in order to make the algorithm fully explicit before discussing an appropriate folding pattern.

The direct implementation below is based on a main recursive function `check` taking as parameters a mobile `m` (the subject of recursion), an integer `x` giving the horizontal coordinate of the root of `m` (propagated downward), and a list profile giving the horizontal coordinate of the rightmost element seen so far at each level. The function returns an update of the list profile after `m` has been visited. The list is thus propagated from left to right, and shrinks or is extended in such manner that it is always relative to the current node. Conceptually, we consider that any level not yet visited has a rightmost element whose horizontal coordinate

equals minus infinity (implemented here as `min_int`). Two ad hoc functions `hd` and `tl` simulate this behaviour to avoid introducing a special case when the list is empty.

```h
exception Overlap
let geometry_check m =
  let hd = function [] -> min_int | x::_ -> x in
  let tl = function [] -> [] | _::tl -> tl in
  let rec check
    (m: mobile) (x: int) (profile: int list)
  : int list =
    match m with
    | Obj(w) ->
      if x-sqrt(w) < hd profile then raise Overlap;
      x+sqrt(w) :: tl profile
    | Bar(r, m1, m2) ->
      if x-r < hd profile then raise Overlap;
      profile |> tl
    |> check m1 (x-r) |> check m2 (x+r)
    |> List.cons (x+r)
  in
  try let _ = check m 0 [] in true
  with Overlap -> false
```

**A more general fold.** To account for the various flows of information seen in the previous geometry check algorithm, we propose a final fold corresponding to a full depth-first walk around the tree. It is parameterized by four functions: an `obj` function that plays the same role as its counterpart in the scanning folds (Section 5), and three functions before, between and after, each of which corresponds to a version of the bar function used in the scanning folds, respectively in prefix fold, infix fold and postfix fold. The direct implementation of this fold is not tail-recursive.

```h
let oneFold
  (before: int -> 'a -> 'a) (between: int -> 'a -> 'a)
  (after: int -> 'a -> 'a) (obj: int -> 'a -> 'a)
  (init: 'a) (m: mobile)
: 'a =
let rec fold m acc = match m with
  | Obj(w) -> acc |> obj w
  | Bar(r, m1, m2) ->
    acc |> before r |> fold m1
  |> between r |> fold m2
  |> after r
  in
fold m init
```

The four function parameters are similar in spirit to the methods that define a visitor in the Boost Graph Library [13], which provides a generic interface for traversing graphs: each function defines the behaviour of the algorithm on a specific event point of the exploration.

This new fold function is general enough to implement the efficient geometry check, provided we use one last trick: include in the accumulator a stack tracking the horizontal coordinates of parent nodes we will have to return to eventually.
Thus the accumulator has three components: a profile list giving the horizontal coordinates of the elements to the left of the current point (identical to the corresponding parameter in the previous implementation of `geometry_check`), the horizontal coordinate `x` of the current point (also the same as before), and a stack (list) of the horizontal coordinates of the parents of the current point. The functions before and after perform a transfer (each in one direction) between the profile and the stack of parents. The intermediate function between updates the coordinate `x` of the root of the submobile considered, and finally the function after retrieves from the stack the horizontal coordinate `xp` of the parent bar we are about to return to.

```javascript
let geometry_check m =
  let hd = function [] -> min_int | x::_ -> x in
  let tl = function [] -> [] | _::tl -> tl in
  try let _ = oneFold
    (fun r (profile, x, parents) ->
     if x-r < hd profile then raise Overlap;
     (tl profile, x-r, x::parents))
    (fun r (profile,_, x::parents) ->
     (profile, x+r, x::parents))
    (fun r (profile, x, xp::parents) ->
     (x::profile, xp, parents))
    (fun w (profile, x, parents) ->
     if x-sqrt(w) < hd profile then raise Overlap;
     (x+sqrt(w) :: tl profile, x, parents))
    ([], 0, []) m
  in true
  with Overlap -> false
```

**Encoding folds.** We now show that the various folds seen in previous sections can be simulated by the generalized fold. The scanning folds from Section 5 are all straightforward instances of the generalized fold, where some of the functions before, between and after are set to the identity. For instance, the infix fold could be expressed as follows.

```javascript
let infixFold
  (bar: int -> 'a -> 'a) (obj: int -> 'a -> 'a)
  (init: 'a) (m: mobile)
: 'a =
  oneFold
  (fun _ a -> a) bar (fun _ a -> a) obj init m
```

Simulating the downward fold from Section 4 using the generalized fold requires the additional trick already seen with the efficient geometry check: the accumulator is not a single value, but a stack of the values computed from the root down to the current branch, which allows backtracking. Then define before as pushing on the top of the stack the propagated value `left r a` (where `a` is the value of the preceding level), and between as replacing this value by `right r a`, and finally after as popping this value.

```javascript
let downwardFold
  (left: int -> 'a -> 'a) (right: int -> 'a -> 'a)
  (obj: int -> 'a -> unit) (init: 'a) (m: mobile)
: unit =
  let _ = oneFold
    (fun r (a :: accs) -> (left r a) :: a :: accs)
    (fun r (_ :: a :: accs) -> (right r a) :: a :: accs)
    (fun r (a :: accs) -> accs)
    (fun w (a :: accs) -> obj w a; a :: accs)
  [init] m
  in ()
```

Simulating the structural fold from Section 3 again requires using a stack as accumulator, except this time the stack does not store values corresponding to the ancestors of the current node, but rather values computed in the left subtrees. This is reminiscent of the traditional stack used for storing intermediate results in an evaluator for arithmetic expressions, and generalizes the technique used for encoding the balance check with a postfix fold in Section 5. Since this encoding does not need the before and between parameters of the generalized fold we directly use the postfix fold, which is already known to be an instance of the generalized fold.

```javascript
let structuralFold
  (bar: int -> 'a -> 'a -> 'a) (obj: int -> 'a)
  (m: mobile)
: 'a =
  postfixFold
    (fun r (a1 :: a2 :: accs) -> bar r a1 a2 :: accs)
    (fun w accs -> obj w :: accs)
  [] m
  > List.hd
```

## 7 Level Fold

In the previous sections we described several folding patterns corresponding to several ways of traversing a tree, and a general fold covering them all. However, the standard textbook collection of tree exploration algorithms is not exhausted yet. As an opening before concluding this exploration of tree exploration patterns, let us consider two algorithms related to breadth-first traversal, which in our setting may be seen as folding “by level”.

**Geometry check, level by level.** The algorithm for geometry check seen in Section 6 is based on a quite subtle propagation of a current profile of the mobile from left to right. A possibly simpler approach would be to compute the coordinates of each element at each level, and linearly check that they do not overlap. The code below performs this in a single breadth-first traversal of the mobile, where each level of the mobile is traversed from left to right. The main function check takes as parameters:

* a list `lv1` of the remaining elements of the current level, which is progressively consumed,
* the horizontal coordinate limit of the right end of the last element seen in the current level, which increases at each call at the same level,

* a list `nxt` of the elements of the next level discovered so far, which is progressively filled.

In the lists `lvl` and `nxt`, each element is paired with its horizontal coordinate. When we arrive at the end of a level, we continue with the next level by reversing the `nxt` list (if it is not empty) and taking it as the new `lvl`. At this point we reinitialize `limit` and `nxt`.

```h
let geometry_check m =
  let rec check limit lvl nxt = match lvl with
    | [] -> if nxt<>[] then check min_int (rev nxt) []
    | (x, Obj(w)) :: tl ->
      if x-sqrt(w) < limit then raise Overlap;
      check (x+sqrt(w)) tl nxt
    | (x, Bar(r, m1, m2)) :: tl ->
      if x-r < limit then raise Overlap;
      check (x+r) tl ((x+r, m2) :: (x-r, m1) :: nxt)
  in
  try let _ = check min_int [(0, m)] [] in true
  with Overlap -> false
```

Remark that this main check function is tail-recursive and thus that, contrarily to the one seen in Section 6, this new implementation of `geometry_check` executes in constant stack space.

**Folding by level.** The BFS-based geometry check is easily generalized as a new folding function that works by levels, and is tail-recursive. This fold uses an accumulator that is updated by folding each node or leaf, and also at level changes.

```h
let levelFold
  (bar: int -> 'a -> 'a) (obj: int -> 'a -> 'a)
  (level: 'a -> 'a) (init: 'a) (m: mobile)
: 'a =
let rec fold lvl nxt acc = match lvl with
| [] ->
  if nxt=[]
  then acc
  else acc > level > fold (rev nxt) []
| Obj(w) :: tl -> acc > obj w > fold tl nxt
| Bar(r, m1, m2) :: tl ->
  acc > bar r > fold tl (m1 :: m2 :: nxt)
in
fold [m] [] init
```

This folding function can be used for a new constant-stack space implementation of `height`, that simply counts the levels as they are traversed.

```h
let height m =
  levelFold (fun _ x -> x) (fun _ x -> x) ((+)1) 0 m
```

The level fold can also be instantiated with the new geometry check algorithm. However, quite sadly the resulting

code is not as elegant as the direct version, since the accumulator has to maintain two lists `xs` and `nxs` that mirror the lists `lvl` and `nxt` by giving the horizontal coordinate of each element (since these are not carried automatically by the internal structures of the fold). This is similar to what can be seen in the implementation of `height` using the prefix fold in Section 5, which uses an explicit list of depths. In both cases this is related to the fact that the accumulator is not used for a simple aggregate value, but rather to keep some information about nodes that have not been explored yet.

```h
let geometry_check m =
  try let _ = levelFold
    (fun r (l, x::xs, nxs) ->
      if x-r < l then raise Overlap;
      (x+r, xs, x+r :: x-r :: nxs))
    (fun w (l, x::xs, nxs) ->
      if x-sqrt(w) < l then raise Overlap;
      (x+sqrt(w), xs, nxs))
    (fun (l, [], nxs) ->
      (min_int, List.rev nxs, []))
    (min_int, [0], []) m
  in true
  with Overlap -> false
```

**Direct ASCII rendering of a mobile.** We have already seen a vertical rendering of a mobile in Section 4, which was a best effort with a single downward traversal. Now consider the same problem of printing the logical structure of a mobile on the standard output, but this time keeping its natural orientation. As before, we focus on the logical shape and do not try to respect the actual lengths of the bars.

<figure><img src="image_9.png" /></figure>

This task mixes by-level aspects, since we print on the standard output one line after the other, from left to right, but also structural (upward) flow of information, since we need to know the sizes of the submobiles to print bars of the appropriate length and at the right position.

We leave as an open question the design of a folding pattern that would allow this effect. We show below an implementation that uses a structural fold to produce a list `f1` of functions, where each function prints a line of the mobile. This code however uses an auxiliary recursive function on lists to combine lists of functions, and also a list iterator to trigger the final print, and thus falls short of our goal of using a single tree fold only.
The two auxiliary functions `skip` and `draw` are used to print spaces or bars of a given length. The auxiliary function `zip` merges two lists of functions (for printing the levels of two twin submobiles) into a single by-level list. In addition to the two lists `l1` and `l2`, it takes as parameters the widths `s1` and `s2` of the submobiles, to replace empty levels by an appropriate amount of spaces. Finally, the fold itself produces a triple `(s1, f1, sr)` where `f1` is the list of the functions printing each level of a mobile, and `s1` (resp. `sr`) is the size of its left (resp. right) submobile.

```python
let skip k = printf "%S" (String.make (2*k) ' ')
let draw k = printf "%S" (String.make (2*k) '-')

let rec zip s1 l1 s2 l2 = match l1, l2 with
| [], [] -> []
| x::tl, [] ->
| (fun () -> x(); skip (1+s2)) :: zip s1 tl s2 []
| [], x::tl ->
| (fun () -> skip (s1+1); x()) :: zip s1 [] s2 tl
| x1::tl1, x2::tl2 ->
| (fun () -> x1 (); skip 1; x2()) :: zip s1 tl1 s2 tl2

let print m =
  let_, f1, _ = structuralFold
    (fun_ (s1l, f1l, sr1) (s12, f12, sr2) ->
     let s1 = s1l + 1 + sr1 and s2 = s12 + 1 + sr2 in
     (s1,
      (fun () -> skip s1; printf "|_"; skip s2)
      ::
      (fun () ->
       skip s1l; printf "+-"; draw sr1; printf "+-";
       draw s12; printf "+_"; skip sr2)
      ::
      zip s1 f1l s2 f12,
      s2))
    (fun _ -> (0, [(fun () -> printf "|_");
                      (fun () -> printf "0_")], 0))

m
in List.iter (fun f -> f(); printf "\n") f1
```

## 8 Conclusion

Binary trees are a rich structure in which information may flow in many different ways. This motivates the use of a variety of distinct iteration patterns, suitable for implementing different algorithms. We proposed three simple pattern families: structural fold, downward fold and scanning folds, as well as a more general fold able to express more complex

algorithms and to simulate the other three. On the other hand, this generalized fold is also more complex to use since it depends on more parameters. Thus the "simple", less expressive folds should definitely remain useful patterns for the pragmatic programmer.

## Acknowledgments

My warmest thanks to Olivier Danvy, for teaching us that programs can tell stories. I am also grateful to Jean-Christophe Filliâtre, who proposed to me lots of programming exercises, some of which are present in this paper.

## References

[1] Thibaut Balabonski, Sylvain Conchon, Jean-Christophe Filliâtre, Kim Nguyen, and Laurent Sartre. 2022. Informatique MP2I/MPI. Ellipses, Paris, France.

[2] Olivier Danvy. 2004. Sur un Exemple de Patrick Greussay. BRICS Report Series 11, 41 (Dec. 2004). doi:10.7146/brics.v11i41.21866

[3] Olivier Danvy. 2022. Getting There and Back Again. CoRR abs/2203.00145 (2022). doi:10.48550/ARXIV.2203.00145 arXiv:2203.00145

[4] Olivier Danvy. 2023. Folding left and right matters: Direct style, accumulators, and continuations. Journal of Functional Programming 33 (2023). doi:10.1017/S0956796822000156

[5] Olivier Danvy and Mayer Goldberg. 2005. There and Back Again. Fundam. Informaticae 66, 4 (2005), 397–413. http://content.iospress.com/articles/fundamenta-informaticae/fi66-4-05

[6] Jeremy Gibbons. 1993. Upwards and downwards accumulations on trees. In Mathematics of Program Construction. Springer Berlin Heidelberg, Berlin, Heidelberg, 122–138.

[7] Jeremy Gibbons. 1996. Functional Pearls: Deriving tidy drawings of trees. Journal of Functional Programming 6, 3 (1996), 535–562. doi:10.1017/S0956796800001842

[8] Patrick Greussay. 1977. Contribution à la définition interprétative et à l'implémentation des lambda-languages. Thèse d'état. Université de Paris VII, Paris, France.

[9] Gérard P. Huet. 1997. The Zipper. J. Funct. Program. 7, 5 (1997), 549–554. doi:10.1017/S0956796897002864

[10] Andrew Kennedy. 1996. Functional Pearls: Drawing Trees. Journal of Functional Programming 6, 3 (1996), 527–534. doi:10.1017/S0956796800001830

[11] OCaml 2025. OCaml language. https://ocaml.org

[12] Frank Ruskey. 1980. On the Average Shape of Binary Trees. SIAM J. Algebraic Discret. Methods 1, 1 (1980), 43–50. doi:10.1137/0601007

[13] Jeremy G. Siek, Lie-Quan Lee, and Andrew Lumsdaine. 2002. The Boost Graph Library - User Guide and Reference Manual. Pearson / Prentice Hall.

[14] Kenneth J. Supowit and Edward M. Reingold. 1982. The Complexity of Drawing Trees Nicely. Acta Informatica 18 (1982), 377–392. doi:10.1007/BF00289576

Received 2025-07-16; accepted 2025-07-31