This post is about the
strength function, Lenses, and strong functors. Specifically, it’s about how we can generalise
strength using lenses to work on any product type, not just tuples.
If you like, you can skip straight to the good bit where we derive a generalised strength.
For our purposes,
strength is a function which “everts” a tuple containing some functor,
(a, f b), turning it inside out to result in a functor of a tuple
f (a, b). We can write this function as follows:
Note that the choice of
f b being the second item in the tuple is fairly arbitrary, and we could just as easily have put it as the first. Our choice is important to make code cleaner later in the article.
In Category Theory, a functor allowing this operation is said to be strong. A more formal definition of a strong functors can be found in Edward Kmett’s excellent article “Deriving strength from laziness”, which also notes that all Haskell
Functors are strong.
This might seem a bit pointless, but turns out to be useful in a number of cases. For example, take MapReduce. a MapReduce program defines two functions,
reduce. Haskell types for these functions might look like this:
ka denotes “key type a”, equivalent to
in_key from the MapReduce slides, and “vb” denotes “value b”, equivalent to
intermediate_value. Let’s suppose we want to write the “identity” reduce function. That is, a function which yields the output of the
mrMap function unchanged.
One such implementation is simply
But it’s already looking very familiar. We can write that in terms of
strength like this:
Another example: JSON objects to key/value pairs
In case you’re not particularly convinced, here’s another example.
Let’s say we’re dealing with a JSON object, and we want to parse it into a list of keys and values. An example object might look like this:
And we want to end up with something like this:
We’ll use the excellent
Data.Aeson library, which provides a function
parseJSON :: FromJSON a => Value -> Parser a which we can use to encode and decode to and from text.
We can use this, combined with
strength, to convert an Object- a
HashMap Text Value- into a list of key/value pairs.
First, we’ll tackle converting a single key/value pair:
Now we can simply apply it to each of the object’s properties and combine the monadic results using mapM:
What if it’s not a pair?
We’ve seen that our examples worked out particularly well for us, but only because we picked an implementation of strength matching our use-cases. How would we deal with nested Functors as the first item? For that matter, what about 3- and 4-tuples? In fact, what about records?
What we want is to be able to use
strength on any product type, including records, with some easy way to specify which field is the functor we want to evert.
Lenses to the rescue
Fortunately, the lens package is here to help. This gives us a nice way of passing around getters and setters, and crucially lets us do polymorphic updates. That means that when modifying a field, we can also change its type (and therefore also the type of the ‘parent’ record). We’ve seen this already in the definition of
parsePair, where the second item in a tuple was modified “in place”, while changing its type from
The essence of strength
Clearly, our new function won’t be able to use pattern matching. We’ll rewrite the original function without pattern matching first.
Note how it’s of the form
fmap (g x) (f x), where:
f xextracts the functor from the record
g xis a function putting values of type
binto a tuple
We can look at f and g as getters and setters of sorts, which is exactly what lenses do best. Now we can rewrite it like this:
The good bit
From here it’s pretty clear how to proceed: we just need to replace the hard-coded lens with one passed in as an argument. Note that you’ll need the RankNTypes extension for this to work (i’m not sure why!)
Note we’ve replaced the lambda expression using
??, an infix version of
flip which you can read as a placeholder for a missing argument.
Finally, to explain the type signature. The type
Lens s t a b can be read as “A lens into a record of type
s to a field of type ‘a’. The field can be modified to be of type ‘b’, resulting in a record of type ‘t’.”
What we’ve specified is a
Lens s t (f a) a, which is a lens on a record
s, containing a field of type
f a. The “target” record is of type
t, and has a field of type
a- the type of elements of the functor. Our
strong function now returns an
f t, the wrapped record.
Finally, some examples of usage:
Further down the rabbit hole
This isn’t the end of the story, however. If we examine the type of
strong more closely, we find something interesting. The
Lens type is defined thusly:
If we replace these types with those from our earlier definition of
strong, we find that
Which means that given a lens of this type, we can apply it to the identity function, and obtain the very same function:
As it turns out, this function is already in Control.Lens, as the
sequenceAOf function, which goes even further to work on
LensLike lenses which don’t even require the Functor constraint for