status
failed

Haskell's strength: generalising with lenses

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:

strength :: Functor f => (a, f b) -> f (a, b)
strength (a, fb) = fmap (\b -> (a, b)) fb

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.

So what?

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, map, and reduce. Haskell types for these functions might look like this:

mrMap :: ka -> va -> [(kb, vb)]
mrReduce :: kb -> [vb] -> [output]

where 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

mrReduce' :: kb -> [vb] -> [(kb, vb)]
mrReduce' k vs = map (\v -> (k, v)) vs

But it’s already looking very familiar. We can write that in terms of strength like this:

mrReduce :: kb -> [vb] -> [(kb, vb)]
mrReduce k vs = strength (k, vs)

-- Or even more simply...
mrReducePF = curry strength

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:

{
  "foo": 3,
  "bar": 1,
  "baz": 4
}

And we want to end up with something like this:

result :: [(Text, Int)]
result = [("foo", 3), ("bar", 1), ("baz", 4)]

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:

parsePair :: FromJSON v => (Text, Value) -> Parser (Text, v)
parsePair = strength . over _2 parseJSON

Now we can simply apply it to each of the object’s properties and combine the monadic results using mapM:

parseKVP :: FromJSON v => Value -> Parser [(Text, v)]
parseKVP (Object ps) = mapM parsePair $ toList ps
parseKVP _ = mzero

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 Value to Parser v.

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.

strength' :: Functor f => (a, f b) -> f (a, b)
strength' x = fmap (g x) (f x)
  where f x = snd x
        g x = \b -> (fst x, b)

Note how it’s of the form fmap (g x) (f x), where:

  • f x extracts the functor from the record
  • g x is a function putting values of type b into 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:

strength'' :: Functor f => (a, f b) -> f (a, b)
strength'' x = fmap (g x) (f x)
  where f = view _2
        g x = \b -> set _2 b x

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!)

strong :: Functor f => Lens s t (f a) a -> s -> f t
strong l x = fmap (set l ?? x) (view l x)

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:

strong _1 (Just "hi", 1) == Just ("hi", 1)
strong _2 ("key", [1..3]) == [("key", 1), ("key", 2), "key", 3)]

data KVP k v = KVP
  { _key :: k
  , _val :: v
  }
makeLenses ''KVP

strong val (KVP "key" [1..3]) == [KVP { _key = "Hi", _val = 1 } ... ]

Pretty cool!

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:

type Lens s t a b = Functor f => (a -> f b) -> s -> f t

If we replace these types with those from our earlier definition of strong, we find that

Lens s t (f a) a == Functor f => (f a -> f a) -> s -> f t

Which means that given a lens of this type, we can apply it to the identity function, and obtain the very same function:

strong' :: Lens s t (f a) a -> s -> f t
strong' l = l id

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 f.

Paul
—