[project @ 2004-02-26 18:06:51 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 toConstr, -- :: a -> Constr
26 fromConstr, -- :: Constr -> a
27 dataTypeOf, -- :: a -> DataType
28 cast0to1, -- mediate types and unary type constructors
29 cast0to2 -- mediate types and binary type constructors
30 ),
31
32 -- * Constructor representations
33 Constr, -- abstract, instance of: Eq, Show
34 ConIndex, -- alias for Int, start at 1
35 Fixity(..), -- instance of: Eq, Show
36 DataType, -- abstract, instance of: Show
37
38 -- * Constructing constructor representations
39 mkConstr, -- :: ConIndex -> String -> Fixity -> Constr
40 mkDataType, -- :: [Constr] -> DataType
41
42 -- * Observing constructor representations
43 conString, -- :: Constr -> String
44 conFixity, -- :: Constr -> Fixity
45 conIndex, -- :: Constr -> ConIndex
46 stringCon, -- :: DataType -> String -> Maybe Constr
47 indexCon, -- :: DataType -> ConIndex -> Constr
48 maxConIndex, -- :: DataType -> ConIndex
49 dataTypeCons, -- :: DataType -> [Constr]
50
51 -- * Generic maps defined in terms of gfoldl
52 gmapT,
53 gmapQ,
54 gmapQl,
55 gmapQr,
56 gmapQi,
57 gmapM,
58 gmapMp,
59 gmapMo,
60
61 ) where
62
63
64 ------------------------------------------------------------------------------
65
66 #ifdef __HADDOCK__
67 import Prelude
68 #endif
69 import Data.Typeable
70 import Data.Maybe
71 import Control.Monad
72
73
74
75 ------------------------------------------------------------------------------
76 --
77 -- The Data class
78 --
79 ------------------------------------------------------------------------------
80
81 {-
82
83 The Data class comprehends a fundamental primitive "gfoldl" for
84 folding over constructor applications, say terms. This primitive can
85 be instantiated in several ways to map over the immediate subterms of
86 a term; see the "gmap" combinators later in this module. Indeed, a
87 generic programmer does not necessarily need to use the ingenious
88 gfoldl primitive but rather the intuitive "gmap" combinators. The
89 "gfoldl" primitive is completed by means to query top-level
90 constructors, to turn constructor representations into proper terms,
91 and to list all possible datatype constructors. This completion
92 allows us to serve generic programming scenarios like read, show,
93 equality, term generation.
94
95 -}
96
97 class Typeable a => Data a where
98
99 {-
100
101 Folding constructor applications ("gfoldl")
102
103 The combinator takes two arguments "f" and "z" to fold over a term
104 "x". The result type is defined in terms of "x" but variability is
105 achieved by means of type constructor "c" for the construction of the
106 actual result type. The purpose of the argument "z" is to define how
107 the empty constructor application is folded. So "z" is like the
108 neutral / start element for list folding. The purpose of the argument
109 "f" is to define how the nonempty constructor application is
110 folded. That is, "f" takes the folded "tail" of the constructor
111 application and its head, i.e., an immediate subterm, and combines
112 them in some way. See the Data instances in this file for an
113 illustration of "gfoldl". Conclusion: the type of gfoldl is a
114 headache, but operationally it is simple generalisation of a list
115 fold.
116
117 -}
118
119 -- | Left-associative fold operation for constructor applications
120 gfoldl :: (forall a b. Data a => c (a -> b) -> a -> c b)
121 -> (forall g. g -> c g)
122 -> a -> c a
123
124 -- Default definition for gfoldl
125 -- which copes immediately with basic datatypes
126 --
127 gfoldl _ z = z
128
129 -- | Obtaining the constructor from a given datum.
130 -- For proper terms, this is meant to be the top-level constructor.
131 -- Primitive datatypes are here viewed as potentially infinite sets of
132 -- values (i.e., constructors).
133 --
134 toConstr :: a -> Constr
135
136
137 -- | Building a term from a constructor
138 fromConstr :: Constr -> a
139
140
141 -- | Provide access to list of all constructors
142 dataTypeOf :: a -> DataType
143
144
145
146 ------------------------------------------------------------------------------
147 --
148 -- Mediate types and type constructors
149 --
150 ------------------------------------------------------------------------------
151
152 -- | Mediate types and unary type constructors
153 cast0to1 :: Typeable1 t
154 => (forall a. Data a => c (t a))
155 -> Maybe (c a)
156 cast0to1 _ = Nothing
157
158 -- | Mediate types and binary type constructors
159 cast0to2 :: Typeable2 t
160 => (forall a b. (Data a, Data b) => c (t a b))
161 -> Maybe (c a)
162 cast0to2 _ = Nothing
163
164
165
166 ------------------------------------------------------------------------------
167 --
168 -- Typical generic maps defined in terms of gfoldl
169 --
170 ------------------------------------------------------------------------------
171
172 {-
173
174 The combinators gmapT, gmapQ, gmapM, ... can all be defined in terms
175 of gfoldl. We provide corresponding default definitions leaving open
176 the opportunity to provide datatype-specific definitions.
177
178 (The inclusion of the gmap combinators as members of class Data allows
179 the programmer or the compiler to derive specialised, and maybe more
180 efficient code per datatype. Note: gfoldl is more higher-order than
181 the gmap combinators. This is subject to ongoing benchmarking
182 experiments. It might turn out that the gmap combinators will be moved
183 out of the class Data.)
184
185 Conceptually, the definition of the gmap combinators in terms of the
186 primitive gfoldl requires the identification of the gfoldl function
187 arguments. Technically, we also need to identify the type constructor
188 "c" for the construction of the result type from the folded term type.
189
190 -}
191
192
193 -- | A generic transformation that maps over the immediate subterms
194 gmapT :: (forall b. Data b => b -> b) -> a -> a
195
196 -- Use an identity datatype constructor ID (see below)
197 -- to instantiate the type constructor c in the type of gfoldl,
198 -- and perform injections ID and projections unID accordingly.
199 --
200 gmapT f x = unID (gfoldl k ID x)
201 where
202 k (ID c) x = ID (c (f x))
203
204
205 -- | A generic query with a left-associative binary operator
206 gmapQl :: (r -> r' -> r) -> r -> (forall a. Data a => a -> r') -> a -> r
207 gmapQl o r f = unCONST . gfoldl k z
208 where
209 k c x = CONST $ (unCONST c) `o` f x
210 z _ = CONST r
211
212 {-
213
214 In the definition of gmapQ? combinators, we use phantom type
215 constructors for the "c" in the type of "gfoldl" because the result
216 type of a query does not involve the (polymorphic) type of the term
217 argument. In the definition of gmapQl we simply use the plain constant
218 type constructor because gfoldl is left-associative anyway and so it
219 is readily suited to fold a left-associative binary operation over the
220 immediate subterms. In the definition of gmapQr, extra effort is
221 needed. We use a higher-order accumulation trick to mediate between
222 left-associative constructor application vs. right-associative binary
223 operation (e.g., (:)). When the query is meant to compute a value of
224 type r, then the result type withing generic folding is r -> r. So the
225 result of folding is a function to which we finally pass the right
226 unit.
227
228 -}
229
230 -- | A generic query with a right-associative binary operator
231 gmapQr :: (r' -> r -> r) -> r -> (forall a. Data a => a -> r') -> a -> r
232 gmapQr o r f x = unQr (gfoldl k (const (Qr id)) x) r
233 where
234 k (Qr c) x = Qr (\r -> c (f x `o` r))
235
236
237 -- | A generic query that processes the immediate subterms and returns a list
238 gmapQ :: (forall a. Data a => a -> u) -> a -> [u]
239 gmapQ f = gmapQr (:) [] f
240
241
242 -- | A generic query that processes one child by index (zero-based)
243 gmapQi :: Int -> (forall a. Data a => a -> u) -> a -> u
244 gmapQi i f x = case gfoldl k z x of { Qi _ (Just q) -> q }
245 where
246 k (Qi i' q) a = Qi (i'+1) (if i==i' then Just (f a) else q)
247 z f = Qi 0 Nothing
248
249
250 -- | A generic monadic transformation that maps over the immediate subterms
251 gmapM :: Monad m => (forall a. Data a => a -> m a) -> a -> m a
252
253 -- Use immediately the monad datatype constructor
254 -- to instantiate the type constructor c in the type of gfoldl,
255 -- so injection and projection is done by return and >>=.
256 --
257 gmapM f = gfoldl k return
258 where
259 k c x = do c' <- c
260 x' <- f x
261 return (c' x')
262
263
264 -- | Transformation of at least one immediate subterm does not fail
265 gmapMp :: MonadPlus m => (forall a. Data a => a -> m a) -> a -> m a
266
267 {-
268
269 The type constructor that we use here simply keeps track of the fact
270 if we already succeeded for an immediate subterm; see Mp below. To
271 this end, we couple the monadic computation with a Boolean.
272
273 -}
274
275 gmapMp f x = unMp (gfoldl k z x) >>= \(x',b) ->
276 if b then return x' else mzero
277 where
278 z g = Mp (return (g,False))
279 k (Mp c) x
280 = Mp ( c >>= \(h,b) ->
281 (f x >>= \x' -> return (h x',True))
282 `mplus` return (h x,b)
283 )
284
285 -- | Transformation of one immediate subterm with success
286 gmapMo :: MonadPlus m => (forall a. Data a => a -> m a) -> a -> m a
287
288 {-
289
290 We use the same pairing trick as for gmapMp,
291 i.e., we use an extra Bool component to keep track of the
292 fact whether an immediate subterm was processed successfully.
293 However, we cut of mapping over subterms once a first subterm
294 was transformed successfully.
295
296 -}
297
298 gmapMo f x = unMp (gfoldl k z x) >>= \(x',b) ->
299 if b then return x' else mzero
300 where
301 z g = Mp (return (g,False))
302 k (Mp c) x
303 = Mp ( c >>= \(h,b) -> if b
304 then return (h x,b)
305 else (f x >>= \x' -> return (h x',True))
306 `mplus` return (h x,b)
307 )
308
309
310 -- | The identity type constructor needed for the definition of gmapT
311 newtype ID x = ID { unID :: x }
312
313
314 -- | The constant type constructor needed for the definition of gmapQl
315 newtype CONST c a = CONST { unCONST :: c }
316
317
318 -- | Type constructor for adding counters to queries
319 data Qi q a = Qi Int (Maybe q)
320
321
322 -- | The type constructor used in definition of gmapQr
323 newtype Qr r a = Qr { unQr :: r -> r }
324
325
326 -- | The type constructor used in definition of gmapMp
327 newtype Mp m x = Mp { unMp :: m (x, Bool) }
328
329
330
331 ------------------------------------------------------------------------------
332 --
333 -- Constructor representations
334 --
335 ------------------------------------------------------------------------------
336
337
338 -- | Representation of constructors
339 data Constr =
340 -- The prime case for proper datatype constructors
341 DataConstr ConIndex String Fixity
342
343 -- Provision for built-in types
344 | IntConstr Int
345 | IntegerConstr Integer
346 | FloatConstr Float
347 | CharConstr Char
348
349 -- Provision for any type that can be read/shown as string
350 | StringConstr String
351
352 -- Provision for function types
353 | FunConstr
354
355 deriving (Show, Typeable)
356
357 --
358 -- Equality of datatype constructors via index.
359 -- Use designated equalities for primitive types.
360 --
361 instance Eq Constr where
362 (DataConstr i1 _ _) == (DataConstr i2 _ _) = i1 == i2
363 (IntConstr i1) == (IntConstr i2) = i1 == i2
364 (IntegerConstr i1) == (IntegerConstr i2) = i1 == i2
365 (FloatConstr i1) == (FloatConstr i2) = i1 == i2
366 (CharConstr i1) == (CharConstr i2) = i1 == i2
367 (StringConstr i1) == (StringConstr i2) = i1 == i2
368 _ == _ = False
369
370
371 -- | Unique index for datatype constructors.
372 -- Textual order is respected. Starts at 1.
373 --
374 type ConIndex = Int
375
376
377 -- | Fixity of constructors
378 data Fixity = Prefix
379 | Infix -- Later: add associativity and precedence
380 deriving (Eq,Show)
381
382 -- | A package of constructor representations;
383 -- could be a list, an array, a balanced tree, or others.
384 --
385 data DataType =
386 -- The prime case for algebraic datatypes
387 DataType [Constr]
388
389 -- Provision for built-in types
390 | IntType
391 | IntegerType
392 | FloatType
393 | CharType
394
395 -- Provision for any type that can be read/shown as string
396 | StringType
397
398 -- Provision for function types
399 | FunType
400
401 deriving Show
402
403
404 ------------------------------------------------------------------------------
405 --
406 -- Constructing constructor representations
407 --
408 ------------------------------------------------------------------------------
409
410
411 -- | Make a representation for a datatype constructor
412 mkConstr :: ConIndex -> String -> Fixity -> Constr
413 -- ToDo: consider adding arity?
414 mkConstr = DataConstr
415
416 -- | Make a package of constructor representations
417 mkDataType :: [Constr] -> DataType
418 mkDataType = DataType
419
420
421 ------------------------------------------------------------------------------
422 --
423 -- Observing constructor representations
424 --
425 ------------------------------------------------------------------------------
426
427
428 -- | Turn a constructor into a string
429 conString :: Constr -> String
430 conString (DataConstr _ str _) = str
431 conString (IntConstr int) = show int
432 conString (IntegerConstr int) = show int
433 conString (FloatConstr real) = show real
434 conString (CharConstr char) = show char
435 conString (StringConstr str) = show str
436 conString FunConstr = "->"
437
438
439 -- | Determine fixity of a constructor;
440 -- undefined for primitive types.
441 conFixity :: Constr -> Fixity
442 conFixity (DataConstr _ _ fix) = fix
443 conFixity _ = undefined
444
445
446 -- | Determine index of a constructor.
447 -- Undefined for primitive types.
448 conIndex :: Constr -> ConIndex
449 conIndex (DataConstr idx _ _) = idx
450 conIndex _ = undefined
451
452
453 -- | Lookup a constructor via a string
454 stringCon :: DataType -> String -> Maybe Constr
455 stringCon (DataType cs) str = worker cs
456 where
457 worker [] = Nothing
458 worker (c:cs) =
459 case c of
460 (DataConstr _ str' _) -> if str == str'
461 then Just c
462 else worker cs
463 _ -> undefined -- other forms of Constr not valid here
464
465 stringCon IntType str = Just . IntConstr $ read str
466 stringCon IntegerType str = Just . IntegerConstr $ read str
467 stringCon FloatType str = Just . FloatConstr $ read str
468 stringCon CharType str = Just . CharConstr $ read str
469 stringCon StringType str = Just . StringConstr $ read str
470 stringCon FunType str = Just FunConstr
471
472
473 -- | Lookup a constructor by its index;
474 --- not defined for primitive types.
475 indexCon :: DataType -> ConIndex -> Constr
476 indexCon (DataType cs) idx = cs !! (idx-1)
477 indexCon _ _ = undefined -- otherwise
478
479
480 -- | Return maximum index;
481 -- 0 for primitive types
482 maxConIndex :: DataType -> ConIndex
483 maxConIndex (DataType cs) = length cs
484 maxConIndex _ = 0 -- otherwise
485
486
487 -- | Return all constructors in increasing order of indicies;
488 -- empty list for primitive types
489 dataTypeCons :: DataType -> [Constr]
490 dataTypeCons (DataType cs) = cs
491 dataTypeCons _ = [] -- otherwise
492
493
494 ------------------------------------------------------------------------------
495 --
496 -- Instances of the Data class for Prelude types
497 --
498 ------------------------------------------------------------------------------
499
500 -- Basic datatype Int; folding and unfolding is trivial
501 instance Data Int where
502 toConstr x = IntConstr x
503 fromConstr (IntConstr x) = x
504 dataTypeOf _ = IntType
505
506 -- Another basic datatype instance
507 instance Data Integer where
508 toConstr x = IntegerConstr x
509 fromConstr (IntegerConstr x) = x
510 dataTypeOf _ = IntegerType
511
512 -- Another basic datatype instance
513 instance Data Float where
514 toConstr x = FloatConstr x
515 fromConstr (FloatConstr x) = x
516 dataTypeOf _ = FloatType
517
518 -- Another basic datatype instance
519 instance Data Char where
520 toConstr x = CharConstr x
521 fromConstr (CharConstr x) = x
522 dataTypeOf _ = CharType
523
524 -- A basic datatype without a specific branch in Constr
525 instance Data Rational where
526 toConstr x = StringConstr (show x)
527 fromConstr (StringConstr x) = read x
528 dataTypeOf _ = StringType
529
530 --
531 -- () as the most trivial algebraic datatype;
532 -- define top-level definitions for representations.
533 --
534
535 emptyTupleConstr = mkConstr 1 "()" Prefix
536 unitDataType = mkDataType [emptyTupleConstr]
537
538 instance Data () where
539 toConstr _ = emptyTupleConstr
540 fromConstr c | conIndex c == 1 = ()
541 dataTypeOf _ = unitDataType
542
543 --
544 -- Bool as another trivial algebraic datatype;
545 -- define top-level definitions for representations.
546 --
547
548 falseConstr = mkConstr 1 "False" Prefix
549 trueConstr = mkConstr 2 "True" Prefix
550 boolDataType = mkDataType [falseConstr,trueConstr]
551
552 instance Data Bool where
553 toConstr False = falseConstr
554 toConstr True = trueConstr
555 fromConstr c = case conIndex c of
556 1 -> False
557 2 -> True
558 dataTypeOf _ = boolDataType
559
560
561 --
562 -- Lists as an example of a polymorphic algebraic datatype.
563 -- Cons-lists are terms with two immediate subterms.
564 --
565
566 nilConstr = mkConstr 1 "[]" Prefix
567 consConstr = mkConstr 2 "(:)" Infix
568 listDataType = mkDataType [nilConstr,consConstr]
569
570 instance Data a => Data [a] where
571 gfoldl f z [] = z []
572 gfoldl f z (x:xs) = z (:) `f` x `f` xs
573 toConstr [] = nilConstr
574 toConstr (_:_) = consConstr
575 fromConstr c = case conIndex c of
576 1 -> []
577 2 -> undefined:undefined
578 dataTypeOf _ = listDataType
579 cast0to1 = cast1
580
581 --
582 -- The gmaps are given as an illustration.
583 -- This shows that the gmaps for lists are different from list maps.
584 --
585 gmapT f [] = []
586 gmapT f (x:xs) = (f x:f xs)
587 gmapQ f [] = []
588 gmapQ f (x:xs) = [f x,f xs]
589 gmapM f [] = return []
590 gmapM f (x:xs) = f x >>= \x' -> f xs >>= \xs' -> return (x':xs')
591
592
593 --
594 -- Yet another polymorphic datatype constructor
595 -- No surprises.
596 --
597
598 nothingConstr = mkConstr 1 "Nothing" Prefix
599 justConstr = mkConstr 2 "Just" Prefix
600 maybeDataType = mkDataType [nothingConstr,justConstr]
601
602 instance Data a => Data (Maybe a) where
603 gfoldl f z Nothing = z Nothing
604 gfoldl f z (Just x) = z Just `f` x
605 toConstr Nothing = nothingConstr
606 toConstr (Just _) = justConstr
607 fromConstr c = case conIndex c of
608 1 -> Nothing
609 2 -> Just undefined
610 dataTypeOf _ = maybeDataType
611 cast0to1 = cast1
612
613
614 --
615 -- Yet another polymorphic datatype constructor.
616 -- No surprises.
617 --
618
619 pairConstr = mkConstr 1 "(,)" Infix
620 productDataType = mkDataType [pairConstr]
621
622 instance (Data a, Data b) => Data (a,b) where
623 gfoldl f z (a,b) = z (,) `f` a `f` b
624 toConstr _ = pairConstr
625 fromConstr c = case conIndex c of
626 1 -> (undefined,undefined)
627 dataTypeOf _ = productDataType
628 cast0to2 = cast2
629
630
631 --
632 -- Yet another polymorphic datatype constructor.
633 -- No surprises.
634 --
635
636 tripleConstr = mkConstr 1 "(,,)" Infix
637 tripleDataType = mkDataType [tripleConstr]
638
639 instance (Data a, Data b, Data c) => Data (a,b,c) where
640 gfoldl f z (a,b,c) = z (,,) `f` a `f` b `f` c
641 toConstr _ = tripleConstr
642 fromConstr c = case conIndex c of
643 1 -> (undefined,undefined,undefined)
644 dataTypeOf _ = tripleDataType
645
646 quadrupleConstr = mkConstr 1 "(,,,)" Infix
647 quadrupleDataType = mkDataType [quadrupleConstr]
648
649 instance (Data a, Data b, Data c, Data d) => Data (a,b,c,d) where
650 gfoldl f z (a,b,c,d) = z (,,,) `f` a `f` b `f` c `f` d
651 toConstr _ = quadrupleConstr
652 fromConstr c = case conIndex c of
653 1 -> (undefined,undefined,undefined,undefined)
654 dataTypeOf _ = quadrupleDataType
655
656
657 --
658 -- Yet another polymorphic datatype constructor.
659 -- No surprises.
660 --
661
662 leftConstr = mkConstr 1 "Left" Prefix
663 rightConstr = mkConstr 2 "Right" Prefix
664 eitherDataType = mkDataType [leftConstr,rightConstr]
665
666 instance (Data a, Data b) => Data (Either a b) where
667 gfoldl f z (Left a) = z Left `f` a
668 gfoldl f z (Right a) = z Right `f` a
669 toConstr (Left _) = leftConstr
670 toConstr (Right _) = rightConstr
671 fromConstr c = case conIndex c of
672 1 -> Left undefined
673 2 -> Right undefined
674 dataTypeOf _ = eitherDataType
675 cast0to2 = cast2
676
677
678 {-
679
680 We should better not FOLD over characters in a string for efficiency.
681 However, the following instance would clearly overlap with the
682 instance for polymorphic lists. Given the current scheme of allowing
683 overlapping instances, this would imply that ANY module that imports
684 Data.Generics would need to explicitly and generally allow overlapping
685 instances. This is prohibitive and calls for a more constrained model
686 of allowing overlapping instances. The present instance would be
687 sensible even more for UNFOLDING. In the definition of "gread"
688 (generic read --- based on unfolding), we succeed handling strings in a
689 special way by using a type-specific case for String.
690
691 instance Data String where
692 toConstr x = StringConstr x
693 fromConstr (StringConstr x) = x
694 dataTypeOf _ = StringType
695
696 -}
697
698 -- A last resort for functions
699 instance (Data a, Data b) => Data (a -> b) where
700 toConstr _ = FunConstr
701 fromConstr _ = undefined
702 dataTypeOf _ = FunType
703 cast0to2 = cast2