GHC.Generics
From HaskellWiki
(→Limitations) |
m (fix typo) |
(32 intermediate revisions by 5 users not shown) |
Revision as of 23:42, 8 December 2013
GHC 7.2 includes improved support for datatype-generic programming through two new features, enabled with two new flags: DeriveGeneric and DefaultSignatures. We show how this all works in this page, starting with a detailed example.
Since this is a fresh new feature, it is possible that you will run into bugs when using it. If so, please report them!
Contents |
1 Example: serialization
Suppose you are writing a class for serialization of data. You have a typedata Bit = O | I class Serialize a where put :: a -> [Bit]
You might have written some instances already:
instance Serialize Int where put i = serializeInt i instance Serialize a => Serialize [a] where put [] = [] put (h:t) = put h ++ put t
A user of your library, however, will have his own datatypes, like:
data UserTree a = Node a (UserTree a) (UserTree a) | Leaf
It is here that generic programming can help you. If you are familiar with SYB you could use it at this stage, but now we'll see how to do this with the new features of GHC 7.2.
1.1 Generic serialization
First you have to tell the compiler how to serialize any datatype, in general. Since Haskell datatypes have a regular structure, this means you can just explain how to serialize a few basic datatypes.
1.1.1 Representation types
We can represent most Haskell datatypes using only the following primitive types:
-- | Unit: used for constructors without arguments data U1 p = U1 -- | Constants, additional parameters and recursion of kind * newtype K1 i c p = K1 { unK1 :: c } -- | Meta-information (constructor names, etc.) newtype M1 i c f p = M1 { unM1 :: f p } -- | Sums: encode choice between constructors infixr 5 :+: data (:+:) f g p = L1 (f p) | R1 (g p) -- | Products: encode multiple arguments to constructors infixr 6 :*: data (:*:) f g p = f p :*: g p
type RepUserTree a = -- A UserTree is either a Leaf, which has no arguments U1 -- ... or it is a Node, which has three arguments that we put in a product :+: a :*: UserTree a :*: UserTree a
Simple, right? Different constructors become alternatives of a sum, and multiple arguments become products. In fact, we want to have some more information in the representation, like datatype and constructor names, and to know if a product argument is a parameter or a type. We use the other primitives for this, and the representation looks more like:
type RealRepUserTree a = -- Information about the datatype M1 D Data_UserTree ( -- Leaf, with information about the constructor M1 C Con_Leaf U1 -- Node, with information about the constructor :+: M1 C Con_Node ( -- Constructor argument, which could have information -- about a record selector label M1 S NoSelector ( -- Argument, tagged with P because it is a parameter K1 P a) -- Another argument, tagged with R because it is -- a recursive occurrence of a type :*: M1 S NoSelector (K1 R (UserTree a)) -- Idem :*: M1 S NoSelector (K1 R (UserTree a)) ))
1.1.2 A generic function
Since GHC can represent user types using only those primitive types, all you have to do is to tell GHC how to serialize each of the individual primitive types. The best way to do that is to create a new type class:
class GSerialize f where gput :: f a -> [Bit]
instance GSerialize U1 where gput U1 = []
The serialization of multiple arguments is simply the concatenation of each of the individual serializations:
instance (GSerialize a, GSerialize b) => GSerialize (a :*: b) where gput (a :*: b) = gput a ++ gput b
The case for sums is the most interesting, as we have to record which alternative we are in. We will use a 0 for left injections and a 1 for right injections:
instance (GSerialize a, GSerialize b) => GSerialize (a :+: b) where gput (L1 x) = O : gput x gput (R1 x) = I : gput x
We don't need to encode the meta-information, so we just go over it recursively :
instance (GSerialize a) => GSerialize (M1 i c a) where gput (M1 x) = gput x
instance (Serialize a) => GSerialize (K1 i a) where gput (K1 x) = put x
1.1.3 Default implementations
We've seen how to represent user types generically, and how to define functions on representation types. However, we still have to tie these two together, explaining how to convert user types to their representation and then applying the generic function.
The representationclass Generic a where -- Encode the representation of a user datatype type Rep a :: * -> * -- Convert from the datatype to its representation from :: a -> (Rep a) x -- Convert from the representation to the datatype to :: (Rep a) x -> a
instance Generic (UserTree a) where type Rep (UserTree a) = RepUserTree a from Leaf = L1 U1 from (Node a l r) = R1 (a :*: l :*: r) to (L1 U1) = Leaf to (R1 (a :*: l :*: r)) = Node a l r
putDefault :: (Generic a, GSerialize (Rep a)) => a -> [Bit] putDefault a = gput (from a)
instance (Serialize a) => Serialize (UserTree a) where put = putDefault
1.2 Using GHC's new features
What we have seen so far could all already be done, at the cost of writing a lot of boilerplate code yourself (or spending hours writing Template Haskell code to do it for you). Now we'll see how the new features of GHC can help you.
1.2.1 Deriving representations
The{-# LANGUAGE DeriveGeneric #-} data UserTree a = Node a (UserTree a) (UserTree a) | Leaf deriving Generic
(Standalone deriving also works fine, and you can use it for types you have not defined yourself, but are imported from somewhere else.) You will need the new DeriveGeneric language pragma.
1.2.2 More general default methods
We don't want the user to have to write theWe solved this by allowing the user to give a different signature for default methods:
{-# LANGUAGE DefaultSignatures #-} class Serialize a where put :: a -> [Bit] default put :: (Generic a, GSerialize (Rep a)) => a -> [Bit] put a = gput (from a)
Now the user can simply write:
instance (Serialize a) => Serialize (UserTree a)
1.3 Complete working example
{-# LANGUAGE DefaultSignatures, DeriveGeneric, TypeOperators, FlexibleContexts #-} import GHC.Generics import Data.Bits data Bit = O | I deriving Show class Serialize a where put :: a -> [Bit] default put :: (Generic a, GSerialize (Rep a)) => a -> [Bit] put a = gput (from a) get :: [Bit] -> (a, [Bit]) default get :: (Generic a, GSerialize (Rep a)) => [Bit] -> (a, [Bit]) get xs = (to x, xs') where (x, xs') = gget xs class GSerialize f where gput :: f a -> [Bit] gget :: [Bit] -> (f a, [Bit]) -- | Unit: used for constructors without arguments instance GSerialize U1 where gput U1 = [] gget xs = (U1, xs) -- | Constants, additional parameters and recursion of kind * instance (GSerialize a, GSerialize b) => GSerialize (a :*: b) where gput (a :*: b) = gput a ++ gput b gget xs = (a :*: b, xs'') where (a, xs') = gget xs (b, xs'') = gget xs' -- | Meta-information (constructor names, etc.) instance (GSerialize a, GSerialize b) => GSerialize (a :+: b) where gput (L1 x) = O : gput x gput (R1 x) = I : gput x gget (O:xs) = (L1 x, xs') where (x, xs') = gget xs gget (I:xs) = (R1 x, xs') where (x, xs') = gget xs -- | Sums: encode choice between constructors instance (GSerialize a) => GSerialize (M1 i c a) where gput (M1 x) = gput x gget xs = (M1 x, xs') where (x, xs') = gget xs -- | Products: encode multiple arguments to constructors instance (Serialize a) => GSerialize (K1 i a) where gput (K1 x) = put x gget xs = (K1 x, xs') where (x, xs') = get xs instance Serialize Bool where put True = [I] put False = [O] get (I:xs) = (True, xs) get (O:xs) = (False, xs) -- -- Try it out. (Normally this would be in a separate module.) -- data UserTree a = Node a (UserTree a) (UserTree a) | Leaf deriving (Generic, Show) instance (Serialize a) => Serialize (UserTree a) main = do let xs = put True print (fst . get $ xs :: Bool) let ys = put (Leaf :: UserTree Bool) print (fst . get $ ys :: UserTree Bool) let zs = put (Node False Leaf Leaf :: UserTree Bool) print (fst . get $ zs :: UserTree Bool)
2 Different perspectives
We outline the changes introduced in 7.2 regarding support for generic programming from the perspective of three different types of users: the end-user, the generic programmer, and the GHC hacker.
2.1 The end-user
If you know nothing about generic programming and would like to keep it that way, then you will be pleased to know that using generics in GHC 7.2 is easier than ever. As soon as you encounter a class with a default signature (like Serialize above), you will be able to give empty instances for your datatypes, like this:
instance (Serialize a) => Serialize (UserTree a)
2.2 The generic programmer
If you are a library author and are eager to make your classes easy to instantiate by your users, then you should invest some time in defining instances for each of the representation types of GHC.Generics and defining a generic default method. See the example for Serialize above, and the original paper for many other examples (but make sure to check the changes from the paper).
2.3 The GHC hacker
If you are working on the GHC source code, you might find it useful to know what kind of changes were made. There is a Trac wiki page with a lower-level overview of things and also keeping track of what still needs to be done.
3 Changes from the paper
In the paper we describe the implementation in UHC. The implementation in GHC is slightly different:
- Representable0 and Representable1 have become Generic and Generic1, respectively. from0, to0, and Rep0 also lost the 0 at the end of their names.
- We are using type families, so the Generic and Generic1 type classes have only one type argument. So, in GHC the classes look like what we describe in the "Avoiding extensions" part of Section 2.3 of the paper. This change affects only a generic function writer, and not a generic function user.
- Default definitions (Section 3.3) work differently. In GHC we don't use a DERIVABLE pragma; instead, a type class can declare a generic default method, which is akin to a standard default method, but includes a default type signature. This removes the need for a separate default definition and a pragma. For example, the Encode class of Section 3.1 is now:
class Encode a where encode :: a -> [Bit] default encode :: (Generic a, Encode1 (Rep a)) => a -> [Bit] encode = encode1 . from
- To derive generic functionality to a user type, the user no longer uses (Section 4.6.1). Instead, the user gives an instance without defining the method; GHC then uses the generic default. For instance:deriving instance
instance Encode [a] -- works if there is an instance Generic [a]
4 Limitations
We cannot derive Generic instances for:
- Datatypes with a context;
- Existentially-quantified datatypes;
- GADTs.