Data.Data module of the GHC base.
Our gmap is optimal: the parts of the data
type that are not affected by mapping are not even traversed. The code
has not a single unsafe operation. Furthermore, if the function to map
is total and Data.Data instances are properly implemented, gmap is total. Although written in the parametricity-breaking
framework SYB that relies on run-time type-introspection,
our gmap is parametric.Generic map is the generalization of the list map and related functions:
map :: (a->b) -> [a] -> [b]
map2 :: (a->b) -> [[a]] -> [[b]]
mapl :: (a->b) -> Either a w -> Either b w
mapx :: (a->b) -> Tree (Maybe (a,Int)) -> Tree (Maybe (b,Int))
...
All these diverse mapping operations become particular instances of a single
function gmap. It is also a generic version of Functor's fmap:class Functor c where fmap :: (a->b) -> c a -> c bNormally, we have to write code for
fmap every time we define a new
instance of Functor. The generic map is written once and for all, for any
data type that is a member of Data.Data. The gmap code is the
`boilerplate', which expresses in an abstract way what it means to
map an (a->b) function over a data type.
For a long time, it was considered impossible to write gmap in SYB.
Although SYB has many functions whose names contain `map', none of
them generalize List.map. At first blush, the generic fold gfold,
a generalization of list fold, lets us easily define something quite close
to a generic map, namely
gmappish :: (Data a, Data (c a)) => (a -> a) -> c a -> c a
gmappish f x = traverse x
where
traverse :: Data a => a -> a
traverse x = unID $ gfoldl k z x
z = ID
k (ID ca) b | Just fb <- castfn f = ID (ca (fb b))
k (ID ca) b = ID (ca (traverse b))
newtype ID a = ID{unID :: a}
castfn :: (Typeable a, Typeable b, Typeable c, Typeable d) =>
(a -> b) -> Maybe (c -> d)
castfn f = cast f
The operation gfold traverses the immediate subcomponents of a value.
If a subcomponent can be passed as an argument to the transforming function f
(i.e., the types match), it is transformed.
Otherwise, we traverse it recursively. The function gmappish
does seem to act like gmap when f
is type-preserving. Alas, there are two problems: gmappish does not
generalize to mappings that do change the type of the transformed value.
Furthermore, gmappish is not truly a map: it is not parametric.
The generalization failure is easy to see, from the type of gfoldl on
which gmappish is based:
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) ->
(forall g. g -> c g) -> a -> c a
The function gfoldl folds over a value of type a and produces
the result c a, with the type constructor c providing the context
of the traversal. Crucially the result is parameterized by the type
of the value to fold. For generic map however we need the result of
a different type, related to the input type in complex ways, see map2, mapl, mapx signatures before. Generic fold gfoldl is
not generic enough.
The non-parametricity of gmappish is subtle, so we explain it
on the example of mapping over a Tricky data type:
data Tricky a = Tricky a Int
tricky_mappish :: Data a => (a->a) -> Tricky a -> Tricky a
tricky_mappish = gmappish
trickish1 = tricky_mappish not (Tricky True 1)
-- Tricky False 1
trickish2 = tricky_mappish (+1) (Tricky (0::Int) 1)
-- Tricky 1 2
Here tricky_mappish is just an instance of gmappish to map over Tricky a; for example, trickish1 maps not over Tricky Bool
with the expected result. The example trickish2 maps successor over Tricky Int -- and so it increments every Int it can find in the
data type, whether that Int is an instance of the type parameter of Tricky, or an unrelated Int component. Hence gmappish has a
`side-effect' of transforming more components of the data type than
intended. It cannot be reasoned as fmap at all: gmappish f . fmap g
/= fmap (f . g). It is not parametric and breaks fusion laws.
The two key insights of our solution address the two problems of gmappish. First is the inability of gfoldl to express mappings
that change the type of the result. A
serialize-transform-deserialize trick gets around this
problem. One may think of gmap as writing its argument to a file,
transforming the file systematically and reading the result back, at
possibly a different type. Generic show and read are well-supported
by SYB. Of course we do not actually write to any file; our
`serialization':
type Serialized = (Constr,[Dyn])
data Dyn = forall a. Data a => Dyn a
data Kids a = Kids{growUp:: [Dyn]}
serialize :: Data a => a -> Serialized
serialize x = (toConstr x, growUp $ gfoldl k (const (Kids [])) x)
where k (Kids l) a = Kids (l ++ [Dyn a])
`writes' a value as the data constructor descriptor followed
by the list of its arguments, which are lazily `serialized'
(that is, wrapped in Dyn). The deserialization step, written
in terms of gunfold, reassembles the
value from its possibly transformed subcomponents. The function gmapt (described below) maps over the subcomponents. Since gmapt needs a template, to be discussed next, the deserialization
handles the serialized value and the template in parallel. data UnfldStateT a = UnfldStateT a [Dyn] [Dyn]
rebuild :: (Data a, Data b, Data t) =>
(a->b) -> Serialized -> Serialized -> t
rebuild f (tcon, tkids) (con, kids) =
case gunfold k (\g -> UnfldStateT g tkids kids) con of
UnfldStateT a [] [] -> a
where k (UnfldStateT ca (tkid:tkids) ((Dyn kid):kids)) =
UnfldStateT (ca (gmapt f tkid kid)) tkids kids
The compositionality problem of gmappish comes from its promiscuity:
when the polymorphic gmappish :: (a->a) -> c a -> c a is
instantiated (say, to a concrete type Int for a and a concrete Tricky
for c), it tries to map any component whose type happens to be Int, whether that Int came from instantiating a for Int, or
not. The solution is to distinguish the two, using a template, which
is an instance c X for some private type X. The mapping function
traverses the value (of the type Tricky Int, say), and the template
(of the type Tricky X) in parallel. When we encounter an Int component
and wish to transform it, we check if the corresponding component in the
template has the type X. This ``X marks the spot'' idea was first
described by Claus Reinke. We develop it further: our template is ephemeral,
that is, undefined.
We are only interested in its type and the type of its components. Therefore,
our approach avoids any unsafe operations. We build the template
incrementally, as we further traverse the real value and learn its structure
layer-by-layer. Here is the rest of the gmap code. The workhorse is gmapt, which takes, in addition to the value to transform, its template,
of the type Dyn.
gmap :: forall a b c .
(Data a, Data b, Data (c a), Data (c b), Data (c X)) =>
(a -> b) -> c a -> c b
gmap f = gmapt f (Dyn (undefined::c X))
data X = X deriving (Data,Typeable)
gmapt :: (Data a, Data b, Data x, Data y) => (a -> b) -> Dyn -> x -> y
gmapt f trep = maybe (\x -> traverse (trep,x)) ifmarked $ castfn f
where
hasmark :: Dyn -> Bool
hasmark (Dyn x) = typeOf x == typeOf X
-- The gmapped value x has the right type to be transformed by 'f'
-- We do the transformation only if 'x' has the mark
ifmarked f x | hasmark trep = f x
ifmarked f x = traverse (trep,x)
-- optimization: t has no mark, there is nothing to map under it
traverse (Dyn t,x) | typeOf t == typeOf x =
maybe (error "traverse1") id $ cast x
traverse (Dyn t,x) | (tcon,tkids) <- splitTyConApp (typeOf t),
(con,kids) <- splitTyConApp (typeOf x),
not (length tkids == length kids && tcon == con) =
error $ unwords ["template type", show (typeOf t),
"inconsistent with value type", show (typeOf x)]
traverse (Dyn t,x) = rebuild f (serialize t1) xdyn
where xdyn@(con,kids) = serialize x
t1 = fromConstr con `asTypeOf` t -- build the ephemeral template
The code has many internal self-consistency checks that should never fire.
The code includes an optimization: if the template (after removing Dyn)
has the same type as the mapped value, there is no X in there and hence
there is nothing to map. Therefore, we immediately return the value
as it is, with no transformation or even traversal.
In conclusion, we have presented a surprising application of Data/Typeable to define Functor's fmap generically, once and
for all. As behooves to the generic fmap, our gmap is total (for
the total mapping function) and parametric. It is also optimal,
traversing only the needed parts of the value. Our approach is a
synthesis of a fake serialization-deserialization with an sham `X
marks the spot' template. Claus Reinke has summarized the approach
aptly: ``if I had followed my own choice of metaphor to the end, I
would have known that X marks the spot only on a map, not on the real
thing (or else everyone could find the treasure..). Your shallow,
incrementally built not-quite copy is just another representation of a
map, and since both map and X are hidden from users of the function,
everyone is happy.''.
I greatly appreciate many critical and inspiring discussions with Claus Reinke and Alexey Rodriguez-Yakushev on the Hs-Generics mailing list in June-July 2008.
Threads entitled ``gMap in SYB1'' and ``compositional gMap in SYB1'' on the Hs-Generics mailing list, July 2008.
< http://www.haskell.org/pipermail/generics/2008-July/000349.html >
< http://www.haskell.org/pipermail/generics/2008-July/000362.html >
Claus Reinke: Traversable Functor Data,or: X marks the spot
Message posted on the Hs-Generics mailing list on Tue Jun 24 14:45:18 EDT 2008
< http://www.haskell.org/pipermail/generics/2008-June/000343.html >
That message proposed the idea of `X marking the spot'.
It has been further developed in gmap, specifically to avoid
any unsafe operations.
Ralf Lämmel and Simon L. Peyton Jones: Scrap Your Boilerplate: A Practical Design Pattern for Generic Programming TLDI 2003, pp. 26-37
< http://www.research.microsoft.com/~simonpj/papers/hmap/ >
This is the paper that introduced SYB.
Claus Reinke: Re: compositional gMap in SYB1
Message posted on the Hs-Generics and Haskell-Libraries mailing lists on Tue Jul 29 15:25:02 EDT 2008
< http://www.haskell.org/pipermail/generics/2008-July/000367.html >
The message turns gmap into a generic traverse, that is,
Traversable.traverse implemented once and for all.
Data.Data, which is
at the core of the generic programming framework SYB. Data.Data and
the related Data.Typeable are part of the GHC base. As an
illustration of our approach we answer Wadler's and Clayden's
questions.
Reifying a data type may seem easy. Given a value of the data type, we
traverse it with gMapQ to find out all its components and their
types. For example, the traversal of [(Just 'a', True)] might
produce the tree
TData "[((Maybe Char),Bool)]"
[TCon "(:)"
[TData "((Maybe Char),Bool)"
[TCon "(,)" [TData "Maybe Char" [TCon "Just" [TData "Char" []]],
TData "Bool" [TCon "True" []]]],
TCon "[]" []]]
What if the only values we have are [(Nothing, True)]::[(Maybe Char,Bool)]
or []::[(Maybe Char,Bool)]? Given just the type Maybe Char,
with no concrete value, we have to determine the data constructors, Just and Nothing, and the types of their arguments, and their
data constructors, etc. The question still seems easy: Data.Data offers the function dataTypeOf :: Data a => a -> DataType
that describes the data type a without requiring any concrete value
of it (in other words, dataTypeOf does not evaluate its argument).
The datatype description has the name of the data type, its sort
(algebraic, Integer, Float, etc.) and the names of its constructors.
Alas, the description gives just the names of data constructors --
but not the number and the types of their
arguments. In other words, dataTypeOf gives a shallow description
of the data type, with too little information to construct its graph.
Fortunately, Data.Data has another way to describe a data type
without needing its value:
gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c aPer se,
gunfold does only the shallow traversal, but it can be applied
recursively. Its signature is a bit strange. Let's
look at one of its instances, when a is Maybe Char: gunfold :: (forall b r. Data b => c (b -> r) -> c r) ->
(forall r. r -> c r) -> Constr -> c (Maybe Char)
gunfold k z c | c == constructor_Nothing = z Nothing
gunfold k z c | c == constructor_Just = k (z Just)
In the last line, k receives z Just of the type c (b->r) where r is Maybe Char and b is Char; b is exactly what we need:
the argument type of the constructor Just. Not only k, which we
provide, finds out the constructor argument type -- it is assured
by the gunfold signature that the type is a member of Data and
hence can be introspected and gunfolded in turn.
That is the general idea of our solution. It is implemented
via a pair of mutually recursive functions describe_type' :: Data a => IgnoreTypes -> SeenTypes -> CTTree a
describe_ctor :: Data a => IgnoreTypes -> SeenTypes -> Constr -> CCList a
type SeenTypes = [TypeRep]
type IgnoreTypes = [TypeRep]
The former finds out the names of constructors and the latter describes the
arguments of a given constructor. Together, they reify a data type a as
a term of the following structure data TRepTree = TData TRep [TCon] | BackRef TypeRep
data TRep = forall a. Data a => TRep a
data TCon = TCon Constr [TRepTree] -- a data constructor and its args
Whereas TRep tells the data type name, sort, and the names of its
constructors, TCon describes one data constructor, named by Data.Data.Constr, with all its arguments.
Since a data type can be recursive the representation may contain cycles,
which are encoded with BackRef. Our functions have to keep track
of the already described data types (the argument SeenTypes) and
build BackRef accordingly. Finally, we let the user prevent
the traversal of particular data types. For example,
one may wish to treat [Char] as an atomic data type of strings rather than
as a list of characters. The function describe_type puts it all
together: describe_type :: forall a. Data a => IgnoreTypes -> a -> TRepTree
describe_type ignore _ = tree
where
CTTree tree = describe_type' ignore [] :: CTTree a
The data type from the initial example is described as follows, with the
result shown in the comments. Compared to the description at the beginning
of the article, the one below has more detail: we now see all data
constructors of Bool and of Maybe Char.
t1 = describe_type [] ([] :: [(Maybe Char, Bool)])
{-
TData [((Maybe Char),Bool)]
[TCon [] [],
TCon (:)
[TData ((Maybe Char),Bool)
[TCon (,)
[TData Maybe Char [TCon Nothing [], TCon Just [TData Char []]],
TData Bool [TCon False [],TCon True []]]],
BackRef [((Maybe Char),Bool)]]]
-}
Once the TRepTree is constructed, answering Wadler's and Clayden's
questions is easy. The former was asking if a data type has a
recursive subcomponent; if not, its maximum depth. For example, Pair
Int (Either Int Int) has depth 3. The depth computation is the
standard depth-first traversal of a TRepTree accumulating the
depth maximum over all branches. If we encounter a BackRef, the
data type is recursive and the depth is infinity. Clayden's question,
of picking out all newtype descriptions, is also answered by the
traversal.
We have seen that the often-mysterious gunfold tells us about
arguments of a data constructor just from its name and its data type,
with no concrete value at hand. Moreover, gunfold can be applied
recursively on the arguments. In the result, we reify a data type
as a TRepTree term, the graph of the data type. We have answered
Wadler's general question of type introspection:
``whether the information about types could be turned into a graph
and manipulated as such''.
Our polymorphic variants are literally open co-products: dual of extensible polymorphic records of HList. The duality is negation:
NOT (A | B) -> (NOT A & NOT B)This implication is a part of the deMorgan law that holds both in classical, and, more importantly, in intuitionistic logics. Our encoding of sums is the straightforward Curry-Howard image of that law.
Our implementation of polymorphic variants in terms of HList records uses no type classes, no type-level programming or any other type hacking. In fact, there are no type annotations, type declarations, or any other mentioning of types, except in the comments.
open-coproduct.txt [4K]
Polymorphic variants (extensible, recursive sums) with HList
The message posted on the Haskell mailing list on Sun, 2 Jul 2006 18:35:12 -0700 (PDT)
< http://guppy.eng.kagawa-u.ac.jp/~kagawa/PVH >
Koji Kagawa: Polymorphic Variants in Haskell
Presented at the Haskell Workshop 2006
This paper proposes a quite different solution to the expression problem, encoding constructors of open `data types' as class methods. Our example is patterned after the running example of this paper.
The code files below closely follow the layout of the running example in Laemmel and Peyton-Jones' ICFP2005 talk. The comments describe which part of the code is the `Library', which part of the code is the (data-structure--independent) `generic function', and which part of the code overrides the general processing of the generic function. The code has two examples; one of them is gsize of the original SYB3 paper.
Our variation of SYB3 takes advantage of the fact that
type-class-bounded and higher-rank polymorphisms can be partially
traded for each other. To be more precise, we use type codes for
functions and dictionaries. The type code must then be interpreted by a type
class similar to Apply of HList (cf. HMap).
This extra interpretation step is the main conceptual deviation
from SYB3, largely taking the important idea of function combinators
out of it.
dat2.hs [4K]
With a little bit of CPS, we now eliminate recursive instance dependency even for recursive datatypes. This is our final solution.
Re: Scrap your boilerplate and Variants
The discussion thread started from a message posted on the Haskell-Generics mailing list on Tue Oct 24 23:28:24 EDT 2006
Our inspiration, SYB3: Scrap your boilerplate with class: extensible generic functions by Ralf Laemmel and Simon Peyton-Jones. In: Proceedings of ICFP 2005.
SYB1, when traversing terms and invoking user functions for subterms of a particular type, relies on a run-time typecase. The latter requires run-time type representation, which is provided by the typeclass Typeable. The typeclass implements the method `cast' for a safe cast from the `generic type' to the specific type. We observe that the typecase, at the type level, has always existed in Haskell: it is the type equality predicate TypeEq of HList.
Our generic functions, like those of SYB1, are ordinary functions. Since the transformation for each subterm is chosen at compile-time, however, we do not need any casts, run-time type representations, or Typeable. We do not need higher-ranked types either. Also unlike SYB1, the set of traversal strategies is extensible: To the pre-defined strategies for gmap, gshow, gfold and geq, the programmer may at any time add a new class of traversals.
Our most general generic function is gapp, which applies a generic function to a term. A generic function is, quite literally, made of two parts. First is a term traversal strategy, identified by a label. One strategy may be to `reduce' a term using a supplied reducing function (cf. fold over a tree). Another strategy rebuilds a term. The second component of a generic function is spec, the HList of `exceptions', or ad hoc transformations. Each element of spec is an ordinary function that tells how to transform a term of a specific type. Exceptions override the generic traversal: If the type of the input term matches the argument type of one of the functions in spec we apply that function. If no specific function applies, we do the generic action implicit in the traversal strategy.
The algorithm that selects for each input subterm the appropriate transformer is tantamount to overloading resolution algorithm. Smash thus implements typeclass instance selection algorithm in the typechecker itself. The messages below describe the implementation of typeclasses in terms of Smash, with an additional flexibility of reordering, inspecting and deleting `instances'.
smash-first.txt [8K]
Smash your boiler-plate without class and Typeable
The message describing the original Smash approach, posted on the Haskell mailing list on 10 Aug 2006 21:16:34 -0000
smash-along.txt [12K]
Smash along your boilerplate; how to traverse a non-existent term
The improved and generalized approach, described in the message posted on the Haskell mailing list on Tue, 5 Jun 2007 00:09:02 -0700 (PDT)
< http://www.haskell.org/haskellwiki/Applications_and_libraries/Generic_programming/Smash >
`Smash' on Haskell Wiki
undefined and produce the fully-defined smallest
(resp. largest) term of the desired type: gminimum () :: (Maybe Int,Either Bool (Maybe Char))
-- ==> (Nothing,Left False)
gmaximum () :: (Maybe Int,Either Bool (Maybe Char))
-- ==> (Just 2147483647,Right (Just '\1114111'))
The result of traversing
undefined::(Maybe Int,Either Bool (Maybe Char)) is
(Nothing,Left False). We take advantage of the fact that undefined
stands for a term of any structure and is deconstructible and
traversable. Haskell's non-strictness lets us
meaningfully traverse non-existing terms.
Traversing non-existing sums such as
undefined::Either Int Char requires special attention.
Sums give us a choice. We should report the available alternatives,
and let the users make the choice of a component of the sum.
The implementation of gminimum always chooses the first
available alternative; gmaximum chooses the last available.
The function gminimum is akin to the de-typechecker since
both convert `undefined' to `defined'. De-typechecker produces only
polymorphic functions, whereas gminimum yields data, including monomorphic
functions.
smash-along.txt [12K]
Smash along your boilerplate; how to traverse a non-existent term
The explanation, described in the second half of the message posted on the Haskell mailing list on Tue, 5 Jun 2007 00:09:02 -0700 (PDT)
Serialization can be written generically, with generic fold. The following Smash code says the result of serializing an object is the list of all its primitive fields.
serialize xs = gapp (TL_red concat) primitive_fields_show xs
primitive_fields_show =
(\ (s::Int) -> [show s]) :+:
(\ (s::Float) -> [show s]) :+:
(\ (s::String) -> [s]) :+:
HNil -- more can be added in the future
For example, for the following data type of a company and a sample term (from the famous example of SYB papers) data Company = C [Dept]; data Dept = D Name Manager [Unit]
data Unit = PU Employee | DU Dept
data Employee = E Person Salary; data Person = P Name Address
data Salary = S Float; type Manager = Employee
type Name = String; type Address = String
genCom = C [D "Research" (E (P "Laemmel" "Amsterdam") (S 8000.0))
[PU (E (P "Joost" "Amsterdam") (S 1000.0)),
PU (E (P "Marlow" "Cambridge") (S 2000.0))],
D "Strategy" (E (P "Blair" "London") (S 100000.0)) []]
serialize genCom produces the list ["Research","Laemmel","Amsterdam","8000.0","Joost","Amsterdam",
"1000.0","Marlow","Cambridge","2000.0","Strategy","Blair",
"London","100000.0"]
Hugh Perkins has posed the problem of writing a generic deserializer, which should work for terms of any structure in the domain of a generic programming library. His particular application is complex terms representing XML documents. The deserializer can indeed be written generically: in the first approximation, it is a generic monadic map over a term. It takes a term, the prototype, and the list of serialized primitive fields as a monadic state. The deserializer traverses the prototype replacing each primitive field with the corresponding value from the monadic state. For example, assuming the following list of serialized fields:
retro = ["Metaphysics", "Kant","Koeningsberg","800.0",
"Hume","Edinburgh","100.0",
"Marlowe","Cambridge","200.0",
"Ruling","Thatcher","London","50000.0"]
and genCom as the prototype, deserialize genCom retro `upgrades' the company giving us the term C [D "Metaphysics" (E (P "Kant" "Koeningsberg") (S 800.0))
[PU (E (P "Hume" "Edinburgh") (S 100.0)),
PU (E (P "Marlowe" "Cambridge") (S 200.0))],
D "Ruling" (E (P "Thatcher" "London") (S 50000.0)) []]
In the discussion thread, Jeremy Gibbons has pointed out that McBride and Paterson's idiomatic traverse subsumes monadic gmap. See his and Oliveira's paper below for the detailed discussion.
Hugh Perkins et al. Thread on the Hs-Generics mailing list, June 26-July 3, 2007.
Jeremy Gibbons and Bruno C. d. S. Oliveira. The essence of the Iterator pattern.
< http://web.comlab.ox.ac.uk/jeremy.gibbons/publications/#iterator >
oleg-at-okmij.org
Your comments, problem reports, questions are very welcome!
Converted from HSXML by HSXML->HTML