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