Data/Generics/Basics.hs

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