If you take a look at the archives, you’ll see that I started this blog explaining monads. Monads have the most buzz in functional programming circles, but there are plenty of other abstractions that are just as useful in their own ways. If I was starting this blog today, this is the first post I would write rather than just jumping straight to monads.

Every programming language I’m aware of has a set of primitive data types; functions, integers, floats, strings, etc. And you start learning a language by figuring out what you can do with the primitive types. But very quickly, you move to working with collections of these primitive types. Lists, arrays, sets and hash maps are examples of collection types you’ll find.

So given a collection of values, there are a couple of obvious things you can do with them. One is to take two collections of the same type and combine them together. In category theory, a collection type along with a function to combine two collections and a special collection value is called a monoid. That special collection value is such that when it is combined with any other collection value, the result is the other collection value unchanged. I’ll come back to monoids in the future, but I’ll note that they show up in the `clojure.core.reducers`

namespace.

Another obvious operation on a collection is to transform a collection by applying a function to every item in that collection, producing a new collection of the results. This operation is commonly referred to as ‘mapping’. So a functor is a collection type (list, tree, etc.) and a function (typically called `fmap`

) that knows how to apply a function to every item in the collection. This type of abstraction over collections is already part of Clojure in at least two ways. First is `conj`

which does the right thing when you want to add a value to various collection types. And also `map`

in clojure.core, which does exactly what `fmap`

of a functor does in the case of any collection that is seqable. One issue with Clojure’s `map`

is that it always returns a list, where `fmap`

is defined to always return a collection of the same type as the original collection. I’ve created a minimal functor library for Clojure here. It just defines a protocol with an `fmap`

function and gives a couple of simple example implementations. Because of the way Clojure’s protocols work, I switched the order of the parameters to `fmap`

as compared to Clojure’s `map`

function. Since functors are so general and Clojure already has `map`

and `clojure.core.reducers/map`

, I don’t intend to add to the functors library unless I come across some collection types that aren’t easily handled by the tools Clojure already provides.

To properly be called a functor, the `fmap`

function must also obey certain laws:

```
(fmap coll identity) <=> coll
(fmap coll (comp g h)) <=> (fmap (fmap coll h) g)
```

The first expression can be interpreted to say that, for any functor, mapping the identity function over a collection just returns the collection itself.

The second expression can be interpreted to say that mapping a function ‘h’ over a collection and then mapping another function ‘g’ over the resulting collection is equivalent to composing ‘h’ and ‘g’ and then mapping that function over the original collection.

Functors are so general, that there’s not much use for a functor library in Clojure. But things get a little more interesting when you start looking at a subset of functors called applicative functors. Applicatives have a few more requirements put on them than functors and as a result are more useful. I’ve created an applicative library here.

Since applicatives are functors, they have a collection type and an `fmap`

function that follows the functor laws. But they also have a couple of other functions that must be defined; `pure`

and what I call `map`

(in Haskell land named `<*>`

). The applicative `map`

can be distinguished from `clojure.core.map`

by requiring the applicative namespace under an alias.

The `pure`

function takes any value and puts it into the collection type. In Clojure, you can view `list`

, `vector`

and `hash-set`

as implementations of `pure`

. Since Clojure doesn’t have a type system like Haskell’s with its type inferencing, it’s not really possible to define a protocol containing a `pure`

function, so I just extended the various collection types to implement a protocol that defines a `map`

function. For new collection types that aren’t extension of Clojure’s collections, the type constructor will serve as the `pure`

function.

The `map`

function of the applicative takes a collection like `fmap`

does. Where it differs is in the other parameter is accepts. Instead of a simple function, applicative’s `map`

takes a collection of functions that are contained in the collection type of the applicative. For example:

```
(require [net.clojure.applicative :as a])
(a/map [fn1 fn2 fn3] [1 2 3 4])
```

In this case, the collection type is a vector and the result of the call to a/map would be a vector of the results returned by applying every function fn1, fn2 and fn3, to every value 1 2 3 4. So it would be a vector of 12 results. Notice that the order of args is different than that of `fmap`

in that the list of functions comes first and then the parameters. This is again because of the way Clojure’s protocols work. They dispatch to the correct protocol function according to the type of the first parameter. With `fmap`

, the first parameter couldn’t be the function, because the proper implementation of `fmap`

couldn’t be selected. So the collection had to be first. In the case of `a/map`

, the collection holding the functions to apply can be first and select the proper implementation to execute.

So why not just keep the same order as `fmap`

? Aside from being the same parameter ordering as `clojure.core/map`

, there’s also another reason. `fmap`

only allows a function that accepts a single argument to be mapped over the collection. `a/map`

will allow functions of any number of args to be mapped over a matching number of collections. So, for example:

```
(a/map (list +) [1 2 3] [1 2 3])
=> (2 3 4 3 4 5 4 5 6)
```

But you’re not limited to a list with a single function in it:

```
(a/map (list + vector) [1 2] [1 2])
=> (2 3 3 4 [1 1] [1 2] [2 1] [2 2])
```

And that leads to an interesting observation. There’s actually another valid way of interpreting two (or more) lists of parameters and that is with pairwise matching like the behavior of `clojure.core/map`

when given multiple lists.

```
(map vector [1 2 3] [:a :b :c])
=> ([1 :a] [2 :b] [3 :c])
```

To account for this, I added a deftype to applicative called ZipWith along with a helper function called `zipwith`

which takes either a single value or a sequence. If it’s given a sequence (vector, list or lazy seq), it just wraps it in the ZipWith type. But if you give it a single value, it wraps an infinite, lazy sequence of that value. And then the implementation of `map`

combines all the sequences pairwise and hands that list off to `r/map`

to apply them in parallel. This is one way to address Rich’s comment in this blog post about needing a way to pass multiple lists to `r/map`

.

Here it is in action:

```
@(a/map (zipwith +) [1 2 3] (range 2000))
=> (1 3 5)
```

The dereference is necessary to unwrap the ZipWith collection returned from a/map. Also notice that only 3 results were returned because that was the length of the shortest sequence given as a parameter.

That’s enough for one blog post. Next time, I intend to explore some reasons to use applicatives and their relation to monads.

Jim Duey 19 January 2013