[project @ 2004-03-30 15:31:35 by ralf]
[packages/random.git] / Data / Generics / Basics.hs
1 -----------------------------------------------------------------------------
2 -- |
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)
6 --
7 -- Maintainer : libraries@haskell.org
8 -- Stability : experimental
9 -- Portability : non-portable
10 --
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.
14 --
15 -----------------------------------------------------------------------------
16
17 module Data.Generics.Basics (
18
19 -- * Module Data.Typeable re-exported for convenience
20 module Data.Typeable,
21
22 -- * The Data class for processing constructor applications
23 Data(
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
30 ),
31
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
39
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
46
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
53
54 -- * From strings to constr's and vice versa: all data types
55 showConstr, -- :: Constr -> String
56 readConstr, -- :: DataType -> String -> Maybe Constr
57
58 -- * Convenience funtions: algebraic data types
59 isAlgType, -- :: DataType -> Bool
60 indexConstr, -- :: DataType -> ConIndex -> Constr
61 constrIndex, -- :: Constr -> ConIndex
62 maxConstrIndex, -- :: DataType -> ConIndex
63
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
71
72 -- * Non-representations for non-presentable types
73 mkNorepType, -- :: String -> DataType
74 isNorepType, -- :: DataType -> Bool
75
76 -- * Convenience functions: take type constructors apart
77 tyconUQname, -- :: String -> String
78 tyconModule, -- :: String -> String
79
80 -- * Generic maps defined in terms of gfoldl
81 gmapT,
82 gmapQ,
83 gmapQl,
84 gmapQr,
85 gmapQi,
86 gmapM,
87 gmapMp,
88 gmapMo,
89
90 -- * Generic operation(s) defined in terms of gunfold
91 fromConstr, -- :: Constr -> a
92 fromConstrB, -- :: ... -> Constr -> a
93 fromConstrM -- :: Monad m => ... -> Constr -> m a
94
95 ) where
96
97
98 ------------------------------------------------------------------------------
99
100 #ifdef __HADDOCK__
101 import Prelude
102 #endif
103
104 import Data.Typeable
105 import Data.Maybe
106 import Control.Monad
107
108
109
110 ------------------------------------------------------------------------------
111 --
112 -- The Data class
113 --
114 ------------------------------------------------------------------------------
115
116 {-
117
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.
129
130 -}
131
132 class Typeable a => Data a where
133
134 {-
135
136 Folding constructor applications ("gfoldl")
137
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
150 fold.
151
152 -}
153
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)
157 -> a -> c a
158
159 -- Default definition for gfoldl
160 -- which copes immediately with basic datatypes
161 --
162 gfoldl _ z = z
163
164 -- | Unfolding constructor applications
165 gunfold :: (forall b r. Data b => c (b -> r) -> c r)
166 -> (forall r. r -> c r)
167 -> Constr
168 -> c a
169
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).
174 --
175 toConstr :: a -> Constr
176
177
178 -- | Provide access to list of all constructors
179 dataTypeOf :: a -> DataType
180
181
182
183 ------------------------------------------------------------------------------
184 --
185 -- Mediate types and type constructors
186 --
187 ------------------------------------------------------------------------------
188
189 -- | Mediate types and unary type constructors
190 dataCast1 :: Typeable1 t
191 => (forall a. Data a => c (t a))
192 -> Maybe (c a)
193 dataCast1 _ = Nothing
194
195 -- | Mediate types and binary type constructors
196 dataCast2 :: Typeable2 t
197 => (forall a b. (Data a, Data b) => c (t a b))
198 -> Maybe (c a)
199 dataCast2 _ = Nothing
200
201
202
203 ------------------------------------------------------------------------------
204 --
205 -- Typical generic maps defined in terms of gfoldl
206 --
207 ------------------------------------------------------------------------------
208
209 {-
210
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.
214
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.)
221
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.
226
227 -}
228
229
230 -- | A generic transformation that maps over the immediate subterms
231 gmapT :: (forall b. Data b => b -> b) -> a -> a
232
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.
236 --
237 gmapT f x = unID (gfoldl k ID x)
238 where
239 k (ID c) x = ID (c (f x))
240
241
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
245 where
246 k c x = CONST $ (unCONST c) `o` f x
247 z _ = CONST r
248
249 {-
250
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
263 unit.
264
265 -}
266
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
270 where
271 k (Qr c) x = Qr (\r -> c (f x `o` r))
272
273
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
277
278
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 }
282 where
283 k (Qi i' q) a = Qi (i'+1) (if i==i' then Just (f a) else q)
284 z f = Qi 0 Nothing
285
286
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
289
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 >>=.
293 --
294 gmapM f = gfoldl k return
295 where
296 k c x = do c' <- c
297 x' <- f x
298 return (c' x')
299
300
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
303
304 {-
305
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.
309
310 -}
311
312 gmapMp f x = unMp (gfoldl k z x) >>= \(x',b) ->
313 if b then return x' else mzero
314 where
315 z g = Mp (return (g,False))
316 k (Mp c) x
317 = Mp ( c >>= \(h,b) ->
318 (f x >>= \x' -> return (h x',True))
319 `mplus` return (h x,b)
320 )
321
322 -- | Transformation of one immediate subterm with success
323 gmapMo :: MonadPlus m => (forall a. Data a => a -> m a) -> a -> m a
324
325 {-
326
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.
332
333 -}
334
335 gmapMo f x = unMp (gfoldl k z x) >>= \(x',b) ->
336 if b then return x' else mzero
337 where
338 z g = Mp (return (g,False))
339 k (Mp c) x
340 = Mp ( c >>= \(h,b) -> if b
341 then return (h x,b)
342 else (f x >>= \x' -> return (h x',True))
343 `mplus` return (h x,b)
344 )
345
346
347 -- | The identity type constructor needed for the definition of gmapT
348 newtype ID x = ID { unID :: x }
349
350
351 -- | The constant type constructor needed for the definition of gmapQl
352 newtype CONST c a = CONST { unCONST :: c }
353
354
355 -- | Type constructor for adding counters to queries
356 data Qi q a = Qi Int (Maybe q)
357
358
359 -- | The type constructor used in definition of gmapQr
360 newtype Qr r a = Qr { unQr :: r -> r }
361
362
363 -- | The type constructor used in definition of gmapMp
364 newtype Mp m x = Mp { unMp :: m (x, Bool) }
365
366
367
368 ------------------------------------------------------------------------------
369 --
370 -- Generic unfolding
371 --
372 ------------------------------------------------------------------------------
373
374
375 -- | Build a term skeleton
376 fromConstr :: Data a => Constr -> a
377 fromConstr = fromConstrB undefined
378
379
380 -- | Build a term and use a generic function for subterms
381 fromConstrB :: Data a
382 => (forall a. Data a => a)
383 -> Constr
384 -> a
385 fromConstrB f = unID . gunfold k z
386 where
387 k c = ID (unID c f)
388 z = ID
389
390
391 -- | Monadic variation on \"fromConstrB\"
392 fromConstrM :: (Monad m, Data a)
393 => (forall a. Data a => m a)
394 -> Constr
395 -> m a
396 fromConstrM f = gunfold k z
397 where
398 k c = do { c' <- c; b <- f; return (c' b) }
399 z = return
400
401
402
403 ------------------------------------------------------------------------------
404 --
405 -- Datatype and constructor representations
406 --
407 ------------------------------------------------------------------------------
408
409
410 --
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.
414 --
415 data DataType = DataType
416 { tycon :: String
417 , datarep :: DataRep
418 }
419
420 deriving Show
421
422
423 -- | Representation of constructors
424 data Constr = Constr
425 { conrep :: ConstrRep
426 , constring :: String
427 , confields :: [String] -- for AlgRep only
428 , confixity :: Fixity -- for AlgRep only
429 , datatype :: DataType
430 }
431
432 instance Show Constr where
433 show = constring
434
435
436 -- | Equality of constructors
437 instance Eq Constr where
438 c == c' = constrRep c == constrRep c'
439
440
441 -- | Public representation of datatypes
442 data DataRep = AlgRep [Constr]
443 | IntRep
444 | FloatRep
445 | StringRep
446 | NoRep
447
448 deriving (Eq,Show)
449
450
451 -- | Public representation of constructors
452 data ConstrRep = AlgConstr ConIndex
453 | IntConstr Integer
454 | FloatConstr Double
455 | StringConstr String
456
457 deriving (Eq,Show)
458
459
460 --
461 -- | Unique index for datatype constructors.
462 -- | Textual order is respected. Starts at 1.
463 --
464 type ConIndex = Int
465
466
467 -- | Fixity of constructors
468 data Fixity = Prefix
469 | Infix -- Later: add associativity and precedence
470
471 deriving (Eq,Show)
472
473
474 ------------------------------------------------------------------------------
475 --
476 -- Observers for datatype representations
477 --
478 ------------------------------------------------------------------------------
479
480
481 -- | Gets the type constructor including the module
482 dataTypeName :: DataType -> String
483 dataTypeName = tycon
484
485
486
487 -- | Gets the public presentation of datatypes
488 dataTypeRep :: DataType -> DataRep
489 dataTypeRep = datarep
490
491
492 -- | Gets the datatype of a constructor
493 constrType :: Constr -> DataType
494 constrType = datatype
495
496
497 -- | Gets the public presentation of constructors
498 constrRep :: Constr -> ConstrRep
499 constrRep = conrep
500
501
502 -- | Look up a constructor by its representation
503 repConstr :: DataType -> ConstrRep -> Constr
504 repConstr dt cr =
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"
511
512
513
514 ------------------------------------------------------------------------------
515 --
516 -- Representations of algebraic data types
517 --
518 ------------------------------------------------------------------------------
519
520
521 -- | Constructs an algebraic datatype
522 mkDataType :: String -> [Constr] -> DataType
523 mkDataType str cs = DataType
524 { tycon = str
525 , datarep = AlgRep cs
526 }
527
528
529 -- | Constructs a constructor
530 mkConstr :: DataType -> String -> [String] -> Fixity -> Constr
531 mkConstr dt str fields fix =
532 Constr
533 { conrep = AlgConstr idx
534 , constring = str
535 , confields = fields
536 , confixity = fix
537 , datatype = dt
538 }
539 where
540 idx = head [ i | (c,i) <- dataTypeConstrs dt `zip` [1..],
541 showConstr c == str ]
542
543
544 -- | Gets the constructors
545 dataTypeConstrs :: DataType -> [Constr]
546 dataTypeConstrs dt = case datarep dt of
547 (AlgRep cons) -> cons
548 _ -> error "dataTypeConstrs"
549
550
551 -- | Gets the field labels of a constructor
552 constrFields :: Constr -> [String]
553 constrFields = confields
554
555
556 -- | Gets the fixity of a constructor
557 constrFixity :: Constr -> Fixity
558 constrFixity = confixity
559
560
561
562 ------------------------------------------------------------------------------
563 --
564 -- From strings to constr's and vice versa: all data types
565 --
566 ------------------------------------------------------------------------------
567
568
569 -- | Gets the string for a constructor
570 showConstr :: Constr -> String
571 showConstr = constring
572
573
574 -- | Lookup a constructor via a string
575 readConstr :: DataType -> String -> Maybe Constr
576 readConstr dt str =
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)
582 NoRep -> Nothing
583 where
584
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)
589 _ -> Nothing
590
591 -- Traverse list of algebraic datatype constructors
592 idx :: [Constr] -> Maybe Constr
593 idx cons = let fit = filter ((==) str . showConstr) cons
594 in if fit == []
595 then Nothing
596 else Just (head fit)
597
598
599 ------------------------------------------------------------------------------
600 --
601 -- Convenience funtions: algebraic data types
602 --
603 ------------------------------------------------------------------------------
604
605
606 -- | Test for an algebraic type
607 isAlgType :: DataType -> Bool
608 isAlgType dt = case datarep dt of
609 (AlgRep _) -> True
610 _ -> False
611
612
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"
618
619
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"
625
626
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"
632
633
634
635 ------------------------------------------------------------------------------
636 --
637 -- Representation of primitive types
638 --
639 ------------------------------------------------------------------------------
640
641
642 -- | Constructs the Int type
643 mkIntType :: String -> DataType
644 mkIntType = mkPrimType IntRep
645
646
647 -- | Constructs the Float type
648 mkFloatType :: String -> DataType
649 mkFloatType = mkPrimType FloatRep
650
651
652 -- | Constructs the String type
653 mkStringType :: String -> DataType
654 mkStringType = mkPrimType StringRep
655
656
657 -- | Helper for mkIntType, mkFloatType, mkStringType
658 mkPrimType :: DataRep -> String -> DataType
659 mkPrimType dr str = DataType
660 { tycon = str
661 , datarep = dr
662 }
663
664
665 -- Makes a constructor for primitive types
666 mkPrimCon :: DataType -> String -> ConstrRep -> Constr
667 mkPrimCon dt str cr = Constr
668 { datatype = dt
669 , conrep = cr
670 , constring = str
671 , confields = error "constrFields"
672 , confixity = error "constrFixity"
673 }
674
675
676 mkIntConstr :: DataType -> Integer -> Constr
677 mkIntConstr dt i = case datarep dt of
678 IntRep -> mkPrimCon dt (show i) (IntConstr i)
679 _ -> error "mkIntConstr"
680
681
682 mkFloatConstr :: DataType -> Double -> Constr
683 mkFloatConstr dt f = case datarep dt of
684 FloatRep -> mkPrimCon dt (show f) (FloatConstr f)
685 _ -> error "mkFloatConstr"
686
687
688 mkStringConstr :: DataType -> String -> Constr
689 mkStringConstr dt str = case datarep dt of
690 StringRep -> mkPrimCon dt str (StringConstr str)
691 _ -> error "mkStringConstr"
692
693
694 ------------------------------------------------------------------------------
695 --
696 -- Non-representations for non-presentable types
697 --
698 ------------------------------------------------------------------------------
699
700
701 -- | Constructs a non-representation
702 mkNorepType :: String -> DataType
703 mkNorepType str = DataType
704 { tycon = str
705 , datarep = NoRep
706 }
707
708
709 -- | Test for a non-representable type
710 isNorepType :: DataType -> Bool
711 isNorepType dt = case datarep dt of
712 NoRep -> True
713 _ -> False
714
715
716
717 ------------------------------------------------------------------------------
718 --
719 -- Convenience for qualified type constructors
720 --
721 ------------------------------------------------------------------------------
722
723
724 -- | Gets the unqualified type constructor
725 -- Drop *.*.*... before name
726 --
727 tyconUQname :: String -> String
728 tyconUQname x = let x' = dropWhile (not . (==) '.') x
729 in if x' == [] then x else tyconUQname (tail x')
730
731
732 -- | Gets the module of a type constructor
733 -- Take *.*.*... before name
734 tyconModule :: String -> String
735 tyconModule x = let (a,b) = break ((==) '.') x
736 in if b == ""
737 then b
738 else a ++ tyconModule' (tail b)
739 where
740 tyconModule' x = let x' = tyconModule x
741 in if x' == "" then "" else ('.':x')