Arrows

Last time I wrote about replacing the monad in core.logic with an arrow and what that allowed you to do. So I’d better get around to explaining what arrows are.

Simply put, arrows are monoids in categories of bifunctors.

Someday, I’ll understand what that means. Until then, I’ll see if I can give a more practical explanation.

Some context

As I’ve dug into the various abstractions I’ve written about, a picture has started to form of how they’re all related. Way back in the beginning of this blog, I wrote about monads being containers of various kinds. The basic Clojure collections (list and variants, sets, hash-maps) along with functions, can be understood as containers for values.

Another idea, is that all functions have effects, the things the function does. The simplest effect is just accepting parameters and returning a single value as a result. Everything else you might conceive a function doing is a side-effect. By wrapping a value in a container, you can emulate all the various side-effects that are possible. So if you want a function that returns more than one result, you return a list of values. If you want multiple unique results, you return a set and so forth. If you want to emulate things like mutable state or IO, you wrap your values in functions that, when executed, emulate the side-effecting behavior. I think of wrapping values in containers as embedding them in a context. And these contexts are themselves just values.

Structure

In this diagram from my ClojureWest talk;

I show how some of these abstractions are related. If a box wholly contains another box, the inner box is said to “be an instance of” the outer one. What this means is that the abstraction in the inner box has more restrictions placed on it, so that if given an instance of the inner box, you can automatically and trivially create an instance of the enclosing box. In other words, the inner abstraction has more structure than the outer one.

With that understanding, if you have a monad, you also have an applicative functor and a functor. But you don’t automatically have a comonad.

From the diagram, you can see that every monad is also an arrow and that every comonad is as well. But there are arrows that are neither monads nor comonads. So arrows have less structure than (co)monads.

Types

While Clojure isn’t statically typed, it does have runtime type checking and thinking in types can help our understanding here.

As I’ve written previously, monads have a result function (which in Clojure is actually one of several functions depending on the monad; list, hash-set, vector, etc.) and a bind function. Comonads have an extract and extend function. Informally, these types look like this

;; monad
result: a -> <a>
bind: <a>, (a -> <a>) -> <a>

;; comonad
extract <a> -> a
extend: <a>, (<a> -> a) -> <a>

So result wraps any value in a context, which depends on the monad and extract pulls a value out of a context. And both bind and extend let you apply a function to value(s) in a context. And since they both return values in contexts, they are how you compose functions that work with such values. But there is a key difference between bind and extend.

In the monad, bind composes functions that accept any value and produce a value in a new context. The function has no access to any of the context its input value might have been wrapped in. On the other hand, it can create a totally new context to wrap the result value in.

For the comonad, extend composes functions that accept a value wrapped in a context and returns a value of any type that is not wrapped. This means that the function has complete access to the context and all the values it contains. But it is unable to modify that context. It can only return a value that the comonad will embed in the original context to produce the final context/value(s).

Having it all

But what if you want to compose functions that both accept and produce values in contexts? For that, you need arrows. But, you have to give up some structure to get that ability. And structure helps with notation, so arrows have a more cumbersome notation than either monads or comonads. So if one of those abstractions fit the bill, prefer them over arrows. With that said, let’s see how to work with the arrow abstraction.

Fun’s all the way down

The first thing to realize is that arrow values are always functions because arrows are all about composing functions. Part of the definition of (co)monads is a type that acts as a container for values. And like I said, there’s also the result/extract functions to get values in to or out of the container type. Arrows have a concept that’s kind of similar. The first thing you need for a basic arrow is a function that accepts a function as a parameter and returns a function of the arrow type.

arr: (x -> y) -> (<x> -> <y>)

The returned function will accept a value that’s already wrapped in a context and return a result that’s also wrapped in a context. There’s no requirement that the incoming context and the outgoing context are of the same type. It’s also possible that either the incoming or outgoing context (or both) is the non-existent context, or identity.

Sequential

So if all arrow values are functions, what is the most obvious way to compose said arrow values. In sequential order, of course.

seq: (<x> -> <y>), (<y> -> <z>) -> (<x> -> <z>)

This is the second part of an arrow definition. A combinator that allows you to compose two arrow values in order so the output of the first is used as input to the second. And it’s also where we start to see the ‘extra’ that arrows gives you. If these arrow values where just plain functions, the seq combinator would just be function composition. What arrows bring to the table is the fact that every arrow function also has some static meta-data associated with it. See, the only thing you can do with a function is call it. But if you add static meta-data, you can do all kinds of other things. So arrows are for composing functions that have meta-data associated with them.

Parallel

The third and final component of a basic arrow is a way to compose arrow values in parallel. But there’s a wrinkle. You could write a combinator that takes two arrow functions and produces one that will execute them in parallel. But what is the input to that composed function to be? A single value that you send down both paths? Or maybe a pair of values, one for each path? There’s actually a simpler combinator that will let you build parallel compositions.

nth: int, (<a> -> <b>) -> ([...<a>...] -> [...<b>...])

This combinator takes an integer value and an arrow value and returns an arrow value that operates on a sequence of values in contexts. This new arrow value extracts the nth value from incoming vector, applies the original arrow value to it, and inserts the result into the original vector at the nth position. With the nth combinator, you can build any variant of parallel arrow value composition you want.

And I know that seq and nth are already defined in clojure.core, but they can be namespaced qualified.

Summing up

This is already quite long, so I’ll leave off here. Next time I’ll look at how to create an arrow from a monad and the arrow I used in core.logic.

Jim Duey 07 October 2013
blog comments powered by Disqus