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