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