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 includeVoid
, and the phantom data types used as tags in some systems. -
U1
- this is the value without any fields. This includes common things likeTrue
andFalse
as well as enumerations likedata XS = A | B | C
. In this case the value being represented isTrue
orA
. -
a :+: b
is where there is a choice of two constructors. This includes things likeBool = True | False
, ordata Tree a = Tip | Branch (Tree a) (Tree a)
ordata 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. Indata 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.
Top comments (0)