Fold pattern compared with visitor pattern

I've been trying my hand at the visitor pattern and have landed at a point where the 'generic' flavor feels comfortable.

I was hoping to step-up to the fold pattern. However, I found the example and description quite difficult to relate back to the visitor pattern, and how to implement the Box, borrow and reference counter flavors.

Turns out I was not alone.

I am particularly interested in learning:

  • how to implement the fold pattern in Rust as it compares to the Visitor pattern.
  • how/when to/not use it to avoiding having to reallocate memory, i.e. the use to reference counters to "reuse the original data structures"

Does anyone know of blog posts or books dealing with these topics?

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

Just wanted to note my thanks while I study this - it'll take a while before I know if I have any follow-up questions, so thanks again until then.

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.