Pieces of Yesod: Inverting a Haskell Function

I’ve recently been working with web frameworks, and decided to have a play with what Haskell has to offer for web resources. One of the several frameworks available is Yesod. Web frameworks need some sort of mapping between URLs and internal logic, usually called routing. In Yesod, routing is done with a “pieces” mechanism. You might declare in your routes:

/resources/#SortBy ResourcesR GET

And this will mean that if you access example.com/resources/d, that will translate into a call that turns the string "d" into a value of type SortBy, which is then passed to getResourcesR. It also means that if you use the syntax “@{ResourceR Date}” in your template files, this will be translated into example.com/resources/d. This translation is done is with the “pieces” classes, for example the single piece class:

class SinglePiece a where
  fromSinglePiece :: Text -> Maybe a
  toSinglePiece :: a -> Text

So a value should always be translatable into a part of a URL (i.e. Text), and an arbitrary URL part may be a valid value. Here’s a simple sorting-order type:

data SortBy = Date | Popularity | Title

And here’s the trivial SinglePiece instance:

instance SinglePiece SortBy where
  fromSinglePiece "d" = Just Date
  fromSinglePiece "p" = Just Popularity
  fromSinglePiece "t" = Just Title
  fromSinglePiece _ = Nothing

  toSinglePiece Date = "d"
  toSinglePiece Popularity = "p"
  toSinglePiece Title = "t"

There’s several drawbacks with this code. The major drawback is obvious: the code is repetitive! It expresses the same simple mapping from sort order to text twice, once in each direction. This is tedious. Another drawback is that is a potential source of bugs if I make a typo. SinglePiece does have an obvious property for testing: fromSinglePiece . toSinglePiece == Just. I also need to make sure I cover all the possible sorting values. The nice thing about toSinglePiece (rather than using a lookup table) is that if I use the GHC flags -fwarn-incomplete-patterns -Werror, it will warn me if I miss out a case. So if I add a new sort order, say Author, and forget to change toSinglePiece, I’ll get a compile-time error as soon as I try to compile (which is quicker even than a test). But fromSinglePiece doesn’t have the same advantage: if I forget a new case for Author, I’ll only know about it because of my test.

The way to fix my problems is to stop repeating myself. I can change the code to this:

instance SinglePiece SortBy where
  fromSinglePiece = invert toSinglePiece
  toSinglePiece Date = "d"
  toSinglePiece Popularity = "p"
  toSinglePiece Title = "t"

That invert function looks a bit magical! Broadly, its type is:

invert :: (a -> b) -> (b -> Maybe a)

Now, as it stands, the invert function is not implementable; there’s no way to arbitrarily invert a Haskell function. But we can brute force an inversion if we know the full range of inputs. That’s possible with the help of some automatically derivable Haskell type-classes:

data SortBy = Date | Popularity | Title
  deriving (Eq, Enum, Bounded)

invert :: (Enum a, Bounded a, Eq b) => (a -> b) -> (b -> Maybe a)
invert f = flip lookup $ map (f &&& id) [minBound..maxBound]

We use Enum and Bounded to get the list of all possible inputs, then form a lookup table which we can reference to find the inverse of a value. So now we’re able to write just toSinglePiece, and automatically derive fromSinglePiece. No repetition and less possible source of mistakes. The only problem is that invert might be a bit slow. Instinctively, it feels like the lookup table can’t be as fast as Haskell’s built-in case structure. To find out, let’s whip up a test using the Criterion benchmarking library.

I’m testing the performance of fromSinglePiece on the three valid URLs and one invalid, i.e.

main = defaultMain
  [bench "benchName" $ nf (map fromSinglePiece :: [Text] -> [Maybe SortBy])
     ["d", "p", "t", "x"]]

I ran this once on the original fromSinglePiece that used a case statement (calling that “cases”), and once on the new fromSinglePiece that uses the lookup table (calling that “invert”), compiling with -O2 each time on GHC 7.0.3. Here’s the results:

benchmarking cases
collecting 100 samples, 23951 iterations each, in estimated 1.011024 s
bootstrapping with 100000 resamples
mean: 423.0417 ns, lb 421.8167 ns, ub 426.2270 ns, ci 0.950
std dev: 9.136906 ns, lb 1.879618 ns, ub 16.88352 ns, ci 0.950
found 2 outliers among 100 samples (2.0%)
  2 (2.0%) high severe
variance introduced by outliers: 0.997%
variance is unaffected by outliers

benchmarking invert
collecting 100 samples, 21664 iterations each, in estimated 1.011000 s
bootstrapping with 100000 resamples
mean: 466.8043 ns, lb 466.7298 ns, ub 466.9089 ns, ci 0.950
std dev: 448.0250 ps, lb 340.4309 ps, ub 723.9564 ps, ci 0.950
found 2 outliers among 100 samples (2.0%)
  1 (1.0%) high severe
variance introduced by outliers: 0.990%
variance is unaffected by outliers

So the difference in speed is only around 10%. I can accept that cost in order to not repeat myself everywhere. Obviously, many types used with SinglePiece are not a trivial conversion between a type constructor and a text value, but for those that are, I found this trick useful.