It seems that the Fold example in the Rust patterns book uses connotations that are totally un-necessary and confuses the reader.

Let me put the following thing in bold:

**The Visitor pattern and the Fold pattern have nothing to do with each other**.

It is unfortunate that Rust patterns book chose the example that it did, mixing the Fold pattern with the Visitor pattern.

If you are already familiar with the functional programming notion of "folds", then the following example will be redundant for you. Otherwise, I think it would be helpful:

Consider the std-lib `Iterator::fold`

. Abstractly, the fold function tells the following:

Given some type that is an `Iterator`

(meaning we can call `next()`

on it to either get `Some(element)`

or `None`

if there is nothing left), we can define a `fold()`

function on that type. The `fold`

function takes two additional parameters, a binary operator `op`

and an initial value `init`

. If the type yields the following sequence of values `a, b, c, d`

, then the `fold()`

function does the following (abstractly): It stores `init`

in `tmp`

. Then for each element of the sequence `x`

, it does `tmp op x`

and stores the value in `tmp`

. It returns the final value of `tmp`

. Thus, here the answer would be `(((init op a) op b) op c) op d`

.

The key points here are: we need an `Iterator`

(something that yields a sequence of values) and we need a **binary** operator `op`

. If the operator is something simple like `+`

, then we simply find the sum of values, plus some `init`

.

This is the simple "list" view of folds. It turns out (and again this is from FP) that folds don't have to be applied on lists. Any operation on a data-structure that collapses it to a single value can be viewed as a fold.

To elaborate on this, let me (roughly) port some Haskell code into Rust. Let us define a `Foldable`

trait.

```
trait Foldable<T, F, I>
where
F: Fn(&T, I) -> I,
{
fn foldr(&self, f: F, init: I) -> I;
}
```

Here, the `Foldable`

trait defines a right-fold, as opposed to the left-fold defined by `Iterator::fold`

. This means that, semantically operations will occur from right to left. More importantly, note how `F`

is defined - it is defined as `Fn(&T, I) -> I`

. This means that in the binary operator, the accumulator variable is now on the right (for a right-fold). It used to be in the left for the left fold (you can scroll up and verify that).

Now, let us define a `BinaryTree`

.

```
enum BinaryTree<T> {
Empty,
Leaf {
value: T,
},
Node {
left: Box<BinaryTree<T>>,
value: T,
right: Box<BinaryTree<T>>,
},
}
```

This is just a normal binary tree, with the nodes containing value of some type `T`

(what `T`

is won't be relevant to us now).

Since we have a binary tree, we may want to find something like the number of nodes in the tree, or sum of all nodes. *That can be defined as a fold!*

The sum of all nodes will correspond to the following binary operator (assuming `T = i32`

and `I = i32`

) :

```
fn node_sum_op(val: &i32, sum: i32) -> i32 {
sum + val
}
```

The no of nodes will correspond to the following operator (`T`

can be whatever, `I = usize`

):

```
fn node_cnt_op<T>(_val: &T, sum: usize) -> usize {
1 + sum
}
```

Now, let us implement `Foldable`

for `BinaryTree`

. It is defined quite directly:

```
impl<T, F, I> Foldable<T, F, I> for BinaryTree<T>
where
F: Fn(&T, I) -> I,
{
fn foldr(&self, f: F, init: I) -> I {
use BinaryTree::*;
match self {
Empty => init,
Leaf { value } => f(&value, init),
Node { left, value, right } => left.foldr(&f, f(&value, right.foldr(&f, init))),
}
}
}
```

Basically, we first recurse into the right sub-tree (depth-first). Then we compute `value f right-tree-value`

. Finally, we recurse into the left-subtree.

So, now for appropriate trees, we can call `tree.foldr(node_cnt_op, 0)`

or `tree.foldr(node_sum_op, 0)`

.

Hope this helps!