2014-09-03 real world one-liner examples.md

Real world one-liner examples

Recently I uploaded a new version of the one-liner package. The goal with the new version was to make writing generic functions as simple and unscary as I could. To do this I had to sacrifice some power, so I wanted to check it would still be useful for a lot of real world cases. To do this, I searched Google for uses of GHC.Generics on Hackage.

Data.Binary

The first example is one I already used in the previous blogpost: put and get from the binary package. With the new version of one-liner, the code for a generic put looks like this:

gput :: (ADT t, Constraints t Binary) => t -> Put
gput t = putWord8 (toEnum (ctorIndex t)) <> gfoldMap (For :: For Binary) put t

Put is a Monoid (with mempty = return () and (<>) = (>>)), so we can use gfoldMap.

gfoldMap :: (ADT t, Constraints t c, Monoid m)
         => for c -> (forall s. c s => s -> m) -> t -> m

We pass the proxy For Binary to tell gfoldMap what class we want to use, and then we need a function of type forall s. Binary s => s -> Put, which is simply put. But before that we need to store a byte containing the index of the constructor, so we'll know what to do when we get:

gget :: (ADT t, Constraints t Binary) => Get t
gget = getWord8 >>= \ix -> createA (For :: For Binary) get !! fromEnum ix

Get is Applicative, which allows us to use createA:

createA :: (ADT t, Constraints t c, Applicative f)
        => for c -> (forall s. c s => f s) -> [f t]

createA (For :: For Binary) get returns a list of ways to read binary data, one for each constructor, and we pick the right one using the index that we stored first.

Data.Hashable

The next example is hashWithSalt from the hashable. Its type is Int -> a -> Int, which at first sight doesn't look like something one-liner can handle. However, if we flip it we get a -> Int -> Int, and Int -> Int is a monoid if we wrap it in Endo. Now we can use gfoldMap again.

ghashWithSalt :: (ADT t, Constraints t Hashable) => Int -> t -> Int
ghashWithSalt = flip $ \t -> flip hashWithSalt (ctorIndex t) .
  appEndo (gfoldMap (For :: For Hashable) (Endo . flip hashWithSalt) t)

As the documentation explains we should first hash the constructor index and then hash all the subcomponents, while effectively composing all the Int -> Int functions along the way.

Control.DeepSeq.Generics

The next example is going to be a walk in the park, it is rnf from the deepseq-generics package. () is a monoid, therefore gfoldMap again is what we use:

grnf :: (ADT t, Constraints t NFData) => t -> ()
grnf = gfoldMap (For :: For NFData) rnf

One minor detail, this requires the Monoid instance of () to be strict. Sadly it isn't, the person who implemented it even left a comment, wondering “Should it be strict?” Now we must create our own strict unit type, and convert between that and (). I'll skip that here.

The real world can be annoying sometimes!

GHC.Generics.Lens

The first result on Google was the tinplate function from the lens package. Straight away this was a non-standard use of GHC.Generics, because it does a deep traversal, i.e. all the immediate subcomponents also need to be an instance of Generic.

It was possible to do this without changing the library, but it was quite tricky and it required a hack to prevent GHC from detecting a class declaration cycle. Also there's the problem that the GHC Generics representation of atomic types like Char and Int contain themselves. To make this use case easier for the user, I added a utility constraint Deep to the library that calculates the constraints needed for all the deep components of a datatype to be an instance of the given class, and a utility function isAtom to test if the given type is atomic or not.

With that in place, I needed only one more utility function, which casts a function of type b -> f b to a function of type a -> f a, if it can be determined through the Typable class that b and a are actually the same. In that case, eqT returns Just Refl, with Refl being of type a :~: a, which lets the compiler know that a and b are the same type when you pattern match on it.

whenCastableOrElse :: forall a b f. (Typeable a, Typeable b)
                   => (b -> f b) -> (a -> f a) -> a -> f a
f `whenCastableOrElse` g = maybe g (\Refl -> f) (eqT :: Maybe (a :~: b))

With these utility functions tinplate can be rather cleanly implemented using gtraverse:

tinplate :: forall t b. (Typeable b, Deep Typeable t) => Traversal' t b
tinplate f
  | isAtom (Proxy :: Proxy t) = f `whenCastableOrElse` pure
  | otherwise = gtraverse (For :: For (Deep Typeable)) $
                   f `whenCastableOrElse` tinplate f

gtraverse is a generalisation of traverse, and gfoldMap can be implemented with it using Const, just like foldMap can be implemented with traverse.

gtraverse :: (ADT t, Constraints t c, Applicative f)
          => for c -> (forall s. c s => s -> f s) -> t -> f t

Test.SmallCheck.Series

The last examples are series and coseries from the smallcheck package.

Series m is Applicative so it may seem we could use createA directly. However the documentation of SmallCheck makes it clear we're not supposed to use <*>, but instead use <~> to get fair, breadth-first generation of values. This is easily fixed by creating a newtype wrapper to get a fair Applicative. Then we can call createA, and fold the ways to produce series with (\/).

newtype Fair m a = Fair { runFair :: Series m a } deriving Functor
instance MonadLogic m => Applicative (Fair m) where
  pure a = Fair $ pure a
  Fair fs <*> Fair as = Fair $ fs <~> as

gseries :: forall t m. (ADT t, Constraints t (Serial m), MonadLogic m) => Series m t
gseries = foldr ((\/) . decDepth . runFair) mzero $ createA (For :: For (Serial m)) (Fair series)

coseries was the most interesting of all the generic functions I found on Hackage. Its type is:

coseries :: Series m b -> Series m (a -> b)

To implement coseries generically we'll wrap that type in a newtype wrapper:

newtype CoSeries m a = CoSeries { runCoSeries :: forall r. Series m r -> Series m (a -> r) }

Is Coseries m Applicative? No, it can't be because it is actually contravariant:

instance Contravariant (CoSeries m) where
  contramap f (CoSeries g) = CoSeries $ fmap (. f) . g

I hadn't thought of contravariant functors yet, they are not (yet) used much in Haskell. No function in one-liner could deal with them.

Coincidentally just a few weeks earlier Edward Kmett figured out a way to do Applicative contravariantly, using a thing called Day convolution. CoSeries m turns out to be an instance, with the implementation of divide largely following the implementation of the Smallcheck function alts2.

instance MonadLogic m => Divisible (CoSeries m) where
  divide f (CoSeries g) (CoSeries h) = CoSeries $ \rs -> do
    rs' <- fixDepth rs
    f2 <- decDepthChecked (constM $ constM rs') (g $ h rs')
    return $ uncurry f2 . f
  conquer = CoSeries constM

My first attempt was then to go on to mirror createA, and make a function that returns a list of ways to consume a type, one for each constructor. But that doesn't work because when you consume a value, you don't know which constructor you're going to get, so we need a special way to combine these ways to consume a value such that the right way is called depending on the constructor of the value that is being consumed.

For that we only need to look a bit further down the documentation of Divisible and there we find Decidable which is a contravariant version of Alternative, and this precisely fits our needs! Then the generic function that consumes values becomes:

consume :: (ADT t, Constraints t c, Decidable f)
        => for c -> (forall s. c s => f s) -> f t

Is CoSeries m Decidable? Yes it is!

instance MonadLogic m => Decidable (CoSeries m) where
  choose f (CoSeries g) (CoSeries h) = CoSeries $ \rs ->
    (\br cr -> either br cr . f) <$> g rs <~> h rs
  lose f = CoSeries $ \_ ->
    return $ absurd . f

After all this, implementing coseries becomes straightforward:

gcoseries :: forall t m r. (ADT t, Constraints t (CoSerial m), MonadLogic m)
          => Series m r -> Series m (t -> r)
gcoseries = runCoSeries $ consume (For :: For (CoSerial m)) (CoSeries coseries)

Edit: If you want to see another contravariant example, I also implemented QuickChecks coarbitrary.

By the way, working with contravariant functors really made my head hurt. I would not have been able to implement this if I wouldn't have been able to mostly just follow the types everywhere.

What doesn't work?

There are 3 uses of generics that I can think of which don't work with one-liner:

• Code that uses meta data. For example aeson needs record field names to generate JavaScript property names.
• Code that does calculations on types. For example deriving zippers needs to calculate the derivative of a type.
• Code that needs non-trivial return types. An example here is deriving lenses, which if you do it generically returns a list of HLists, with a lens to each field of each constructor.

Conclusion

Looking for practical uses of generics turned out to be very useful. As I had hoped, most generic functions that did not fit in one of the 3 categories above, were implementable with one-liner, and the few ones that didn't provide useful new additions to the library.

You can add comments to this article on reddit.