alux-traversable

traverse and the Traversable class are Conor McBride and Ross Paterson's, from Applicative programming with effects (Journal of Functional Programming 18(1):1–13, 2008, doi:10.1017/S0956796807006326) — the paper that introduced applicative functors and, with them, the operator for running an effectful function over a structure:

traverse  :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
sequenceA = traverse id

We introduce Applicative functors — an abstract characterisation of an applicative style of effectful programming, weaker than Monads and hence more widespread.

… hence we introduce the type class Traversable, capturing functorial data structures through which we can thread an applicative computation.

— McBride and Paterson, §1 and §3

Jeremy Gibbons and Bruno C. d. S. Oliveira later showed in The essence of the Iterator pattern (Journal of Functional Programming 19(3–4):377–402, 2009, doi:10.1017/S0956796809007291) that this one operator is what the iterator pattern is reaching for: walking a structure, doing something effectful at each element, and rebuilding the structure with the effects sequenced.

t is the traversable structure and f is the applicative effect. Rust cannot quantify over t, so this crate provides the two instances worth having — Option and iterators — with f fixed to Result, whose applicative is the short-circuiting one. So: a function returning Result becomes composable inside an Option or an iterator, sequencing the Result effect while preserving the shape and order of the outer value. The suffix identifies the wrapper produced inside Result:

sequence, sequence_opt, and sequence_iter are the corresponding identity mappings for values that already contain Result:

• Some(42).traverse(|x| Ok(x + 1)) == Ok(Some(43))
• Some(Ok(42)).sequence() == Ok(Some(42))
• [1, 2].traverse(|x| Ok(x + 1)) == Ok(vec![2, 3])
• [1, 2].traverse_opt(|x| Ok(Some(x))) == Ok(vec![1, 2])
• [1, 2].traverse_iter(|x| Ok([x])) == Ok(vec![1, 2])
• [Ok(None), Ok(Some(1))].sequence_opt() == Ok(vec![1])

Which method applies is decided by what the mapping states inside Result, and what comes out is decided by what was traversed:

Option .traverse/sequence T        ==> Option
Option .traverse/sequence Option   ==> Option
Option .traverse/sequence Iter     ==> Vec
Iter   .traverse/sequence T        ==> Vec
Iter   .traverse/sequence Option   ==> Vec
Iter   .traverse/sequence Iter     ==> Vec

Iterator traversal accepts stateful FnMut transformations, preserving source order and stopping at the first error.

The papers state the laws as naturality, identity, and composition: traversal commutes with applicative morphisms, traversal in the identity applicative is fmap, and two traversals composed are one traversal in the composed applicative. That last one is why the suffixes are worth having — traverse_opt and traverse_iter are each a traversal whose inner structure is already composed, so a caller writes one pass where two would nest.

Read in the Option and iterator shapes, the laws are:

• traversing None performs no effect and returns Ok(None);
• iterator traversal preserves order and stops at the first error;
• optional iterator traversal omits None without reordering the remaining values;
• sequencing equals traversal by the identity function;
• traverse_iter concatenates each successful inner iterator in input order.

What it is for

Hold an Option<Key>, and a function that reads one: fn record(Key) -> Result<Record, Error>. Map one over the other and you get Option<Result<Record, Error>> — which is the two layers in the wrong order. ? works on the outside, and the failure is now on the inside, so it cannot be reached without taking the Option apart first. What the caller wants is Result<Option<Record>, Error>: fail if the read failed, state nothing if there was no key.

The paper arrives at it from the same direction, mapping a failure-prone function across a list and then collecting:

As you can see, flakyMap traverses ss twice — once to apply f, and again to collect the results. More generally, it is preferable to define this applicative mapping operation directly, with a single traversal.

— McBride and Paterson, §3

traverse is that single traversal: the swap done while mapping — one pass, and the result comes out with the failure outermost where ? can reach it:

The reason this is worth a name is that the layers accumulate. A store read both fails and states nothing: Result<Option<Raw>, Error>. What it states must still be decoded, which fails on its own: Raw -> Result<Record, Error>. Put the two together without traversing and you are holding Result<Option<Result<Record, Error>>, Error> before doing anything with it — and the next step adds another layer.

Why it reads better

Traversed, the path has one line per layer, and each line is an operation with a fixed meaning: traverse runs a fallible step inside a structure and brings the failure to the outside, traverse_opt does the same where the step itself may state nothing, traverse_iter where it may state several things. The shape of the code is the shape of the path, so a reader checks it by reading it, and a fourth level costs one more line rather than one more level of nesting.

By hand, every one of those layers becomes control flow invented on the spot: an early return here, an accumulator there, a continue that has to mean the right loop, a match whose two None arms mean different things. None of it is wrong Rust. What it lacks is that its correctness is re-established by reading it, at every site, every time it is touched — while the traversal's correctness was settled once, by the laws above, for every site at once. A loop states how; traverse states what, and that is the difference the combinator was named for.

The cost shows up in change, not in the first writing. Add a step to the traversed version and the types refuse anything that drops a layer. Add one to the hand-written version and the compiler is happy either way — a continue that should have been a return, or an accumulator cleared one loop too high, reads exactly like the code that was right.

Reading the example

Read it as one layer coming off at a time. raw(key)? leaves an Option<Raw>; traverse runs the decode inside it and states Result<Option<Record>, Error>, which ? opens again. traverse_opt on the parent key takes two layers at once — the key may not be there, and what it names may not be there either — and both come out as one Option<Record>. traverse over the parts turns many reads into one, stopping at the first key that had to be there. The hand-written twin meets the same three layers as a match returning early, a match inside a match whose two None arms mean different things, and a loop that has to remember which absence is fatal.

The example is a spec rather than an executable program: the store is stated over abstract types, nothing is implemented behind it, and nothing runs. That is the denotational style this workspace is written in, and it is also the shortest way to show a traversal without first inventing a database. That style is what the ALUX programming guidelines are about: Denotations and Laws and interpretations.

use extend::ext;
use alux_traversable::*;

trait Store {
    type Error;
    type Key: Copy;
    type Raw;
    type Record;
    type Part;
    type Assembly;

    /// Reads what a key stands for, which may not be there.
    fn raw(&self, key: Self::Key) -> Result<Option<Self::Raw>, Self::Error>;
    /// Decodes a record, which fails on its own terms.
    fn record(&self, raw: Self::Raw) -> Result<Self::Record, Self::Error>;
    /// Decodes a part, likewise.
    fn part(&self, raw: Self::Raw) -> Result<Self::Part, Self::Error>;
    /// The key a record may name.
    fn parent(&self, record: &Self::Record) -> Option<Self::Key>;
    /// The keys a record does name, each of which must be there.
    fn parts(&self, record: &Self::Record) -> Vec<Self::Key>;
    /// States what a record, its parent, and its parts come to.
    fn assemble(
        &self,
        record: Self::Record,
        parent: Option<Self::Record>,
        parts: Vec<Self::Part>,
    ) -> Self::Assembly;
    /// States a key that had to be there and was not.
    fn missing(&self, key: Self::Key) -> Self::Error;
}

/// Reads one whole assembly: a record, the record it may name, and the parts it does.
#[ext(name = StoreAssembly)]
pub impl<This> This
where
    This: Store,
{
    /// One line per layer, each a named operation.
    fn assembled(&self, key: This::Key) -> Result<Option<This::Assembly>, This::Error> {
        self.raw(key)? // may fail, and may state nothing
            .traverse(|raw| self.record(raw))? // decode inside the option
            .traverse_opt(|record| {
                // no record, no assembly
                let parent = self
                    .parent(&record)
                    .traverse_opt(|key| self.raw(key)?.traverse(|raw| self.record(raw)))?; // two absences, one option

                let parts = self.parts(&record).into_iter().traverse(|key| {
                    // many reads, one result, stopping at the first failure
                    let raw = self.raw(key)?.ok_or_else(|| self.missing(key))?; // this one must be there

                    self.part(raw)
                })?;

                Ok(Some(self.assemble(record, parent, parts)))
            })
    }

    /// The same, with every layer re-derived as control flow.
    fn assembled_by_hand(&self, key: This::Key) -> Result<Option<This::Assembly>, This::Error> {
        let record = match self.raw(key)? {
            Some(raw) => self.record(raw)?,
            None => return Ok(None), // this absence leaves the function
        };

        let parent = match self.parent(&record) {
            Some(key) => match self.raw(key)? {
                Some(raw) => Some(self.record(raw)?),
                None => None, // and these two mean different things
            },
            None => None,
        };

        let keys = self.parts(&record);
        let mut parts = Vec::with_capacity(keys.len());
        for key in keys {
            let raw = match self.raw(key)? {
                Some(raw) => raw,
                None => return Err(self.missing(key)), // this one is fatal, two loops in
            };

            parts.push(self.part(raw)?); // and the push must not outlive its `?`
        }

        Ok(Some(self.assemble(record, parent, parts)))
    }
}