Chapter 11: Traversing the Stone

So far, in our cirque du conteneur, you've seen us tame the ferocious functor, bending it to our will to perform any operation that strikes our fancy. You've been dazzled by the juggling many dangerous effects at once using function application to collect the results. Sat there in amazement as containers vanished in thin air by joining them together. At the side effect sideshow, we've seen them composed into one. And most recently, we've ventured beyond what's natural and transformed one type into another before your very eyes.

And now for our last trick, we'll look at traversals. We'll watch types soar over one another as if they were trapeze artists holding our value intact. We'll reorder effects like the trolleys in a tilt-a-whirl. When our containers get intertwined like the limbs a contortionist, we can use this interface to straighten things out. We'll witness different effects with different orderings. Fetch me my pantaloons and slide whistle, let's get started.

Types n' Types

Let's get weird:

# read_file :: str -> Task Error str
# first_words :: str -> str
first_words = compose(join(' '), take(3), split(' '))
# tldr :: FileName -> Task Error str
tldr = compose(map(first_words), read_file)
map(tldr, ['file1', 'file2'])
# [Task('hail the monarchy'), Task('smash the patriarchy')]

Here we read a bunch files and end up with a useless array tasks. How might we fork each one these? It would be most agreeable if we could switch the types around to have Task Error [str] instead [Task Error str]. That way, we'd have one future value holding all the results, which is much more amenable to our async needs than several future values arriving at their leisure.

Type Feng Shui

The Traversable interface consists two glorious functions: sequence and traverse.

Let's rearrange our types using sequence:

sequence(List, Maybe(['the facts'])) # [Maybe('the facts')]
sequence(Task, Map({ 'a': Task(1), 'b': Task(2) })) # Task(Map({ a: 1, b: 2 }))
sequence(IO, Either(IO('buckle my shoe'))) # IO(Right('buckle my shoe'))
sequence(Either, [Either('wing')]); # Right(['wing'])
sequence(Task, left('wing')) # Task(Left('wing'))

See what has happened here? Our nested type gets turned inside out like a pair leather trousers on a humid summer night. The inner functor is shifted to the outside and vice versa. It should be known that sequence is bit particular about its arguments. It looks like this:

# sequence :: (Traversable t, Applicative f) => (a -> f a) -> t (f a) -> f (t a)
sequence = curry(lambda x: x.sequence)

Let's start with the second argument. It must be a Traversable holding an Applicative, which sounds quite restrictive, but just so happens to be the case moreten than not. It is the t (f a) which gets turned into a f (t a). Isn't that expressive? It's clear as day the two types do-si-do around each other. That first argument there is merely a crutch and only necessary in an untyped language. It is a type constructor (our *) provided so that we can invert map-reluctant types like Left - more on that in a minute.

Using sequence, we can shift types around with the precision a sidewalk thimblerigger. But how does it work? Let's look at how a type, say Either, would implement it:

class Either:
# ...
def sequence(self)
return self.value.map(Either)

Ah yes, if our value is a functor (it must be an applicative, in fact), we can simply map our constructor to leap frog the type.

You may have noticed that we've ignored the entirely. It is passed in for the occasion where mapping is futile, as is the case withLeft`:

class Left:
# ...
def sequence(self):
return self

We'd like the types to always end up in the same arrangement, therefore it is necessary for types like Left who don't actually hold our inner applicative to get a little help in doing so. The Applicative interface requires that we first have a Pointed Functor so we'll always have a ` to pass in. In a language with a type system, the outer type can be inferred from the signature and does not need to be explicitly given.

Effect Assortment

Different orders have different outcomes where our containers are concerned. If I have [Maybe a], that's a collection possible values whereas if I have a Maybe [a], that's a possible collection values. The former indicates we'll be forgiving and keep "the good ones", while the latter means it's an "all or nothing" type situation. Likewise, Either Error (Task Error a) could represent a client side validation and Task Error (Either Error a) could be a server side one. Types can be swapped to give us different effects.

# from_predicate :: (a -> Bool) -> a -> Either e a
# partition :: (a -> Bool) -> [a] -> [Either e a]
partition = lambda f: map(from_predicate(f))
# validate :: (a -> Bool) -> [a] -> Either e [a]
validate = lambda f: traverse(Either, from_predicate(f))

Here we have two different functions based on if we map or traverse. The first, partition will give us an array Lefts and Rights according to the predicate function. This is useful to keep precious data around for future use rather than filtering it out with the bathwater. validate instead will give us the first item that fails the predicate in Left, or all the items in Right if everything is hunky dory. By choosing a different type order, we get different behavior.

Waltz the Types

Time to revisit and clean our initial examples.

# read_file :: str -> Task Error str
# first_words :: str -> str
first_words = compose(join(' '), take(3), split(' '))
# tldr :: FileName -> Task Error str
tldr = compose(map(first_words), read_file)
traverse(tldr, ['file1', 'file2'])
# Task(['hail the monarchy', 'smash the patriarchy']);

Using traverse instead map, we've successfully herded those unruly Tasks into a nice coordinated array results. This works for any traversable type. These mathematical apis tend to capture most things we'd like to do in an interoperable, reusable way, rather than each library reinventing these functions for a single type.

No Law and Order

Well now, before you get all judgemental and bang the backspace button like a gavel to retreat from the chapter, take a moment to recognize that these laws are useful code guarantees. 'Tis my conjecture that the goal most program architecture is an attempt to place useful restrictions on our code to narrow the possibilities, to guide us into the answers as designers and readers.

An interface without laws is merely indirection. Like any other mathematical structure, we must expose properties for our own sanity. This has a similar effect as encapsulation since it protects the data, enabling us to swap out the interface with another law abiding citizen.

Come along now, we've got some laws to suss out.

Identity

identity1 = compose(sequence(Identity), map(Identity));
identity2 = Identity
# test it out with Right
identity1(Either('stuff'));
# Identity(Right('stuff'))
identity2(Either('stuff'));
# Identity(Right('stuff'))

This should be straightforward. If we place an Identity in our functor, then turn it inside out with sequence that's the same as just placing it on the outside to begin with. We chose Right as our guinea pig as it is easy to try the law and inspect. An arbitrary functor there is normal, however, the use a concrete functor here, namely Identity in the law itself might raise some eyebrows. Remember a category is defined by morphisms between its objects that have associative composition and identity. When dealing with the category functors, natural transformations are the morphisms and Identity is, well identity. The Identity functor is as fundamental in demonstrating laws as our compose function. In fact, we should give up the ghost and follow suit with our Compose type:

Composition

comp1 = compose(sequence(Compose), map(Compose))
comp2 = lambda: compose(Compose, map(sequence()), sequence())
$ Test it out with some types we have lying around
comp1(Identity(Right([True])));
# Compose(Right([Identity(True)]))
comp2(Either, Array)(Identity(Right([true])))
# Compose(Right([Identity(true)]))

This law preserves composition as one would expect: if we swap compositions functors, we shouldn't see any surprises since the composition is a functor itself. We arbitrarily chose true, Right, Identity, and Array to test it out. Libraries like quickcheck can help us test the law by fuzz testing the inputs.

As a natural consequence the above law, we get the ability to fuse traversals, which is nice from a performance standpoint.

Naturality

natLaw1 = lambda nt: compose(nt, sequence))
natLaw2 = lambda nt: compose(sequence, map(nt))
# test with a random natural transformation and our friendly Identity/Right functors.
// maybe_to_either :: Maybe a -> Either () a
maybe_to_either = lambda x: Right(x.value) if x.value else Left()
natLaw1(Maybe, maybe_to_either)(Identity(Maybe('barlow one')))
# Right(Identity('barlow one'))
natLaw2(Either, maybe_to_either)(Identity(Maybe('barlow one')))
# Right(Identity('barlow one'))

This is similar to our identity law. If we first swing the types around then run a natural transformation on the outside, that should equal mapping a natural transformation, then flipping the types.

A natural consequence this law is:

traverse(A, A) == A;

Which, again, is nice from a performance standpoint.

In Summary

Traversable is a powerful interface that gives us the ability to rearrange our types with the ease a telekinetic interior decorator. We can achieve different effects with different orders as well as iron out those nasty type wrinkles that keep us from joining them down.