6.4. Fundamental Sequence Algorithms

The pattern used by back_inserter of "folding" sequence elements into a result, is at the heart of the way sequences are processed in a functional environment. Users of Haskell and ML will immediately recognize it as the pattern used by the fold function (and hardcore STL users will recognize it as the pattern of std::accumulate). In pseudocode:

    fold(Seq, Prev, BinaryOp) :=


       if Seq is empty then:


           Prev


       else:        // combine the first element with Prev


           fold(    // and process the rest recursively


               tail(Seq)


             , BinaryOp(Prev, head(Seq))


             , BinaryOp


           )

From the caller's viewpoint, Prev should probably be called InitialType. We chose the name Prev because it makes understanding the algorithm's implementation easier. At each step of processing other than the first, Prev is the result from the previous step of processing.

You can build many other more complicated sequence traversal algorithms on top of fold. For example, we can reverse any front-extensible sequence with:

    template <class Seq>


    struct reverse


      : mpl::fold<


           Seq


         , typename mpl::clear<Seq>::type // initial type


         , mpl::push_front<_,_>           // binary operation


        >


    {};

It's worth noticing the curious property of fold that, when we use it with push_front, the result always comes out in reverse order. Since lists can only be built with push_front and it's mighty inefficient to have to use reverse just to put things back in the right order every time we generate a list result, MPL also provides a reverse_fold metafunction that processes elements in reverse order. To do that efficiently with a sequence that can only be traversed in the forward direction may seem like quite a trick at first, but it's actually pretty simple. Instead of operating on the sequence's first element and folding the rest, we first fold the rest and then operate on the first element:

    reverse_fold(Seq, Prev, BinaryOp) :=


       if Seq is empty then:


           Prev


         else:          // process the rest of the sequence


           BinaryOp(    // and combine with the first element


               reverse_fold(tail(seq), Prev, BinaryOp)


             , head(seq)


           )

Instead of processing each sequence element "on the way in" to the traversal, we're processing it "on the way out."

If we can process elements either "going in" or "coming back out," why not both? MPL's reverse_fold is actually a little more general than what we've shown you. A fourth optional argument can be used to supply an "inward," or forward, operation. So the algorithm actually looks more like this:

    reverse_fold(Seq, Prev, OutOp, InOp = _1) :=


       if Seq is empty then:


           Prev


         else:


           OutOp(


               reverse_fold(


                   tail(Seq)


                 , InOp(Prev,head(Seq)) // just Prev by default


                 , OutOp


                 , InOp)


             , head(Seq)


           )

This generalization allows us to take full advantage of the inherently bidirectional pattern of a recursive sequence traversal. Note that InOp is, by default, just a function that returns its first argument. When we don't supply InOp, it's as though Prev were passed directly to the recursive call.

Before we finish with low-level iteration algorithms and move on to more exciting fare, there's just one more generalization in MPL's fold algorithm family we need to cover: Instead of iterating over elements of the sequence, we can iterate over positions, that is, iterator values. That's useful, for example, if we want to process consecutive subranges of the input sequence. Since we can always retrieve the element referenced by an iterator, it's slightly more general to fold sequence iterators with iter_fold than to fold sequence elements with plain fold. In pseudocode, iter_fold is defined as follows:

    iter_fold(Seq, Prev, BinaryOp) :=


       if Seq is empty then:


           Prev


         else:           // combine the first position with Prev


           iter_fold(    // and process the rest recursively


               tail(Seq)


             , BinaryOp(Prev, begin(Seq))


             , BinaryOp


           )

The main difference between fold and iter_fold is that the second argument to BinaryOp is an iterator instead of an element. Naturally, the full generalization, reverse_iter_fold, is provided too:

    reverse_iter_fold(Seq, Prev, OutOp, InOp = _1) :=


       if Seq is empty then:


           Prev


         else:


           OutOp(


               reverse_iter_fold(


                   tail(Seq)


                 , InOp(Prev, begin(Seq))


                 , OutOp


                 , InOp)


             , begin(Seq)


           )