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