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