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