[project @ 2004-11-26 11:58:18 by simonmar]
[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 import Prelude -- necessary to get dependencies right
101
102 import Data.Typeable
103 import Data.Maybe
104 import Control.Monad
105
106
107
108 ------------------------------------------------------------------------------
109 --
110 -- The Data class
111 --
112 ------------------------------------------------------------------------------
113
114 {-
115
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.
127
128 -}
129
130 class Typeable a => Data a where
131
132 {-
133
134 Folding constructor applications ("gfoldl")
135
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
148 fold.
149
150 -}
151
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)
155 -> a -> c a
156
157 -- Default definition for gfoldl
158 -- which copes immediately with basic datatypes
159 --
160 gfoldl _ z = z
161
162 -- | Unfolding constructor applications
163 gunfold :: (forall b r. Data b => c (b -> r) -> c r)
164 -> (forall r. r -> c r)
165 -> Constr
166 -> c a
167
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).
172 --
173 toConstr :: a -> Constr
174
175
176 -- | Provide access to list of all constructors
177 dataTypeOf :: a -> DataType
178
179
180
181 ------------------------------------------------------------------------------
182 --
183 -- Mediate types and type constructors
184 --
185 ------------------------------------------------------------------------------
186
187 -- | Mediate types and unary type constructors
188 dataCast1 :: Typeable1 t
189 => (forall a. Data a => c (t a))
190 -> Maybe (c a)
191 dataCast1 _ = Nothing
192
193 -- | Mediate types and binary type constructors
194 dataCast2 :: Typeable2 t
195 => (forall a b. (Data a, Data b) => c (t a b))
196 -> Maybe (c a)
197 dataCast2 _ = Nothing
198
199
200
201 ------------------------------------------------------------------------------
202 --
203 -- Typical generic maps defined in terms of gfoldl
204 --
205 ------------------------------------------------------------------------------
206
207 {-
208
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.
212
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.)
219
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.
224
225 -}
226
227
228 -- | A generic transformation that maps over the immediate subterms
229 gmapT :: (forall b. Data b => b -> b) -> a -> a
230
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.
234 --
235 gmapT f x = unID (gfoldl k ID x)
236 where
237 k (ID c) x = ID (c (f x))
238
239
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
243 where
244 k c x = CONST $ (unCONST c) `o` f x
245 z _ = CONST r
246
247 {-
248
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
261 unit.
262
263 -}
264
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
268 where
269 k (Qr c) x = Qr (\r -> c (f x `o` r))
270
271
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
275
276
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 }
280 where
281 k (Qi i' q) a = Qi (i'+1) (if i==i' then Just (f a) else q)
282 z f = Qi 0 Nothing
283
284
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
287
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 >>=.
291 --
292 gmapM f = gfoldl k return
293 where
294 k c x = do c' <- c
295 x' <- f x
296 return (c' x')
297
298
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
301
302 {-
303
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.
307
308 -}
309
310 gmapMp f x = unMp (gfoldl k z x) >>= \(x',b) ->
311 if b then return x' else mzero
312 where
313 z g = Mp (return (g,False))
314 k (Mp c) x
315 = Mp ( c >>= \(h,b) ->
316 (f x >>= \x' -> return (h x',True))
317 `mplus` return (h x,b)
318 )
319
320 -- | Transformation of one immediate subterm with success
321 gmapMo :: MonadPlus m => (forall a. Data a => a -> m a) -> a -> m a
322
323 {-
324
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.
330
331 -}
332
333 gmapMo f x = unMp (gfoldl k z x) >>= \(x',b) ->
334 if b then return x' else mzero
335 where
336 z g = Mp (return (g,False))
337 k (Mp c) x
338 = Mp ( c >>= \(h,b) -> if b
339 then return (h x,b)
340 else (f x >>= \x' -> return (h x',True))
341 `mplus` return (h x,b)
342 )
343
344
345 -- | The identity type constructor needed for the definition of gmapT
346 newtype ID x = ID { unID :: x }
347
348
349 -- | The constant type constructor needed for the definition of gmapQl
350 newtype CONST c a = CONST { unCONST :: c }
351
352
353 -- | Type constructor for adding counters to queries
354 data Qi q a = Qi Int (Maybe q)
355
356
357 -- | The type constructor used in definition of gmapQr
358 newtype Qr r a = Qr { unQr :: r -> r }
359
360
361 -- | The type constructor used in definition of gmapMp
362 newtype Mp m x = Mp { unMp :: m (x, Bool) }
363
364
365
366 ------------------------------------------------------------------------------
367 --
368 -- Generic unfolding
369 --
370 ------------------------------------------------------------------------------
371
372
373 -- | Build a term skeleton
374 fromConstr :: Data a => Constr -> a
375 fromConstr = fromConstrB undefined
376
377
378 -- | Build a term and use a generic function for subterms
379 fromConstrB :: Data a
380 => (forall a. Data a => a)
381 -> Constr
382 -> a
383 fromConstrB f = unID . gunfold k z
384 where
385 k c = ID (unID c f)
386 z = ID
387
388
389 -- | Monadic variation on \"fromConstrB\"
390 fromConstrM :: (Monad m, Data a)
391 => (forall a. Data a => m a)
392 -> Constr
393 -> m a
394 fromConstrM f = gunfold k z
395 where
396 k c = do { c' <- c; b <- f; return (c' b) }
397 z = return
398
399
400
401 ------------------------------------------------------------------------------
402 --
403 -- Datatype and constructor representations
404 --
405 ------------------------------------------------------------------------------
406
407
408 --
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.
412 --
413 data DataType = DataType
414 { tycon :: String
415 , datarep :: DataRep
416 }
417
418 deriving Show
419
420
421 -- | Representation of constructors
422 data Constr = Constr
423 { conrep :: ConstrRep
424 , constring :: String
425 , confields :: [String] -- for AlgRep only
426 , confixity :: Fixity -- for AlgRep only
427 , datatype :: DataType
428 }
429
430 instance Show Constr where
431 show = constring
432
433
434 -- | Equality of constructors
435 instance Eq Constr where
436 c == c' = constrRep c == constrRep c'
437
438
439 -- | Public representation of datatypes
440 data DataRep = AlgRep [Constr]
441 | IntRep
442 | FloatRep
443 | StringRep
444 | NoRep
445
446 deriving (Eq,Show)
447
448
449 -- | Public representation of constructors
450 data ConstrRep = AlgConstr ConIndex
451 | IntConstr Integer
452 | FloatConstr Double
453 | StringConstr String
454
455 deriving (Eq,Show)
456
457
458 --
459 -- | Unique index for datatype constructors.
460 -- | Textual order is respected. Starts at 1.
461 --
462 type ConIndex = Int
463
464
465 -- | Fixity of constructors
466 data Fixity = Prefix
467 | Infix -- Later: add associativity and precedence
468
469 deriving (Eq,Show)
470
471
472 ------------------------------------------------------------------------------
473 --
474 -- Observers for datatype representations
475 --
476 ------------------------------------------------------------------------------
477
478
479 -- | Gets the type constructor including the module
480 dataTypeName :: DataType -> String
481 dataTypeName = tycon
482
483
484
485 -- | Gets the public presentation of datatypes
486 dataTypeRep :: DataType -> DataRep
487 dataTypeRep = datarep
488
489
490 -- | Gets the datatype of a constructor
491 constrType :: Constr -> DataType
492 constrType = datatype
493
494
495 -- | Gets the public presentation of constructors
496 constrRep :: Constr -> ConstrRep
497 constrRep = conrep
498
499
500 -- | Look up a constructor by its representation
501 repConstr :: DataType -> ConstrRep -> Constr
502 repConstr dt cr =
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"
509
510
511
512 ------------------------------------------------------------------------------
513 --
514 -- Representations of algebraic data types
515 --
516 ------------------------------------------------------------------------------
517
518
519 -- | Constructs an algebraic datatype
520 mkDataType :: String -> [Constr] -> DataType
521 mkDataType str cs = DataType
522 { tycon = str
523 , datarep = AlgRep cs
524 }
525
526
527 -- | Constructs a constructor
528 mkConstr :: DataType -> String -> [String] -> Fixity -> Constr
529 mkConstr dt str fields fix =
530 Constr
531 { conrep = AlgConstr idx
532 , constring = str
533 , confields = fields
534 , confixity = fix
535 , datatype = dt
536 }
537 where
538 idx = head [ i | (c,i) <- dataTypeConstrs dt `zip` [1..],
539 showConstr c == str ]
540
541
542 -- | Gets the constructors
543 dataTypeConstrs :: DataType -> [Constr]
544 dataTypeConstrs dt = case datarep dt of
545 (AlgRep cons) -> cons
546 _ -> error "dataTypeConstrs"
547
548
549 -- | Gets the field labels of a constructor
550 constrFields :: Constr -> [String]
551 constrFields = confields
552
553
554 -- | Gets the fixity of a constructor
555 constrFixity :: Constr -> Fixity
556 constrFixity = confixity
557
558
559
560 ------------------------------------------------------------------------------
561 --
562 -- From strings to constr's and vice versa: all data types
563 --
564 ------------------------------------------------------------------------------
565
566
567 -- | Gets the string for a constructor
568 showConstr :: Constr -> String
569 showConstr = constring
570
571
572 -- | Lookup a constructor via a string
573 readConstr :: DataType -> String -> Maybe Constr
574 readConstr dt str =
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)
580 NoRep -> Nothing
581 where
582
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)
587 _ -> Nothing
588
589 -- Traverse list of algebraic datatype constructors
590 idx :: [Constr] -> Maybe Constr
591 idx cons = let fit = filter ((==) str . showConstr) cons
592 in if fit == []
593 then Nothing
594 else Just (head fit)
595
596
597 ------------------------------------------------------------------------------
598 --
599 -- Convenience funtions: algebraic data types
600 --
601 ------------------------------------------------------------------------------
602
603
604 -- | Test for an algebraic type
605 isAlgType :: DataType -> Bool
606 isAlgType dt = case datarep dt of
607 (AlgRep _) -> True
608 _ -> False
609
610
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"
616
617
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"
623
624
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"
630
631
632
633 ------------------------------------------------------------------------------
634 --
635 -- Representation of primitive types
636 --
637 ------------------------------------------------------------------------------
638
639
640 -- | Constructs the Int type
641 mkIntType :: String -> DataType
642 mkIntType = mkPrimType IntRep
643
644
645 -- | Constructs the Float type
646 mkFloatType :: String -> DataType
647 mkFloatType = mkPrimType FloatRep
648
649
650 -- | Constructs the String type
651 mkStringType :: String -> DataType
652 mkStringType = mkPrimType StringRep
653
654
655 -- | Helper for mkIntType, mkFloatType, mkStringType
656 mkPrimType :: DataRep -> String -> DataType
657 mkPrimType dr str = DataType
658 { tycon = str
659 , datarep = dr
660 }
661
662
663 -- Makes a constructor for primitive types
664 mkPrimCon :: DataType -> String -> ConstrRep -> Constr
665 mkPrimCon dt str cr = Constr
666 { datatype = dt
667 , conrep = cr
668 , constring = str
669 , confields = error "constrFields"
670 , confixity = error "constrFixity"
671 }
672
673
674 mkIntConstr :: DataType -> Integer -> Constr
675 mkIntConstr dt i = case datarep dt of
676 IntRep -> mkPrimCon dt (show i) (IntConstr i)
677 _ -> error "mkIntConstr"
678
679
680 mkFloatConstr :: DataType -> Double -> Constr
681 mkFloatConstr dt f = case datarep dt of
682 FloatRep -> mkPrimCon dt (show f) (FloatConstr f)
683 _ -> error "mkFloatConstr"
684
685
686 mkStringConstr :: DataType -> String -> Constr
687 mkStringConstr dt str = case datarep dt of
688 StringRep -> mkPrimCon dt str (StringConstr str)
689 _ -> error "mkStringConstr"
690
691
692 ------------------------------------------------------------------------------
693 --
694 -- Non-representations for non-presentable types
695 --
696 ------------------------------------------------------------------------------
697
698
699 -- | Constructs a non-representation
700 mkNorepType :: String -> DataType
701 mkNorepType str = DataType
702 { tycon = str
703 , datarep = NoRep
704 }
705
706
707 -- | Test for a non-representable type
708 isNorepType :: DataType -> Bool
709 isNorepType dt = case datarep dt of
710 NoRep -> True
711 _ -> False
712
713
714
715 ------------------------------------------------------------------------------
716 --
717 -- Convenience for qualified type constructors
718 --
719 ------------------------------------------------------------------------------
720
721
722 -- | Gets the unqualified type constructor
723 -- Drop *.*.*... before name
724 --
725 tyconUQname :: String -> String
726 tyconUQname x = let x' = dropWhile (not . (==) '.') x
727 in if x' == [] then x else tyconUQname (tail x')
728
729
730 -- | Gets the module of a type constructor
731 -- Take *.*.*... before name
732 tyconModule :: String -> String
733 tyconModule x = let (a,b) = break ((==) '.') x
734 in if b == ""
735 then b
736 else a ++ tyconModule' (tail b)
737 where
738 tyconModule' x = let x' = tyconModule x
739 in if x' == "" then "" else ('.':x')