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