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