[project @ 2003-07-28 15:03:05 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/>.
13 --
14 -----------------------------------------------------------------------------
15
16 module Data.Generics.Basics (
17
18 -- Module Data.Typeable re-exported for convenience
19 module Data.Typeable,
20
21 -- * The Data class for processing constructor applications
22 Data(
23 gfoldl, -- :: ... -> a -> c a
24 toConstr, -- :: a -> Constr
25 fromConstr, -- :: Constr -> a
26 dataTypeOf -- :: a -> DataType
27
28 ),
29
30 -- * Constructor representations
31 Constr, -- abstract, instance of: Eq, Show
32 ConIndex, -- alias for Int, start at 1
33 Fixity(..), -- instance of: Eq, Show
34 DataType, -- abstract, instance of: Show
35
36 -- * Constructing constructor representations
37 mkConstr, -- :: ConIndex -> String -> Fixity -> Constr
38 mkDataType, -- :: [Constr] -> DataType
39
40 -- * Observing constructor representations
41 conString, -- :: Constr -> String
42 conFixity, -- :: Constr -> Fixity
43 conIndex, -- :: Constr -> ConIndex
44 stringCon, -- :: DataType -> String -> Maybe Constr
45 indexCon, -- :: DataType -> ConIndex -> Constr
46 maxConIndex, -- :: DataType -> ConIndex
47 dataTypeCons, -- :: DataType -> [Constr]
48
49 -- * Generic maps defined in terms of gfoldl
50 gmapT,
51 gmapQ,
52 gmapQl,
53 gmapQr,
54 gmapM,
55 gmapMp,
56
57 -- * Generic unfolding defined in terms of gfoldl and fromConstr
58 gunfoldM -- :: Monad m => ... -> m a
59
60 ) where
61
62
63 ------------------------------------------------------------------------------
64
65
66 import Data.Typeable
67 import Data.Maybe
68 import Control.Monad
69
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
253 -- | The identity type constructor needed for the definition of gmapT
254 newtype ID x = ID { unID :: x }
255
256
257 -- | The constant type constructor needed for the definition of gmapQl
258 newtype CONST c a = CONST { unCONST :: c }
259
260
261 -- | The type constructor used in definition of gmapQr
262 newtype Qr r a = Qr { unQr :: r -> r }
263
264
265 -- | The type constructor used in definition of gmapMp
266 newtype Mp m x = Mp { unMp :: m (x, Bool) }
267
268
269
270 ------------------------------------------------------------------------------
271 --
272 -- Constructor representations
273 --
274 ------------------------------------------------------------------------------
275
276
277 -- | Representation of constructors
278 data Constr =
279 -- The prime case for proper datatype constructors
280 DataConstr ConIndex String Fixity
281
282 -- Provision for built-in types
283 | IntConstr Int
284 | IntegerConstr Integer
285 | FloatConstr Float
286 | CharConstr Char
287
288 -- Provision for any type that can be read/shown as string
289 | StringConstr String
290
291 -- Provision for function types
292 | FunConstr
293
294 deriving (Show, Typeable)
295
296 --
297 -- Equality of datatype constructors via index.
298 -- Use designated equalities for primitive types.
299 --
300 instance Eq Constr where
301 (DataConstr i1 _ _) == (DataConstr i2 _ _) = i1 == i2
302 (IntConstr i1) == (IntConstr i2) = i1 == i2
303 (IntegerConstr i1) == (IntegerConstr i2) = i1 == i2
304 (FloatConstr i1) == (FloatConstr i2) = i1 == i2
305 (CharConstr i1) == (CharConstr i2) = i1 == i2
306 (StringConstr i1) == (StringConstr i2) = i1 == i2
307 _ == _ = False
308
309
310 -- | Unique index for datatype constructors.
311 -- Textual order is respected. Starts at 1.
312 --
313 type ConIndex = Int
314
315
316 -- | Fixity of constructors
317 data Fixity = Prefix
318 | Infix -- Later: add associativity and precedence
319 deriving (Eq,Show)
320
321 -- | A package of constructor representations;
322 -- could be a list, an array, a balanced tree, or others.
323 --
324 data DataType =
325 -- The prime case for algebraic datatypes
326 DataType [Constr]
327
328 -- Provision for built-in types
329 | IntType
330 | IntegerType
331 | FloatType
332 | CharType
333
334 -- Provision for any type that can be read/shown as string
335 | StringType
336
337 -- Provision for function types
338 | FunType
339
340 deriving Show
341
342
343 ------------------------------------------------------------------------------
344 --
345 -- Constructing constructor representations
346 --
347 ------------------------------------------------------------------------------
348
349
350 -- | Make a representation for a datatype constructor
351 mkConstr :: ConIndex -> String -> Fixity -> Constr
352 -- ToDo: consider adding arity?
353 mkConstr = DataConstr
354
355 -- | Make a package of constructor representations
356 mkDataType :: [Constr] -> DataType
357 mkDataType = DataType
358
359
360 ------------------------------------------------------------------------------
361 --
362 -- Observing constructor representations
363 --
364 ------------------------------------------------------------------------------
365
366
367 -- | Turn a constructor into a string
368 conString :: Constr -> String
369 conString (DataConstr _ str _) = str
370 conString (IntConstr int) = show int
371 conString (IntegerConstr int) = show int
372 conString (FloatConstr real) = show real
373 conString (CharConstr char) = show char
374 conString (StringConstr str) = show str
375 conString FunConstr = "->"
376
377
378 -- | Determine fixity of a constructor;
379 -- undefined for primitive types.
380 conFixity :: Constr -> Fixity
381 conFixity (DataConstr _ _ fix) = fix
382 conFixity _ = undefined
383
384
385 -- | Determine index of a constructor.
386 -- Undefined for primitive types.
387 conIndex :: Constr -> ConIndex
388 conIndex (DataConstr idx _ _) = idx
389 conIndex _ = undefined
390
391
392 -- | Lookup a constructor via a string
393 stringCon :: DataType -> String -> Maybe Constr
394 stringCon (DataType cs) str = worker cs
395 where
396 worker [] = Nothing
397 worker (c:cs) =
398 case c of
399 (DataConstr _ str' _) -> if str == str'
400 then Just c
401 else worker cs
402 _ -> undefined -- other forms of Constr not valid here
403
404 stringCon IntType str = Just . IntConstr $ read str
405 stringCon IntegerType str = Just . IntegerConstr $ read str
406 stringCon FloatType str = Just . FloatConstr $ read str
407 stringCon CharType str = Just . CharConstr $ read str
408 stringCon StringType str = Just . StringConstr $ read str
409 stringCon FunType str = Just FunConstr
410
411
412 -- | Lookup a constructor by its index;
413 --- not defined for primitive types.
414 indexCon :: DataType -> ConIndex -> Constr
415 indexCon (DataType cs) idx = cs !! (idx-1)
416 indexCon _ _ = undefined -- otherwise
417
418
419 -- | Return maximum index;
420 -- 0 for primitive types
421 maxConIndex :: DataType -> ConIndex
422 maxConIndex (DataType cs) = length cs
423 maxConIndex _ = 0 -- otherwise
424
425
426 -- | Return all constructors in increasing order of indicies;
427 -- empty list for primitive types
428 dataTypeCons :: DataType -> [Constr]
429 dataTypeCons (DataType cs) = cs
430 dataTypeCons _ = [] -- otherwise
431
432
433 ------------------------------------------------------------------------------
434 --
435 -- Instances of the Data class for Prelude types
436 --
437 ------------------------------------------------------------------------------
438
439 -- Basic datatype Int; folding and unfolding is trivial
440 instance Data Int where
441 toConstr x = IntConstr x
442 fromConstr (IntConstr x) = x
443 dataTypeOf _ = IntType
444
445 -- Another basic datatype instance
446 instance Data Integer where
447 toConstr x = IntegerConstr x
448 fromConstr (IntegerConstr x) = x
449 dataTypeOf _ = IntegerType
450
451 -- Another basic datatype instance
452 instance Data Float where
453 toConstr x = FloatConstr x
454 fromConstr (FloatConstr x) = x
455 dataTypeOf _ = FloatType
456
457 -- Another basic datatype instance
458 instance Data Char where
459 toConstr x = CharConstr x
460 fromConstr (CharConstr x) = x
461 dataTypeOf _ = CharType
462
463 -- A basic datatype without a specific branch in Constr
464 instance Data Rational where
465 toConstr x = StringConstr (show x)
466 fromConstr (StringConstr x) = read x
467 dataTypeOf _ = StringType
468
469 --
470 -- Bool as the most trivial algebraic datatype;
471 -- define top-level definitions for representations.
472 --
473
474 falseConstr = mkConstr 1 "False" Prefix
475 trueConstr = mkConstr 2 "True" Prefix
476 boolDataType = mkDataType [falseConstr,trueConstr]
477
478 instance Data Bool where
479 toConstr False = falseConstr
480 toConstr True = trueConstr
481 fromConstr c = case conIndex c of
482 1 -> False
483 2 -> True
484 dataTypeOf _ = boolDataType
485
486
487 --
488 -- Lists as an example of a polymorphic algebraic datatype.
489 -- Cons-lists are terms with two immediate subterms.
490 --
491
492 nilConstr = mkConstr 1 "[]" Prefix
493 consConstr = mkConstr 2 "(:)" Infix
494 listDataType = mkDataType [nilConstr,consConstr]
495
496 instance Data a => Data [a] where
497 gfoldl f z [] = z []
498 gfoldl f z (x:xs) = z (:) `f` x `f` xs
499 toConstr [] = nilConstr
500 toConstr (_:_) = consConstr
501 fromConstr c = case conIndex c of
502 1 -> []
503 2 -> undefined:undefined
504 dataTypeOf _ = listDataType
505
506 --
507 -- The gmaps are given as an illustration.
508 -- This shows that the gmaps for lists are different from list maps.
509 --
510 gmapT f [] = []
511 gmapT f (x:xs) = (f x:f xs)
512 gmapQ f [] = []
513 gmapQ f (x:xs) = [f x,f xs]
514 gmapM f [] = return []
515 gmapM f (x:xs) = f x >>= \x' -> f xs >>= \xs' -> return (x':xs')
516
517
518 --
519 -- Yet another polymorphic datatype constructor
520 -- No surprises.
521 --
522
523 nothingConstr = mkConstr 1 "Nothing" Prefix
524 justConstr = mkConstr 2 "Just" Prefix
525 maybeDataType = mkDataType [nothingConstr,justConstr]
526
527 instance Data a => Data (Maybe a) where
528 gfoldl f z Nothing = z Nothing
529 gfoldl f z (Just x) = z Just `f` x
530 toConstr Nothing = nothingConstr
531 toConstr (Just _) = justConstr
532 fromConstr c = case conIndex c of
533 1 -> Nothing
534 2 -> Just undefined
535 dataTypeOf _ = maybeDataType
536
537 --
538 -- Yet another polymorphic datatype constructor.
539 -- No surprises.
540 --
541
542 pairConstr = mkConstr 1 "(,)" Infix
543 productDataType = mkDataType [pairConstr]
544
545 instance (Data a, Data b) => Data (a,b) where
546 gfoldl f z (a,b) = z (,) `f` a `f` b
547 toConstr _ = pairConstr
548 fromConstr c = case conIndex c of
549 1 -> (undefined,undefined)
550 dataTypeOf _ = productDataType
551
552
553 {-
554
555 We should better not FOLD over characters in a string for efficiency.
556 However, the following instance would clearly overlap with the
557 instance for polymorphic lists. Given the current scheme of allowing
558 overlapping instances, this would imply that ANY module that imports
559 Data.Generics would need to explicitly and generally allow overlapping
560 instances. This is prohibitive and calls for a more constrained model
561 of allowing overlapping instances. The present instance would be
562 sensible even more for UNFOLDING. In the definition of "gread"
563 (generic read --- based on unfolding), we succeed handling strings in a
564 special way by using a type-specific case for String.
565
566 instance Data String where
567 toConstr x = StringConstr x
568 fromConstr (StringConstr x) = x
569 dataTypeOf _ = StringType
570
571 -}
572
573 -- A last resort for functions
574 instance (Typeable a, Typeable b) => Data (a -> b) where
575 toConstr _ = FunConstr
576 fromConstr _ = undefined
577 dataTypeOf _ = FunType
578
579
580 ------------------------------------------------------------------------------
581 --
582 -- Generic unfolding
583 --
584 ------------------------------------------------------------------------------
585
586 -- | Construct an initial with undefined immediate subterms
587 -- and then map over the skeleton to fill in proper terms.
588 --
589 gunfoldM :: (Monad m, Data a)
590 => Constr
591 -> (forall a. Data a => m a)
592 -> m a
593 gunfoldM c f = gmapM (const f) $ fromConstr c