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