1 -----------------------------------------------------------------------------
3 -- Module : Data.Generics.Basics
4 -- Copyright : (c) The University of Glasgow, CWI 2001--2004
5 -- License : BSD-style (see the file libraries/base/LICENSE)
7 -- Maintainer : libraries@haskell.org
8 -- Stability : experimental
9 -- Portability : non-portable
11 -- \"Scrap your boilerplate\" --- Generic programming in Haskell
12 -- See <http://www.cs.vu.nl/boilerplate/>. The present module provides
13 -- the Data class with its primitives for generic programming.
15 -----------------------------------------------------------------------------
17 module Data.Generics.Basics (
19 -- * Module Data.Typeable re-exported for convenience
22 -- * The Data class for processing constructor applications
24 gfoldl, -- :: ... -> a -> c a
25 gunfold, -- :: ... -> Constr -> c a
26 toConstr, -- :: a -> Constr
27 dataTypeOf, -- :: a -> DataType
28 dataCast1, -- mediate types and unary type constructors
29 dataCast2 -- mediate types and binary type constructors
32 -- * Datatype representations
33 DataType, -- abstract, instance of: Show
34 Constr, -- abstract, instance of: Eq, Show
35 DataRep(..), -- instance of: Eq, Show
36 ConstrRep(..), -- instance of: Eq, Show
37 ConIndex, -- alias for Int, start at 1
38 Fixity(..), -- instance of: Eq, Show
40 -- * Observers for datatype representations
41 dataTypeName, -- :: DataType -> String
42 dataTypeRep, -- :: DataType -> DataRep
43 constrType, -- :: Constr -> DataType
44 constrRep, -- :: Constr -> ConstrRep
45 repConstr, -- :: DataType -> ConstrRep -> Constr
47 -- * Representations of algebraic data types
48 mkDataType, -- :: String -> [Constr] -> DataType
49 mkConstr, -- :: DataType -> String -> Fixity -> Constr
50 dataTypeConstrs,-- :: DataType -> [Constr]
51 constrFields, -- :: Constr -> [String]
52 constrFixity, -- :: Constr -> Fixity
54 -- * From strings to constr's and vice versa: all data types
55 showConstr, -- :: Constr -> String
56 readConstr, -- :: DataType -> String -> Maybe Constr
58 -- * Convenience funtions: algebraic data types
59 isAlgType, -- :: DataType -> Bool
60 indexConstr, -- :: DataType -> ConIndex -> Constr
61 constrIndex, -- :: Constr -> ConIndex
62 maxConstrIndex, -- :: DataType -> ConIndex
64 -- * Representation of primitive types
65 mkIntType, -- :: String -> DataType
66 mkFloatType, -- :: String -> DataType
67 mkStringType, -- :: String -> DataType
68 mkIntConstr, -- :: DataType -> Integer -> Constr
69 mkFloatConstr, -- :: DataType -> Double -> Constr
70 mkStringConstr, -- :: DataType -> String -> Constr
72 -- * Non-representations for non-presentable types
73 mkNorepType, -- :: String -> DataType
74 isNorepType, -- :: DataType -> Bool
76 -- * Convenience functions: take type constructors apart
77 tyconUQname, -- :: String -> String
78 tyconModule, -- :: String -> String
80 -- * Generic maps defined in terms of gfoldl
90 -- * Generic operation(s) defined in terms of gunfold
91 fromConstr, -- :: Constr -> a
92 fromConstrB, -- :: ... -> Constr -> a
93 fromConstrM -- :: Monad m => ... -> Constr -> m a
98 ------------------------------------------------------------------------------
110 ------------------------------------------------------------------------------
114 ------------------------------------------------------------------------------
118 The Data class comprehends a fundamental primitive "gfoldl" for
119 folding over constructor applications, say terms. This primitive can
120 be instantiated in several ways to map over the immediate subterms of
121 a term; see the "gmap" combinators later in this module. Indeed, a
122 generic programmer does not necessarily need to use the ingenious
123 gfoldl primitive but rather the intuitive "gmap" combinators. The
124 "gfoldl" primitive is completed by means to query top-level
125 constructors, to turn constructor representations into proper terms,
126 and to list all possible datatype constructors. This completion
127 allows us to serve generic programming scenarios like read, show,
128 equality, term generation.
132 class Typeable a => Data a where
136 Folding constructor applications ("gfoldl")
138 The combinator takes two arguments "k" and "z" to fold over a term
139 "x". The result type is defined in terms of "x" but variability is
140 achieved by means of type constructor "c" for the construction of the
141 actual result type. The purpose of the argument "z" is to define how
142 the empty constructor application is folded. So "z" is like the
143 neutral / start element for list folding. The purpose of the argument
144 "k" is to define how the nonempty constructor application is
145 folded. That is, "k" takes the folded "tail" of the constructor
146 application and its head, i.e., an immediate subterm, and combines
147 them in some way. See the Data instances in this file for an
148 illustration of "gfoldl". Conclusion: the type of gfoldl is a
149 headache, but operationally it is simple generalisation of a list
154 -- | Left-associative fold operation for constructor applications
155 gfoldl :: (forall a b. Data a => c (a -> b) -> a -> c b)
156 -> (forall g. g -> c g)
159 -- Default definition for gfoldl
160 -- which copes immediately with basic datatypes
164 -- | Unfolding constructor applications
165 gunfold :: (forall b r. Data b => c (b -> r) -> c r)
166 -> (forall r. r -> c r)
170 -- | Obtaining the constructor from a given datum.
171 -- For proper terms, this is meant to be the top-level constructor.
172 -- Primitive datatypes are here viewed as potentially infinite sets of
173 -- values (i.e., constructors).
175 toConstr :: a -> Constr
178 -- | Provide access to list of all constructors
179 dataTypeOf :: a -> DataType
183 ------------------------------------------------------------------------------
185 -- Mediate types and type constructors
187 ------------------------------------------------------------------------------
189 -- | Mediate types and unary type constructors
190 dataCast1 :: Typeable1 t
191 => (forall a. Data a => c (t a))
193 dataCast1 _ = Nothing
195 -- | Mediate types and binary type constructors
196 dataCast2 :: Typeable2 t
197 => (forall a b. (Data a, Data b) => c (t a b))
199 dataCast2 _ = Nothing
203 ------------------------------------------------------------------------------
205 -- Typical generic maps defined in terms of gfoldl
207 ------------------------------------------------------------------------------
211 The combinators gmapT, gmapQ, gmapM, ... can all be defined in terms
212 of gfoldl. We provide corresponding default definitions leaving open
213 the opportunity to provide datatype-specific definitions.
215 (The inclusion of the gmap combinators as members of class Data allows
216 the programmer or the compiler to derive specialised, and maybe more
217 efficient code per datatype. Note: gfoldl is more higher-order than
218 the gmap combinators. This is subject to ongoing benchmarking
219 experiments. It might turn out that the gmap combinators will be moved
220 out of the class Data.)
222 Conceptually, the definition of the gmap combinators in terms of the
223 primitive gfoldl requires the identification of the gfoldl function
224 arguments. Technically, we also need to identify the type constructor
225 "c" for the construction of the result type from the folded term type.
230 -- | A generic transformation that maps over the immediate subterms
231 gmapT :: (forall b. Data b => b -> b) -> a -> a
233 -- Use an identity datatype constructor ID (see below)
234 -- to instantiate the type constructor c in the type of gfoldl,
235 -- and perform injections ID and projections unID accordingly.
237 gmapT f x = unID (gfoldl k ID x)
239 k (ID c) x = ID (c (f x))
242 -- | A generic query with a left-associative binary operator
243 gmapQl :: (r -> r' -> r) -> r -> (forall a. Data a => a -> r') -> a -> r
244 gmapQl o r f = unCONST . gfoldl k z
246 k c x = CONST $ (unCONST c) `o` f x
251 In the definition of gmapQ? combinators, we use phantom type
252 constructors for the "c" in the type of "gfoldl" because the result
253 type of a query does not involve the (polymorphic) type of the term
254 argument. In the definition of gmapQl we simply use the plain constant
255 type constructor because gfoldl is left-associative anyway and so it
256 is readily suited to fold a left-associative binary operation over the
257 immediate subterms. In the definition of gmapQr, extra effort is
258 needed. We use a higher-order accumulation trick to mediate between
259 left-associative constructor application vs. right-associative binary
260 operation (e.g., (:)). When the query is meant to compute a value of
261 type r, then the result type withing generic folding is r -> r. So the
262 result of folding is a function to which we finally pass the right
267 -- | A generic query with a right-associative binary operator
268 gmapQr :: (r' -> r -> r) -> r -> (forall a. Data a => a -> r') -> a -> r
269 gmapQr o r f x = unQr (gfoldl k (const (Qr id)) x) r
271 k (Qr c) x = Qr (\r -> c (f x `o` r))
274 -- | A generic query that processes the immediate subterms and returns a list
275 gmapQ :: (forall a. Data a => a -> u) -> a -> [u]
276 gmapQ f = gmapQr (:) [] f
279 -- | A generic query that processes one child by index (zero-based)
280 gmapQi :: Int -> (forall a. Data a => a -> u) -> a -> u
281 gmapQi i f x = case gfoldl k z x of { Qi _ q -> fromJust q }
283 k (Qi i' q) a = Qi (i'+1) (if i==i' then Just (f a) else q)
287 -- | A generic monadic transformation that maps over the immediate subterms
288 gmapM :: Monad m => (forall a. Data a => a -> m a) -> a -> m a
290 -- Use immediately the monad datatype constructor
291 -- to instantiate the type constructor c in the type of gfoldl,
292 -- so injection and projection is done by return and >>=.
294 gmapM f = gfoldl k return
301 -- | Transformation of at least one immediate subterm does not fail
302 gmapMp :: MonadPlus m => (forall a. Data a => a -> m a) -> a -> m a
306 The type constructor that we use here simply keeps track of the fact
307 if we already succeeded for an immediate subterm; see Mp below. To
308 this end, we couple the monadic computation with a Boolean.
312 gmapMp f x = unMp (gfoldl k z x) >>= \(x',b) ->
313 if b then return x' else mzero
315 z g = Mp (return (g,False))
317 = Mp ( c >>= \(h,b) ->
318 (f x >>= \x' -> return (h x',True))
319 `mplus` return (h x,b)
322 -- | Transformation of one immediate subterm with success
323 gmapMo :: MonadPlus m => (forall a. Data a => a -> m a) -> a -> m a
327 We use the same pairing trick as for gmapMp,
328 i.e., we use an extra Bool component to keep track of the
329 fact whether an immediate subterm was processed successfully.
330 However, we cut of mapping over subterms once a first subterm
331 was transformed successfully.
335 gmapMo f x = unMp (gfoldl k z x) >>= \(x',b) ->
336 if b then return x' else mzero
338 z g = Mp (return (g,False))
340 = Mp ( c >>= \(h,b) -> if b
342 else (f x >>= \x' -> return (h x',True))
343 `mplus` return (h x,b)
347 -- | The identity type constructor needed for the definition of gmapT
348 newtype ID x = ID { unID :: x }
351 -- | The constant type constructor needed for the definition of gmapQl
352 newtype CONST c a = CONST { unCONST :: c }
355 -- | Type constructor for adding counters to queries
356 data Qi q a = Qi Int (Maybe q)
359 -- | The type constructor used in definition of gmapQr
360 newtype Qr r a = Qr { unQr :: r -> r }
363 -- | The type constructor used in definition of gmapMp
364 newtype Mp m x = Mp { unMp :: m (x, Bool) }
368 ------------------------------------------------------------------------------
372 ------------------------------------------------------------------------------
375 -- | Build a term skeleton
376 fromConstr :: Data a => Constr -> a
377 fromConstr = fromConstrB undefined
380 -- | Build a term and use a generic function for subterms
381 fromConstrB :: Data a
382 => (forall a. Data a => a)
385 fromConstrB f = unID . gunfold k z
391 -- | Monadic variation on \"fromConstrB\"
392 fromConstrM :: (Monad m, Data a)
393 => (forall a. Data a => m a)
396 fromConstrM f = gunfold k z
398 k c = do { c' <- c; b <- f; return (c' b) }
403 ------------------------------------------------------------------------------
405 -- Datatype and constructor representations
407 ------------------------------------------------------------------------------
411 -- | Representation of datatypes.
412 -- | A package of constructor representations with names of type and module.
413 -- | The list of constructors could be an array, a balanced tree, or others.
415 data DataType = DataType
423 -- | Representation of constructors
425 { conrep :: ConstrRep
426 , constring :: String
427 , confields :: [String] -- for AlgRep only
428 , confixity :: Fixity -- for AlgRep only
429 , datatype :: DataType
432 instance Show Constr where
436 -- | Equality of constructors
437 instance Eq Constr where
438 c == c' = constrRep c == constrRep c'
441 -- | Public representation of datatypes
442 data DataRep = AlgRep [Constr]
451 -- | Public representation of constructors
452 data ConstrRep = AlgConstr ConIndex
455 | StringConstr String
461 -- | Unique index for datatype constructors.
462 -- | Textual order is respected. Starts at 1.
467 -- | Fixity of constructors
469 | Infix -- Later: add associativity and precedence
474 ------------------------------------------------------------------------------
476 -- Observers for datatype representations
478 ------------------------------------------------------------------------------
481 -- | Gets the type constructor including the module
482 dataTypeName :: DataType -> String
487 -- | Gets the public presentation of datatypes
488 dataTypeRep :: DataType -> DataRep
489 dataTypeRep = datarep
492 -- | Gets the datatype of a constructor
493 constrType :: Constr -> DataType
494 constrType = datatype
497 -- | Gets the public presentation of constructors
498 constrRep :: Constr -> ConstrRep
502 -- | Look up a constructor by its representation
503 repConstr :: DataType -> ConstrRep -> Constr
505 case (dataTypeRep dt, cr) of
506 (AlgRep cs, AlgConstr i) -> cs !! (i-1)
507 (IntRep, IntConstr i) -> mkIntConstr dt i
508 (FloatRep, FloatConstr f) -> mkFloatConstr dt f
509 (StringRep, StringConstr str) -> mkStringConstr dt str
510 _ -> error "repConstr"
514 ------------------------------------------------------------------------------
516 -- Representations of algebraic data types
518 ------------------------------------------------------------------------------
521 -- | Constructs an algebraic datatype
522 mkDataType :: String -> [Constr] -> DataType
523 mkDataType str cs = DataType
525 , datarep = AlgRep cs
529 -- | Constructs a constructor
530 mkConstr :: DataType -> String -> [String] -> Fixity -> Constr
531 mkConstr dt str fields fix =
533 { conrep = AlgConstr idx
540 idx = head [ i | (c,i) <- dataTypeConstrs dt `zip` [1..],
541 showConstr c == str ]
544 -- | Gets the constructors
545 dataTypeConstrs :: DataType -> [Constr]
546 dataTypeConstrs dt = case datarep dt of
547 (AlgRep cons) -> cons
548 _ -> error "dataTypeConstrs"
551 -- | Gets the field labels of a constructor
552 constrFields :: Constr -> [String]
553 constrFields = confields
556 -- | Gets the fixity of a constructor
557 constrFixity :: Constr -> Fixity
558 constrFixity = confixity
562 ------------------------------------------------------------------------------
564 -- From strings to constr's and vice versa: all data types
566 ------------------------------------------------------------------------------
569 -- | Gets the string for a constructor
570 showConstr :: Constr -> String
571 showConstr = constring
574 -- | Lookup a constructor via a string
575 readConstr :: DataType -> String -> Maybe Constr
577 case dataTypeRep dt of
578 AlgRep cons -> idx cons
579 IntRep -> mkReadCon (\i -> (mkPrimCon dt str (IntConstr i)))
580 FloatRep -> mkReadCon (\f -> (mkPrimCon dt str (FloatConstr f)))
581 StringRep -> Just (mkStringConstr dt str)
585 -- Read a value and build a constructor
586 mkReadCon :: Read t => (t -> Constr) -> Maybe Constr
587 mkReadCon f = case (reads str) of
588 [(t,"")] -> Just (f t)
591 -- Traverse list of algebraic datatype constructors
592 idx :: [Constr] -> Maybe Constr
593 idx cons = let fit = filter ((==) str . showConstr) cons
599 ------------------------------------------------------------------------------
601 -- Convenience funtions: algebraic data types
603 ------------------------------------------------------------------------------
606 -- | Test for an algebraic type
607 isAlgType :: DataType -> Bool
608 isAlgType dt = case datarep dt of
613 -- | Gets the constructor for an index
614 indexConstr :: DataType -> ConIndex -> Constr
615 indexConstr dt idx = case datarep dt of
616 (AlgRep cs) -> cs !! (idx-1)
617 _ -> error "indexConstr"
620 -- | Gets the index of a constructor
621 constrIndex :: Constr -> ConIndex
622 constrIndex con = case constrRep con of
623 (AlgConstr idx) -> idx
624 _ -> error "constrIndex"
627 -- | Gets the maximum constructor index
628 maxConstrIndex :: DataType -> ConIndex
629 maxConstrIndex dt = case dataTypeRep dt of
630 AlgRep cs -> length cs
631 _ -> error "maxConstrIndex"
635 ------------------------------------------------------------------------------
637 -- Representation of primitive types
639 ------------------------------------------------------------------------------
642 -- | Constructs the Int type
643 mkIntType :: String -> DataType
644 mkIntType = mkPrimType IntRep
647 -- | Constructs the Float type
648 mkFloatType :: String -> DataType
649 mkFloatType = mkPrimType FloatRep
652 -- | Constructs the String type
653 mkStringType :: String -> DataType
654 mkStringType = mkPrimType StringRep
657 -- | Helper for mkIntType, mkFloatType, mkStringType
658 mkPrimType :: DataRep -> String -> DataType
659 mkPrimType dr str = DataType
665 -- Makes a constructor for primitive types
666 mkPrimCon :: DataType -> String -> ConstrRep -> Constr
667 mkPrimCon dt str cr = Constr
671 , confields = error "constrFields"
672 , confixity = error "constrFixity"
676 mkIntConstr :: DataType -> Integer -> Constr
677 mkIntConstr dt i = case datarep dt of
678 IntRep -> mkPrimCon dt (show i) (IntConstr i)
679 _ -> error "mkIntConstr"
682 mkFloatConstr :: DataType -> Double -> Constr
683 mkFloatConstr dt f = case datarep dt of
684 FloatRep -> mkPrimCon dt (show f) (FloatConstr f)
685 _ -> error "mkFloatConstr"
688 mkStringConstr :: DataType -> String -> Constr
689 mkStringConstr dt str = case datarep dt of
690 StringRep -> mkPrimCon dt str (StringConstr str)
691 _ -> error "mkStringConstr"
694 ------------------------------------------------------------------------------
696 -- Non-representations for non-presentable types
698 ------------------------------------------------------------------------------
701 -- | Constructs a non-representation
702 mkNorepType :: String -> DataType
703 mkNorepType str = DataType
709 -- | Test for a non-representable type
710 isNorepType :: DataType -> Bool
711 isNorepType dt = case datarep dt of
717 ------------------------------------------------------------------------------
719 -- Convenience for qualified type constructors
721 ------------------------------------------------------------------------------
724 -- | Gets the unqualified type constructor
725 -- Drop *.*.*... before name
727 tyconUQname :: String -> String
728 tyconUQname x = let x' = dropWhile (not . (==) '.') x
729 in if x' == [] then x else tyconUQname (tail x')
732 -- | Gets the module of a type constructor
733 -- Take *.*.*... before name
734 tyconModule :: String -> String
735 tyconModule x = let (a,b) = break ((==) '.') x
738 else a ++ tyconModule' (tail b)
740 tyconModule' x = let x' = tyconModule x
741 in if x' == "" then "" else ('.':x')