Duck-typing with GHC Generics

If you come to Haskell from a more run-of-the-mill programming background, some of the terminology can be downright obscure and cryptic. One piece of the Haskell (or specifically GHC) land-scape that is more confusing than cryptic is the GHC Generics system. Here I'm going to go through what this is, why you might want to use it, and how it can let you do things that would otherwise appear impossible within the constraints of the Haskell type system.

Generics /= Parametric Polymorphism

Unfortunately, the term 'Generics' is rather overloaded in the software development community. Starting with Java, the term has spread to many language communities (including perhaps the most influential and widespread type system in use today, TypeScript) with the meaning of 'parametric polymorphism', i.e. the ability to construct types that have one or more type parameters, and are thus generic in the sense that one structure can be inhabited by many different types. Examples of this ubiquitious in Haskell, including all the common suspects such as [a], Maybe a, Tree a, Map k v, (a,b) and even IO a.

So given these two types:

data A = A Int Bool Char
data B a b c = B a b c

A is monomorphic, i.e. it has only one inhabitant, and B is polymorphic, and can be inhabited by all kinds of different things, such as B Word Word Word, B String (Set Int) (IO ()) etc, even B Int Bool Char, which is isomorphic to A. We can also say that A is of kind * and B is of kind * -> * -> * ->
*.

But even though A and B Int Bool Char have the same shape (1 constructor, 3 positional fields) and each of the their fields has the same shape, they are distinct types, and we cannot directly write a single function that can, say, extract the second position field as a Bool from either an A or a B Int Bool Char, not to mention a B a Int b, without writing some kind of type class.

Compare this with dynamically typed languages like Python, or Clojure, where it is straightforward to write such functions, that manipulate objects in terms of their structure, not their names:

def foo(x):
  print x.foo

(defn foo [x]
  (print (:foo x)))

This different approach to data-types, so called Structural typing, as opposed to nominal typing, is often referred to as Duck Typing, as in if it quacks like a duck, and looks like a duck, then to all intents and purposes, it is a duck. In structural typing terms, if it has a field of that name, and that field has that type, then as far as we are concerned, we can treat it as the same kind of thing (as though there was a HasFoo class).

GHC generics allow us to consider data in terms not of its names, but its shapes. And so we will see how we can go about bringing a python-like object system to Haskell.

What is an object, anyway?

That all requires some sense of what an object is. A python object is really just a mapping from names to fields, which are all dynamically typed. So that is what our objects will be too.

import qualified  Data.Map.Strict as Map

type Map = Map.Map

data Object = Object
  { objectMeta             :: Map String String
  , objectNamedFields      :: Map String Dynamic
  , objectPositionalFields :: [Dynamic]
  }
  deriving (Show, Typeable)

In addition to the named fields, we will also store special meta-data about the object, such as its type and its constructor. Fields either have names (as in records) or they are placed positionally.

We want to then extract fields and meta-data of course, so we need to say how to get fields out:

data Key a = Named String | Positional Int
  deriving (Show, Eq)

get :: Typeable a => Key a -> Object -> Maybe a
get (Named s) = getField s
get (Positional i) = getFieldAt i

getField :: Typeable a => String -> Object -> Maybe a
getField k (Object _ fs _) = Map.lookup k fs >>= fromDynamic

getFieldAt :: Typeable a => Int -> Object -> Maybe a
getFieldAt k (Object _ _ fs) = listToMaybe (drop k fs) >>= fromDynamic

getType :: Object -> Maybe String
getType (Object m _ _) = Map.lookup "__type" m

mkObject :: Typeable a => String -> a -> Object
mkObject k v = Object mempty (Map.singleton k (toDyn v)) []

This lets us fetch individual fields, where the user specifies the name and implicitly requires it to be of a specific type. We return it if we can.

Lets take these objects out for a spin:

let os = [mkObject "foo" 'a'
         ,mkObject "foo" (10 :: Int)
         ,mkObject "foo" 'b'
         ,mkObject "bar" 'c'
         ]
mapM_ print . catMaybes $ fmap (get (Named "foo" :: Key Char)) os
> 'a'
> 'b'

Notice we have to tell the compiler what we are expecting back, and we can do that by annotating the keys. We can even have a function like the useful get-in from clojure that walks a chain of fields to find the thing we want at the end:

getIn :: Typeable a => Key a -> [Key Object] -> Object -> Maybe a
getIn k ks o = foldr (\k mo -> mo >>= get k) (pure o) (reverse ks) >>= get k

Which works as follows:

let o = mkObject "a" (mkObject "b" (mkObject "c" (mkObject "d" True)))
print $ getIn (Named "d" :: Key Bool) [Named "a", Named "b", Named "c"] o
> Just True

Well that isn't very useful (yet)

So far all we have is a wonky map-based obejct system. It would be neither ergonomic nor practical to do any real programming using the Object type. Instead, we will want to use normal Haskell ADTs, and be able to transform them into Objects to be queried structurally.

This is where Generics come in handy. They are based on the observation that the algebra of Alegbraic Data Types means that we can identify a minimal subset of shapes we can use to represent all data types:

• V1 - this is the data type without constructors. There aren't lots of these, but some examples include Void, and the phantom data types used as tags in some systems.
• U1 - this is the value without any fields. This includes common things like True and False as well as enumerations like data XS = A | B | C. In this case the value being represented is True or A.
• a :+: b is where there is a choice of two constructors. This includes things like Bool = True | False, or data Tree a = Tip | Branch (Tree a) (Tree a) or data Either a b = Left a | Right b. In this case the value being represented is a Bool, or Either an a or a b, not the side itself. Where there are more than two options, the expressions nest, as (a :+: b :+: c :+: ...) and so on.
• a :*: b represents the combination of two things. This happens all the time when a value has more than one field, either named or positional. In data Foo = F Int Char Word there are three fields, and all are present, so this might be come as (int :*: (char :*: word)). The simplest example is (a,b), which is just that, at combination of two things.
• K1 represents a leaf value itself.
• M1 holds the meta-data This includes data-type name, constructor names, and field names. Rather than repeating this in several places, this is unified into one representation.

Our job then is to use the GHC Generics machinery to turn normal Haskell ADTs into these Generic data-types, and then transform these into Objects. Since all these six things are distinct types, we need a type-class to dispatch over them:

From Rep to Object

The normal pattern is to have two type classes, one for the normal Haskell ADTs, and one for the structural representation. We will call the two classes here ToObject and ToObject'

class ToObject a where
  object :: a -> Object
  default object :: (Generic a, ToObject' (Rep a)) => a -> Object
  object x = toObject (from x)

In the outer wrapper class, we allow types to specify a custom instance, but then say, well, if you can transform yourself into one of those types up above, then I can handle you myself, in a uniform, generic manner.

This implementation lives in Generic land, where every constructor has a phantom parameter, so we expect all the types in this class to be of kind * -> *. This means the structural type-class is:

class ToObject' f where
  toObject :: f p -> Object

Then we need to handle each of the six possible representations. The first few are entirely straightforward:

instance ToObject' V1 where
  toObject x = error "impossible"

For the uninhabited type, we will never be passed any instances, since they can never be constructed. We can just error out here.

instance ToObject' U1 where
  toObject U1 = Object Map.empty Map.empty []

For empty values, return an empty object.

instance ( ToObject' lhs , ToObject' rhs) => ToObject' (lhs :+: rhs) where
           toObject (L1 lhs) = toObject lhs
           toObject (R1 rhs) = toObject rhs

If we have a LHS, then handle that, otherwise handle the RHS.

instance ( ToObject' lhs
         , ToObject' rhs) => ToObject' (lhs :*: rhs) where
           toObject (lhs :*: rhs) = toObject lhs <> toObject rhs

If we have both a RHS and a LHS, then combine them in some way. To do this, it is helpful to define a Semigroup instance for our objects:

instance Semigroup Object where
  (Object m1 a fs) <> (Object m2 b fs') = Object (m1 <> m2) (a <> b) (fs <> fs')

Where it gets interesting is when we get down to values and names, so K1 and M1. For K1 we know the value, but we don't know its name, if it has one, so we will package it up into an object under a special key which is not a legal Haskell identifier, so we can detect it later. Also we want to be careful to distinguish between values like 10 :: Int, 'a' :: Char, which we want to stick in the object directly as as leaf, and ADTs like Tree a, which we want to decompose further if possible. So we will introduce a new type class here to dispatch between primitive and composite values:

class ToValue a where
  toVal :: a -> Dynamic

  default toVal :: (ToObject a) => a -> Dynamic
  toVal x = toDyn $ object x

instance (ToValue x) => ToObject' (K1 i x) where
  toObject (K1 x) = Object Map.empty (Map.singleton "$value" (toVal x)) []

Now when we get to the M1 nodes, we need to handle them differently based on whether they hold constructor, datatype or selector (field) names. Constructor and Datatype are simple - extract the names and tag the objects:

metaCon, metaType :: String
metaCon  = "tag"
metaType = "type"

instance (Constructor t, ToObject' f) => ToObject' (M1 C t f) where
  toObject m =
    let o = toObject (unM1 m)
     in o { objectMeta = Map.insert metaCon (conName m) (objectMeta o) }

instance (Datatype t, ToObject' f) => ToObject' (M1 D t f) where
  toObject m =
    let o = toObject (unM1 m)
     in o { objectMeta = Map.insert metaType (datatypeName m) (objectMeta o) }

When we get a selector, we need to behave slightly differently depending whether we get a leaf node (a value) or another kind of object and depending on whether the selector has a name (is a record field) or is empty (is positional):

instance (Selector t, ToObject' f) => ToObject' (M1 S t f) where
  toObject m =
    let val = toObject (unM1 m)
     in case Map.toList (objectNamedFields val) of
         [("$value", v)] -> case selName m of
                               [] -> val { objectNamedFields = mempty
                                         , objectPositionalFields = [v]
                                         }
                               k -> val { objectNamedFields = Map.singleton k v }
         _ -> case selName m of
                [] -> Object mempty mempty [toDyn val]
                k  -> Object mempty (Map.singleton k (toDyn val)) []

Putting this into action

So now we need some ADTs to use this with, for example:

data Foo = Foo { fooA :: Int, fooB :: Bool, fooC :: String }
  deriving (Show, Eq, Generic)

data Bar = Bar Double Int deriving (Show, Eq, Generic)

data WhatIDid = Veni | Vidi | Vici deriving (Show, Eq, Generic)

data Nested = N { nInt :: Int, nFoo :: Foo, nBar :: Bar }
  deriving (Show, Eq, Generic)

data Tree a = Tip | Branch { treeNode :: a, treeLHS :: (Tree a), treeRHS :: (Tree a) }
  deriving (Show, Eq, Generic)

For everything we want to handle structurally, we need to opt in to the ToObject and ToValue classes. Thankfully the implementations are not onerous, but they are a bit boilerplatey:

instance ToValue Int where toVal = toDyn
instance ToValue Double where toVal = toDyn
instance (Typeable a) => ToValue [a] where toVal = toDyn
instance ToValue Bool where toVal = toDyn
instance ToValue Char where toVal = toDyn

instance ToValue Foo
instance ToObject Foo

instance ToValue Bar
instance ToObject Bar

instance ToValue WhatIDid
instance ToObject WhatIDid

instance ToValue Nested
instance ToObject Nested

instance (Typeable a, ToValue a) => ToValue (Tree a)
instance (Typeable a, ToValue a) => ToObject (Tree a)

And we can give it a whirl:

let t_char = Branch 'a' Tip
                        (Branch 'b' (Branch 'e' Tip Tip)
                                    (Branch 'd' Tip Tip))
getIn (Named "treeNode" :: Key Char) [Named "treeRHS", Named "treeLHS"]
      (object t_char)
> Just 'e'

let t_bar = Branch (Bar 1.0 1)
                   Tip
                   (Branch (Bar 2.0 2)
                           (Branch (Bar pi 0) Tip Tip)
                           (Branch (Bar 42 3) Tip Tip))
getIn (Positional 0 :: Key Double) [Named "treeRHS", Named "treeLHS", Named "treeNode"]
      (object t_bar)
> Just 3.141592653589793

Wrapping it all up

This is not a serious example, necessarily, although it does point to the kinds of things that GHC Generics are good for. When you want to handle data according to its shape, not its meaning, then this is a good way to reduce duplicated effort, and allow 3rd party tools to opt-in. Examples of this are often to do with interacting with the outside world, such as JSON encoding/decoding, or binary serialization. You can write your own FromJSON and ToJSON instances, but if you don't have very finicky needs, why not get the compiler to write it for you? And then you ensure that you never forget to add a new field to the encoder.

Even this toy example has interesting applications, such as very lightweight reflection (there are better reflection tools, but the API here is dead simple), or it could describe in a configuration file the path through a graph of values to a configuration node. Obviously that is not a Haskelly approach, since it involves throwing away the type-safety of the nominal type system in return for the flexibility of structural typing, but it goes to show that with only a small amount of effort, Haskell has the same flexibility as even the most unityped language.