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 ------------------------------------------------------------------------------
100 import Prelude -- necessary to get dependencies right
108 ------------------------------------------------------------------------------
112 ------------------------------------------------------------------------------
116 The Data class comprehends a fundamental primitive "gfoldl" for
117 folding over constructor applications, say terms. This primitive can
118 be instantiated in several ways to map over the immediate subterms of
119 a term; see the "gmap" combinators later in this module. Indeed, a
120 generic programmer does not necessarily need to use the ingenious
121 gfoldl primitive but rather the intuitive "gmap" combinators. The
122 "gfoldl" primitive is completed by means to query top-level
123 constructors, to turn constructor representations into proper terms,
124 and to list all possible datatype constructors. This completion
125 allows us to serve generic programming scenarios like read, show,
126 equality, term generation.
130 class Typeable a => Data a where
134 Folding constructor applications ("gfoldl")
136 The combinator takes two arguments "k" and "z" to fold over a term
137 "x". The result type is defined in terms of "x" but variability is
138 achieved by means of type constructor "c" for the construction of the
139 actual result type. The purpose of the argument "z" is to define how
140 the empty constructor application is folded. So "z" is like the
141 neutral / start element for list folding. The purpose of the argument
142 "k" is to define how the nonempty constructor application is
143 folded. That is, "k" takes the folded "tail" of the constructor
144 application and its head, i.e., an immediate subterm, and combines
145 them in some way. See the Data instances in this file for an
146 illustration of "gfoldl". Conclusion: the type of gfoldl is a
147 headache, but operationally it is simple generalisation of a list
152 -- | Left-associative fold operation for constructor applications
153 gfoldl :: (forall a b. Data a => c (a -> b) -> a -> c b)
154 -> (forall g. g -> c g)
157 -- Default definition for gfoldl
158 -- which copes immediately with basic datatypes
162 -- | Unfolding constructor applications
163 gunfold :: (forall b r. Data b => c (b -> r) -> c r)
164 -> (forall r. r -> c r)
168 -- | Obtaining the constructor from a given datum.
169 -- For proper terms, this is meant to be the top-level constructor.
170 -- Primitive datatypes are here viewed as potentially infinite sets of
171 -- values (i.e., constructors).
173 toConstr :: a -> Constr
176 -- | Provide access to list of all constructors
177 dataTypeOf :: a -> DataType
181 ------------------------------------------------------------------------------
183 -- Mediate types and type constructors
185 ------------------------------------------------------------------------------
187 -- | Mediate types and unary type constructors
188 dataCast1 :: Typeable1 t
189 => (forall a. Data a => c (t a))
191 dataCast1 _ = Nothing
193 -- | Mediate types and binary type constructors
194 dataCast2 :: Typeable2 t
195 => (forall a b. (Data a, Data b) => c (t a b))
197 dataCast2 _ = Nothing
201 ------------------------------------------------------------------------------
203 -- Typical generic maps defined in terms of gfoldl
205 ------------------------------------------------------------------------------
209 The combinators gmapT, gmapQ, gmapM, ... can all be defined in terms
210 of gfoldl. We provide corresponding default definitions leaving open
211 the opportunity to provide datatype-specific definitions.
213 (The inclusion of the gmap combinators as members of class Data allows
214 the programmer or the compiler to derive specialised, and maybe more
215 efficient code per datatype. Note: gfoldl is more higher-order than
216 the gmap combinators. This is subject to ongoing benchmarking
217 experiments. It might turn out that the gmap combinators will be moved
218 out of the class Data.)
220 Conceptually, the definition of the gmap combinators in terms of the
221 primitive gfoldl requires the identification of the gfoldl function
222 arguments. Technically, we also need to identify the type constructor
223 "c" for the construction of the result type from the folded term type.
228 -- | A generic transformation that maps over the immediate subterms
229 gmapT :: (forall b. Data b => b -> b) -> a -> a
231 -- Use an identity datatype constructor ID (see below)
232 -- to instantiate the type constructor c in the type of gfoldl,
233 -- and perform injections ID and projections unID accordingly.
235 gmapT f x = unID (gfoldl k ID x)
237 k (ID c) x = ID (c (f x))
240 -- | A generic query with a left-associative binary operator
241 gmapQl :: (r -> r' -> r) -> r -> (forall a. Data a => a -> r') -> a -> r
242 gmapQl o r f = unCONST . gfoldl k z
244 k c x = CONST $ (unCONST c) `o` f x
249 In the definition of gmapQ? combinators, we use phantom type
250 constructors for the "c" in the type of "gfoldl" because the result
251 type of a query does not involve the (polymorphic) type of the term
252 argument. In the definition of gmapQl we simply use the plain constant
253 type constructor because gfoldl is left-associative anyway and so it
254 is readily suited to fold a left-associative binary operation over the
255 immediate subterms. In the definition of gmapQr, extra effort is
256 needed. We use a higher-order accumulation trick to mediate between
257 left-associative constructor application vs. right-associative binary
258 operation (e.g., (:)). When the query is meant to compute a value of
259 type r, then the result type withing generic folding is r -> r. So the
260 result of folding is a function to which we finally pass the right
265 -- | A generic query with a right-associative binary operator
266 gmapQr :: (r' -> r -> r) -> r -> (forall a. Data a => a -> r') -> a -> r
267 gmapQr o r f x = unQr (gfoldl k (const (Qr id)) x) r
269 k (Qr c) x = Qr (\r -> c (f x `o` r))
272 -- | A generic query that processes the immediate subterms and returns a list
273 gmapQ :: (forall a. Data a => a -> u) -> a -> [u]
274 gmapQ f = gmapQr (:) [] f
277 -- | A generic query that processes one child by index (zero-based)
278 gmapQi :: Int -> (forall a. Data a => a -> u) -> a -> u
279 gmapQi i f x = case gfoldl k z x of { Qi _ q -> fromJust q }
281 k (Qi i' q) a = Qi (i'+1) (if i==i' then Just (f a) else q)
285 -- | A generic monadic transformation that maps over the immediate subterms
286 gmapM :: Monad m => (forall a. Data a => a -> m a) -> a -> m a
288 -- Use immediately the monad datatype constructor
289 -- to instantiate the type constructor c in the type of gfoldl,
290 -- so injection and projection is done by return and >>=.
292 gmapM f = gfoldl k return
299 -- | Transformation of at least one immediate subterm does not fail
300 gmapMp :: MonadPlus m => (forall a. Data a => a -> m a) -> a -> m a
304 The type constructor that we use here simply keeps track of the fact
305 if we already succeeded for an immediate subterm; see Mp below. To
306 this end, we couple the monadic computation with a Boolean.
310 gmapMp f x = unMp (gfoldl k z x) >>= \(x',b) ->
311 if b then return x' else mzero
313 z g = Mp (return (g,False))
315 = Mp ( c >>= \(h,b) ->
316 (f x >>= \x' -> return (h x',True))
317 `mplus` return (h x,b)
320 -- | Transformation of one immediate subterm with success
321 gmapMo :: MonadPlus m => (forall a. Data a => a -> m a) -> a -> m a
325 We use the same pairing trick as for gmapMp,
326 i.e., we use an extra Bool component to keep track of the
327 fact whether an immediate subterm was processed successfully.
328 However, we cut of mapping over subterms once a first subterm
329 was transformed successfully.
333 gmapMo f x = unMp (gfoldl k z x) >>= \(x',b) ->
334 if b then return x' else mzero
336 z g = Mp (return (g,False))
338 = Mp ( c >>= \(h,b) -> if b
340 else (f x >>= \x' -> return (h x',True))
341 `mplus` return (h x,b)
345 -- | The identity type constructor needed for the definition of gmapT
346 newtype ID x = ID { unID :: x }
349 -- | The constant type constructor needed for the definition of gmapQl
350 newtype CONST c a = CONST { unCONST :: c }
353 -- | Type constructor for adding counters to queries
354 data Qi q a = Qi Int (Maybe q)
357 -- | The type constructor used in definition of gmapQr
358 newtype Qr r a = Qr { unQr :: r -> r }
361 -- | The type constructor used in definition of gmapMp
362 newtype Mp m x = Mp { unMp :: m (x, Bool) }
366 ------------------------------------------------------------------------------
370 ------------------------------------------------------------------------------
373 -- | Build a term skeleton
374 fromConstr :: Data a => Constr -> a
375 fromConstr = fromConstrB undefined
378 -- | Build a term and use a generic function for subterms
379 fromConstrB :: Data a
380 => (forall a. Data a => a)
383 fromConstrB f = unID . gunfold k z
389 -- | Monadic variation on \"fromConstrB\"
390 fromConstrM :: (Monad m, Data a)
391 => (forall a. Data a => m a)
394 fromConstrM f = gunfold k z
396 k c = do { c' <- c; b <- f; return (c' b) }
401 ------------------------------------------------------------------------------
403 -- Datatype and constructor representations
405 ------------------------------------------------------------------------------
409 -- | Representation of datatypes.
410 -- | A package of constructor representations with names of type and module.
411 -- | The list of constructors could be an array, a balanced tree, or others.
413 data DataType = DataType
421 -- | Representation of constructors
423 { conrep :: ConstrRep
424 , constring :: String
425 , confields :: [String] -- for AlgRep only
426 , confixity :: Fixity -- for AlgRep only
427 , datatype :: DataType
430 instance Show Constr where
434 -- | Equality of constructors
435 instance Eq Constr where
436 c == c' = constrRep c == constrRep c'
439 -- | Public representation of datatypes
440 data DataRep = AlgRep [Constr]
449 -- | Public representation of constructors
450 data ConstrRep = AlgConstr ConIndex
453 | StringConstr String
459 -- | Unique index for datatype constructors.
460 -- | Textual order is respected. Starts at 1.
465 -- | Fixity of constructors
467 | Infix -- Later: add associativity and precedence
472 ------------------------------------------------------------------------------
474 -- Observers for datatype representations
476 ------------------------------------------------------------------------------
479 -- | Gets the type constructor including the module
480 dataTypeName :: DataType -> String
485 -- | Gets the public presentation of datatypes
486 dataTypeRep :: DataType -> DataRep
487 dataTypeRep = datarep
490 -- | Gets the datatype of a constructor
491 constrType :: Constr -> DataType
492 constrType = datatype
495 -- | Gets the public presentation of constructors
496 constrRep :: Constr -> ConstrRep
500 -- | Look up a constructor by its representation
501 repConstr :: DataType -> ConstrRep -> Constr
503 case (dataTypeRep dt, cr) of
504 (AlgRep cs, AlgConstr i) -> cs !! (i-1)
505 (IntRep, IntConstr i) -> mkIntConstr dt i
506 (FloatRep, FloatConstr f) -> mkFloatConstr dt f
507 (StringRep, StringConstr str) -> mkStringConstr dt str
508 _ -> error "repConstr"
512 ------------------------------------------------------------------------------
514 -- Representations of algebraic data types
516 ------------------------------------------------------------------------------
519 -- | Constructs an algebraic datatype
520 mkDataType :: String -> [Constr] -> DataType
521 mkDataType str cs = DataType
523 , datarep = AlgRep cs
527 -- | Constructs a constructor
528 mkConstr :: DataType -> String -> [String] -> Fixity -> Constr
529 mkConstr dt str fields fix =
531 { conrep = AlgConstr idx
538 idx = head [ i | (c,i) <- dataTypeConstrs dt `zip` [1..],
539 showConstr c == str ]
542 -- | Gets the constructors
543 dataTypeConstrs :: DataType -> [Constr]
544 dataTypeConstrs dt = case datarep dt of
545 (AlgRep cons) -> cons
546 _ -> error "dataTypeConstrs"
549 -- | Gets the field labels of a constructor
550 constrFields :: Constr -> [String]
551 constrFields = confields
554 -- | Gets the fixity of a constructor
555 constrFixity :: Constr -> Fixity
556 constrFixity = confixity
560 ------------------------------------------------------------------------------
562 -- From strings to constr's and vice versa: all data types
564 ------------------------------------------------------------------------------
567 -- | Gets the string for a constructor
568 showConstr :: Constr -> String
569 showConstr = constring
572 -- | Lookup a constructor via a string
573 readConstr :: DataType -> String -> Maybe Constr
575 case dataTypeRep dt of
576 AlgRep cons -> idx cons
577 IntRep -> mkReadCon (\i -> (mkPrimCon dt str (IntConstr i)))
578 FloatRep -> mkReadCon (\f -> (mkPrimCon dt str (FloatConstr f)))
579 StringRep -> Just (mkStringConstr dt str)
583 -- Read a value and build a constructor
584 mkReadCon :: Read t => (t -> Constr) -> Maybe Constr
585 mkReadCon f = case (reads str) of
586 [(t,"")] -> Just (f t)
589 -- Traverse list of algebraic datatype constructors
590 idx :: [Constr] -> Maybe Constr
591 idx cons = let fit = filter ((==) str . showConstr) cons
597 ------------------------------------------------------------------------------
599 -- Convenience funtions: algebraic data types
601 ------------------------------------------------------------------------------
604 -- | Test for an algebraic type
605 isAlgType :: DataType -> Bool
606 isAlgType dt = case datarep dt of
611 -- | Gets the constructor for an index
612 indexConstr :: DataType -> ConIndex -> Constr
613 indexConstr dt idx = case datarep dt of
614 (AlgRep cs) -> cs !! (idx-1)
615 _ -> error "indexConstr"
618 -- | Gets the index of a constructor
619 constrIndex :: Constr -> ConIndex
620 constrIndex con = case constrRep con of
621 (AlgConstr idx) -> idx
622 _ -> error "constrIndex"
625 -- | Gets the maximum constructor index
626 maxConstrIndex :: DataType -> ConIndex
627 maxConstrIndex dt = case dataTypeRep dt of
628 AlgRep cs -> length cs
629 _ -> error "maxConstrIndex"
633 ------------------------------------------------------------------------------
635 -- Representation of primitive types
637 ------------------------------------------------------------------------------
640 -- | Constructs the Int type
641 mkIntType :: String -> DataType
642 mkIntType = mkPrimType IntRep
645 -- | Constructs the Float type
646 mkFloatType :: String -> DataType
647 mkFloatType = mkPrimType FloatRep
650 -- | Constructs the String type
651 mkStringType :: String -> DataType
652 mkStringType = mkPrimType StringRep
655 -- | Helper for mkIntType, mkFloatType, mkStringType
656 mkPrimType :: DataRep -> String -> DataType
657 mkPrimType dr str = DataType
663 -- Makes a constructor for primitive types
664 mkPrimCon :: DataType -> String -> ConstrRep -> Constr
665 mkPrimCon dt str cr = Constr
669 , confields = error "constrFields"
670 , confixity = error "constrFixity"
674 mkIntConstr :: DataType -> Integer -> Constr
675 mkIntConstr dt i = case datarep dt of
676 IntRep -> mkPrimCon dt (show i) (IntConstr i)
677 _ -> error "mkIntConstr"
680 mkFloatConstr :: DataType -> Double -> Constr
681 mkFloatConstr dt f = case datarep dt of
682 FloatRep -> mkPrimCon dt (show f) (FloatConstr f)
683 _ -> error "mkFloatConstr"
686 mkStringConstr :: DataType -> String -> Constr
687 mkStringConstr dt str = case datarep dt of
688 StringRep -> mkPrimCon dt str (StringConstr str)
689 _ -> error "mkStringConstr"
692 ------------------------------------------------------------------------------
694 -- Non-representations for non-presentable types
696 ------------------------------------------------------------------------------
699 -- | Constructs a non-representation
700 mkNorepType :: String -> DataType
701 mkNorepType str = DataType
707 -- | Test for a non-representable type
708 isNorepType :: DataType -> Bool
709 isNorepType dt = case datarep dt of
715 ------------------------------------------------------------------------------
717 -- Convenience for qualified type constructors
719 ------------------------------------------------------------------------------
722 -- | Gets the unqualified type constructor
723 -- Drop *.*.*... before name
725 tyconUQname :: String -> String
726 tyconUQname x = let x' = dropWhile (not . (==) '.') x
727 in if x' == [] then x else tyconUQname (tail x')
730 -- | Gets the module of a type constructor
731 -- Take *.*.*... before name
732 tyconModule :: String -> String
733 tyconModule x = let (a,b) = break ((==) '.') x
736 else a ++ tyconModule' (tail b)
738 tyconModule' x = let x' = tyconModule x
739 in if x' == "" then "" else ('.':x')