Fold pattern compared with visitor pattern

help
2

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!

3 Likes