Data/Generics.hs

   1 -----------------------------------------------------------------------------
   2 -- |
   3 -- Module      :  Data.Generics
   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, ralf@cwi.nl
   8 -- Stability   :  experimental
   9 -- Portability :  non-portable
  10 --
  11 -- Generic programming in Haskell;
  12 -- see <http://www.cs.vu.nl/boilerplate>.
  13 --
  14 -----------------------------------------------------------------------------
  15
  16 module Data.Generics (
  17
  18         -- The Typeable class and the type-safe cast operation;
  19         -- re-exported for convenience
  20         Typeable(..), cast,
  21
  22         -- * Prime types of generic functions
  23         GenericT, GenericQ, GenericM,
  24
  25         -- * Combinators to \"make\" generic functions
  26         mkT, mkQ, mkM, extT, extQ, extM, sameType,
  27
  28         -- * The Data class for folding and unfolding constructor applications
  29         Data( gmapT,
  30               gmapQ,
  31               gmapM,
  32               gfoldl,
  33               conOf,
  34               consOf,
  35               gunfold
  36             ),
  37
  38         -- * The Constr datatype for describing datatype constructors
  39         Constr(..),
  40
  41         -- * Frequently used generic traversal schemes
  42         everywhere,
  43         everywhere',
  44         everywhereBut,
  45         everywhereM,
  46         everything,
  47         something,
  48         synthesize,
  49
  50         -- * Generic operations such as show, equality, read
  51         glength,
  52         gnodecount,
  53         gtypecount,
  54         gshow,
  55         geq,
  56         gzip,
  57         gread
  58
  59 #ifndef __HADDOCK__
  60         ,
  61         -- Data types for the sum-of-products type encoding;
  62         -- included for backwards compatibility; maybe obsolete
  63         (:*:)(..), (:+:)(..), Unit(..)
  64 #endif
  65
  66  ) where
  67
  68 ------------------------------------------------------------------------------
  69
  70 import Prelude  -- So that 'make depend' works
  71
  72 #ifdef __GLASGOW_HASKELL__
  73 #ifndef __HADDOCK__
  74 import GHC.Base ( (:*:)(..), (:+:)(..), Unit(..) )
  75 #endif
  76 #endif
  77
  78 import Data.Dynamic
  79 import Control.Monad
  80
  81
  82
  83 ------------------------------------------------------------------------------
  84 --
  85 --      Prime types of generic functions
  86 --
  87 ------------------------------------------------------------------------------
  88
  89 -- | Generic transformations,
  90 --   i.e., take an \"a\" and return an \"a\"
  91 --
  92 type GenericT = forall a. Data a => a -> a
  93
  94
  95 -- | Generic queries of type "r",
  96 --   i.e., take any \"a\" and return an \"r\"
  97 --
  98 type GenericQ r = forall a. Data a => a -> r
  99
 100
 101 -- | Generic monadic transformations,
 102 --   i.e., take an \"a\" and compute an \"a\"
 103 --
 104 type GenericM m = forall a. Data a => a -> m a
 105
 106
 107
 108 ------------------------------------------------------------------------------
 109 --
 110 --      Combinators to "make" generic functions
 111 --      We use type-safe cast in a number of ways to make generic functions.
 112 --
 113 ------------------------------------------------------------------------------
 114
 115 -- | Make a generic transformation;
 116 --   start from a type-specific case;
 117 --   preserve the term otherwise
 118 --
 119 mkT :: (Typeable a, Typeable b) => (b -> b) -> a -> a
 120 mkT f = case cast f of
 121                Just g -> g
 122                Nothing -> id
 123
 124
 125 -- | Make a generic query;
 126 --   start from a type-specific case;
 127 --   return a constant otherwise
 128 --
 129 mkQ :: (Typeable a, Typeable b) => r -> (b -> r) -> a -> r
 130 (r `mkQ` br) a = case cast a of
 131                     Just b  -> br b
 132                     Nothing -> r
 133
 134
 135 -- | Make a generic monadic transformation;
 136 --   start from a type-specific case;
 137 --   resort to return otherwise
 138 --
 139 mkM :: (Typeable a, Typeable b, Typeable (m a), Typeable (m b), Monad m)
 140     => (b -> m b) -> a -> m a
 141 mkM f = case cast f of
 142           Just g  -> g
 143           Nothing -> return
 144
 145
 146 -- | Extend a generic transformation by a type-specific case
 147 extT :: (Typeable a, Typeable b) => (a -> a) -> (b -> b) -> a -> a
 148 extT f g = case cast g of
 149               Just g' -> g'
 150               Nothing -> f
 151
 152
 153 -- | Extend a generic query by a type-specific case
 154 extQ :: (Typeable a, Typeable b) => (a -> q) -> (b -> q) -> a -> q
 155 extQ f g a = case cast a of
 156                 Just b -> g b
 157                 Nothing -> f a
 158
 159
 160 -- | Extend a generic monadic transformation by a type-specific case
 161 extM :: (Typeable a, Typeable b, Typeable (m a), Typeable (m b), Monad m)
 162        => (a -> m a) -> (b -> m b) -> a -> m a
 163 extM f g = case cast g of
 164               Just g' -> g'
 165               Nothing -> f
 166
 167
 168 -- | Test for two objects to agree on the type
 169 sameType :: (Typeable a, Typeable b) => a -> b -> Bool
 170 sameType (_::a) = maybe False (\(_::a) -> True) . cast
 171
 172
 173
 174 ------------------------------------------------------------------------------
 175 --
 176 --      The Data class
 177 --
 178 ------------------------------------------------------------------------------
 179
 180 class Typeable a => Data a where
 181
 182   -- | A generic transformation that maps over the immediate subterms
 183   gmapT   :: (forall b. Data b => b -> b) -> a -> a
 184
 185   -- | A generic query that processes the immediate subterms and returns a list
 186   gmapQ   :: (forall a. Data a => a -> u) -> a -> [u]
 187
 188   -- | A monadic variation on generic transformation
 189   gmapM   :: Monad m => (forall a. Data a => a -> m a) -> a -> m a
 190
 191   -- | Left-associative fold operation for constructor applications
 192   gfoldl  :: (forall a b. Data a => c (a -> b) -> a -> c b)
 193           -> (forall g. g -> c g)
 194           -> a -> c a
 195
 196   -- | Obtain the constructor from a given term
 197   conOf   :: a -> Constr
 198
 199   -- | List all constructors for a given type
 200   consOf  :: a -> [Constr]
 201
 202   -- | Unfold operation to build terms from constructors and others
 203   gunfold :: (forall a b. Data a => c (a -> b) -> c b)
 204           -> (forall g. g -> c g)
 205           -> Constr
 206           -> c a
 207
 208   -- Default definition for gfoldl
 209   -- which copes immediately with basic datatypes
 210   --
 211   gfoldl _ z = z
 212
 213
 214 {-
 215
 216 The combinators gmapT, gmapQ, gmapM can all be defined in terms of
 217 gfoldl. We provide corresponding default definitions leaving open the
 218 opportunity to provide datatype-specific definitions if needed.
 219
 220 (Also, the inclusion of the gmap combinators as members of class Data
 221 allows the programmer or the compiler to derive specialised, and maybe
 222 more efficient code per datatype. Note: gfoldl is more higher-order
 223 than the gmap combinators. This is subject to ongoing benchmarking
 224 experiments.)
 225
 226 Conceptually, the definition of the gmap combinators in terms of the
 227 primitive gfoldl requires the identification of the gfoldl function
 228 arguments. Technically, we also need to identify the type constructor
 229 c used all over the type of gfoldl. We give the default definitions in
 230 the order of increasing headache.
 231
 232 -}
 233
 234   -- Use immediately the monad datatype constructor
 235   -- to instantiate the type constructor c in the type of gfoldl,
 236   -- so injection and projection is done by return and >>=.
 237   --
 238   gmapM f = gfoldl k return
 239           where
 240             k c x = do c' <- c
 241                        x' <- f x
 242                        return (c' x')
 243
 244   -- Use an identity datatype constructor ID (see below)
 245   -- to instantiate the type constructor c in the type of gfoldl,
 246   -- and perform injections ID and projections unID accordingly.
 247   --
 248   gmapT f x = unID (gfoldl k ID x)
 249     where
 250       k (ID c) x = ID (c (f x))
 251
 252   -- Use a phantom + function datatype constructor Q (see below),
 253   -- to instantiate the type constructor c in the type of gfoldl,
 254   -- and perform injections Q and projections unQ accordingly.
 255   --
 256   gmapQ f x = unQ (gfoldl k (const (Q id)) x) []
 257     where
 258       k (Q c) x = Q (\rs -> c (f x : rs))
 259
 260
 261 -- | The identity type constructor needed for the definition of gmapT
 262 newtype ID x = ID { unID :: x }
 263
 264
 265 -- | A phantom datatype constructor used in definition of gmapQ;
 266 --   the function-typed component is needed to mediate between
 267 --   left-associative constructor application vs. right-associative lists.
 268 --
 269 newtype Q r a = Q { unQ  :: [r] -> [r] }
 270
 271
 272
 273 ------------------------------------------------------------------------------
 274 --
 275 --      The Constr datatype for describing datatype constructors
 276 --      To be extended by fixity, associativity, and maybe others.
 277 --
 278 ------------------------------------------------------------------------------
 279
 280 -- | Description of datatype constructors
 281 data Constr = Constr { conString :: String }
 282
 283
 284 {-
 285
 286 It is interesting to observe that we can determine the arity of a
 287 constructor without further meta-information. To this end, we use
 288 gunfold to construct a term from a given constructor while leaving the
 289 subterms undefined. Here we instantiate the type constructor c of the
 290 gunfold type by the identity type constructor ID. In a subsequent step
 291 we determine the number of subterms by folding as captured in the
 292 generic operation glength elsewhere in this module. Note that we need
 293 an extra argument to specify the intended type of the constructor.
 294
 295 -}
 296
 297 garity :: Data a => (a -> ()) -> Constr -> Int
 298 garity (_::a->()) = glength
 299                   . (unID :: ID a -> a)
 300                   . gunfold bottom ID
 301   where
 302     bottom = (\f -> ID (f undefined)) . unID
 303
 304
 305
 306 ------------------------------------------------------------------------------
 307 --
 308 --      Frequently used generic traversal schemes
 309 --
 310 ------------------------------------------------------------------------------
 311
 312 -- | Apply a transformation everywhere in bottom-up manner
 313 everywhere :: (forall a. Data a => a -> a)
 314            -> (forall a. Data a => a -> a)
 315
 316 -- use gmapT to recurse into immediate subterms;
 317 -- recall: gmapT preserves the outermost constructor;
 318 -- post-process recursively transformed result via f
 319 --
 320 everywhere f = f . gmapT (everywhere f)
 321
 322
 323 -- | Apply a transformation everywhere in top-down manner
 324 everywhere' :: (forall a. Data a => a -> a)
 325             -> (forall a. Data a => a -> a)
 326
 327 -- Arguments of (.) are flipped compared to everywhere
 328 everywhere' f = gmapT (everywhere' f) . f
 329
 330
 331 -- | Variation on everywhere with an extra stop condition
 332 everywhereBut :: GenericQ Bool -> GenericT -> GenericT
 333
 334 -- Guarded to let traversal cease if predicate q holds for x
 335 everywhereBut q f x
 336     | q x       = x
 337     | otherwise = f (gmapT (everywhereBut q f) x)
 338
 339
 340 -- | Monadic variation on everywhere
 341 everywhereM :: Monad m => GenericM m -> GenericM m
 342
 343 -- Bottom-up order is also reflected in order of do-actions
 344 everywhereM f x = do x' <- gmapM (everywhereM f) x
 345                      f x'
 346
 347
 348 -- | Summarise all nodes in top-down, left-to-right order
 349 everything :: (r -> r -> r) -> GenericQ r -> GenericQ r
 350
 351 -- Apply f to x to summarise top-level node;
 352 -- use gmapQ to recurse into immediate subterms;
 353 -- use ordinary foldl to reduce list of intermediate results
 354 --
 355 everything k f x
 356      = foldl k (f x) (gmapQ (everything k f) x)
 357
 358
 359 -- | Look up a subterm by means of a maybe-typed filter
 360 something :: GenericQ (Maybe u) -> GenericQ (Maybe u)
 361
 362 -- "something" can be defined in terms of "everything"
 363 -- when a suitable "choice" operator is used for reduction
 364 --
 365 something = everything orElse
 366
 367
 368 -- Left-biased choice on maybes (non-strict in right argument)
 369 orElse :: Maybe a -> Maybe a -> Maybe a
 370 x `orElse` y = maybe y Just x
 371
 372
 373 -- Another definition of orElse
 374 -- where the folding over maybies as defined by maybe is inlined
 375 -- to ease readability
 376 --
 377 x `orElse'` y = case x of
 378                   Just _  -> x
 379                   Nothing -> y
 380
 381
 382
 383
 384 -- | Bottom-up synthesis of a data structure;
 385 --   1st argument z is the initial element for the synthesis;
 386 --   2nd argument o is for reduction of results from subterms;
 387 --   3rd argument f updates the sythesised data according to the given term
 388 --
 389 synthesize :: s  -> (s -> s -> s) -> GenericQ (s -> s) -> GenericQ s
 390 synthesize z o f x = f x (foldr o z (gmapQ (synthesize z o f) x))
 391
 392
 393
 394 -----------------------------------------------------------------------------
 395 --
 396 --      "Twin" variations on gmapT, gmapQ. gmapM,
 397 --      i.e., these combinators take two terms at the same time.
 398 --      They are needed for multi-parameter traversal as generic equality.
 399 --      They are not exported.
 400 --
 401 -----------------------------------------------------------------------------
 402
 403 {-
 404
 405 We need type constructors for twin traversal as we needed type
 406 constructor for the ordinary gmap combinators. These type constructors
 407 again serve for the instantiation of the type constructor c used in
 408 the definition of gfoldl. The type constructors for twin traversal are
 409 elaborations of the type constructors ID, Q and monads that were used
 410 for the ordinary gmap combinators. More precisely, we use a pairing
 411 technique to always attach an additional component to the results of
 412 folding. This additional component carries the list of generic
 413 functions to be used for the intermediate subterms encountered during
 414 folding.
 415
 416 -}
 417
 418 newtype TT r a = TT { unTT :: (a,[GenericT']) }
 419 newtype TQ r a = TQ { unTQ :: ([r]->[r],[GenericQ' r]) }
 420 newtype TM m a = TM { unTM :: (m a,[GenericM' m]) }
 421
 422
 423 -- First-class polymorphic versions of GenericT/GenericQ/GenericM;
 424 -- they are referenced in TQ amd TM above
 425 --
 426 data GenericT' = T' { unT' :: forall a. Data a => a -> a }
 427 data GenericQ' u = Q' { unQ' :: forall a. Data a => a -> u }
 428 data Monad m => GenericM' m = M' { unM' :: forall a. Data a => a -> m a }
 429
 430
 431 {-
 432
 433 A twin variation on gmapT, where the pattern "GenericQ GenericT"
 434 expresses that the argument terms x and y are processed rather
 435 independently. So firstly, x is "queried" with a generic
 436 transformation as intermediate result, and secondly, this generic
 437 transformation is applied to y.
 438
 439 -}
 440
 441 tmapT :: GenericQ GenericT -> GenericQ GenericT
 442 tmapT g x y = fst (unTT (gfoldl k z y))
 443   where
 444     k (TT (f,l)) x = TT (f (unT' (head l) x),tail l)
 445     z f            = TT (f,gmapQ (\x -> T' (g x)) x)
 446
 447
 448
 449 -- A twin variation on gmapQ
 450
 451 tmapQ :: forall r.
 452          (forall a b. (Data a, Data b) => a -> b -> r)
 453       -> (forall a b. (Data a, Data b) => a -> b -> [r])
 454
 455 tmapQ g x y = fst (unTQ (gfoldl k z y)) []
 456     where
 457       k (TQ (c,l)) x = TQ (\rs -> c (unQ' (head l) x:rs), tail l)
 458       z _            = TQ (id,gmapQ (\x -> Q' (g x)) x)
 459
 460
 461 -- A twin variation on gmapM
 462
 463 tmapM :: forall m. Monad m
 464       => (forall a b. (Data a, Data b) => a -> b -> m b)
 465       -> (forall a b. (Data a, Data b) => a -> b -> m b)
 466 tmapM g x y = fst (unTM (gfoldl k z y))
 467   where
 468     k (TM (f,l)) x = TM (f >>= \f' -> unM' (head l) x >>= return . f',tail l)
 469     z f            = TM (return f,gmapQ (\x -> M' (g x)) x)
 470
 471
 472
 473 ------------------------------------------------------------------------------
 474 --
 475 --      Generic operations such as show, equality, read
 476 --
 477 ------------------------------------------------------------------------------
 478
 479 -- | Count the number of immediate subterms of the given term
 480 glength :: GenericQ Int
 481 glength = length . gmapQ (const ())
 482
 483
 484 -- | Determine the number of all nodes in a given term
 485 gnodecount :: GenericQ Int
 486 gnodecount = everything (+) (const 1)
 487
 488
 489 -- | Determine the number of nodes of a given type in a given term
 490 gtypecount :: Typeable a => (a -> ()) -> GenericQ Int
 491 gtypecount f = everything (+) (0 `mkQ` (const 1 . f))
 492
 493
 494 -- | Generic show: an alternative to "deriving Show"
 495 gshow :: Data a => a -> String
 496
 497 -- This is a prefix-show using surrounding "(" and ")",
 498 -- where we recurse into subterms with gmapQ.
 499 --
 500 gshow t =    "("
 501           ++ conString (conOf t)
 502           ++ concat (gmapQ ((++) " " . gshow) t)
 503           ++ ")"
 504
 505
 506 -- | Generic equality: an alternative to "deriving Eq"
 507 geq :: forall a. Data a => a -> a -> Bool
 508
 509 {-
 510
 511 We establish the equality of the two top-level datatype constructors.
 512 We use a twin gmap combinator, namely tgmapQ, to compare the two lists
 513 of immediate subterms.
 514
 515 (Note for the experts: the type of the worker geq' is rather general
 516 but precision is recovered via the restrictive type of the top-level
 517 operation geq. The imprecision of geq' is caused by the type system's
 518 unability to express the type equivalence for the corresponding
 519 couples of immediate subterms from the two given input terms.)
 520
 521 -}
 522
 523 geq x y = geq' x y
 524  where
 525   geq' :: forall a b. (Data a, Data b) => a -> b -> Bool
 526   geq' x y = and ( (conString (conOf x) == conString (conOf y))
 527                  : tmapQ geq' x y
 528                  )
 529
 530
 531 -- | Generic zip controlled by a function with type-specific branches
 532 gzip :: (forall a b. (Data a, Data b) => a -> b -> Maybe b)
 533      -> (forall a b. (Data a, Data b) => a -> b -> Maybe b)
 534
 535 -- See testsuite/.../Generics/gzip.hs for an illustration
 536 gzip f x y =
 537   f x y
 538   `orElse`
 539   if conString (conOf x) == conString (conOf y)
 540    then tmapM (gzip f) x y
 541    else Nothing
 542
 543
 544 -- | The type constructor for gunfold a la ReadS from the Haskell 98 Prelude
 545 newtype GRead i a = GRead (i -> Maybe (a, i))
 546 unGRead (GRead x) = x
 547
 548
 549 -- | Generic read: an alternative to "deriving Read"
 550 gread :: Data a => String -> Maybe (a, String)
 551
 552 {-
 553
 554 This is a read operation which insists on prefix notation.
 555 (The Haskell 98 read is closer to conrete syntax.)
 556 We use gunfold to "parse" the input.
 557
 558 -}
 559
 560 gread s
 561  = do s' <- return $ dropWhile ((==) ' ') s
 562       guard (not (s' == ""))
 563       guard (head s' == '(')
 564       (c,s'')  <- prefixConstr (dropWhile ((==) ' ') (tail s'))
 565       (a,s''') <- unGRead (gunfold f z c) s''
 566       guard (not (s''' == ""))
 567       guard (head s''' == ')')
 568       return (a,tail s''')
 569  where
 570
 571   -- Argument f for unfolding
 572   f :: Data a => GRead String (a -> b) -> GRead String b
 573   f x = GRead (\s -> do (r,s') <- unGRead x s
 574                         (t,s'')  <- gread s'
 575                         return (r t,s''))
 576
 577   -- Argument z for unfolding
 578   z ::  forall g. g -> GRead String g
 579   z g = GRead (\s -> return (g,s))
 580
 581   -- Get Constr at front of string
 582   prefixConstr :: String -> Maybe (Constr, String)
 583
 584   -- Assume an infix operators in parantheses
 585   prefixConstr ('(':s)
 586     = case break ((==) ')') s of
 587         (s'@(_:_),(')':s'')) -> Just (Constr ("(" ++ s' ++ ")"), s'')
 588         _ -> Nothing
 589
 590   -- Special treatment of multiple token constructors
 591   prefixConstr ('[':']':s) = Just (Constr "[]",s)
 592
 593   -- Try lex for ordinary constructor and basic datatypes
 594   prefixConstr s
 595     = case lex s of
 596         [(s'@(_:_),s'')] -> Just (Constr s',s'')
 597         _ -> Nothing
 598
 599
 600
 601 ------------------------------------------------------------------------------
 602 --
 603 --      Instances of the Data class
 604 --
 605 ------------------------------------------------------------------------------
 606
 607 -- Basic datatype Int; folding and unfolding is trivial
 608 instance Data Int where
 609  conOf x = Constr (show x)
 610  consOf _ = []
 611  gunfold f z c = z (read (conString c))
 612
 613 -- Another basic datatype instance
 614 instance Data Integer where
 615  conOf x = Constr (show x)
 616  consOf _ = []
 617  gunfold f z c = z (read (conString c))
 618
 619 -- Another basic datatype instance
 620 instance Data Float where
 621  conOf x = Constr (show x)
 622  consOf _ = []
 623  gunfold f z c = z (read (conString c))
 624
 625 -- Another basic datatype instance
 626 instance Data Char where
 627  conOf x = Constr (show x)
 628  consOf _ = []
 629  gunfold f z c = z (read (conString c))
 630
 631 {-
 632
 633 Commented out;
 634 subject to inclusion of a missing Typeable instance
 635
 636 -- Another basic datatype instance
 637 instance Data Rational where
 638  conOf x = Constr (show x)
 639  consOf _ = []
 640  gunfold f z c = z (read (conString c))
 641
 642 -}
 643
 644 -- Bool as a kind of enumeration type
 645 instance Data Bool where
 646  conOf False = Constr "False"
 647  conOf True  = Constr "True"
 648  consOf _    = [Constr "False",Constr "True"]
 649  gunfold f z (Constr "False") = z False
 650  gunfold f z (Constr "True")  = z True
 651
 652 {-
 653
 654 We should better not fold over characters in a string for efficiency.
 655 However, the following instance would clearly overlap with the
 656 instance for polymorphic lists. Given the current scheme of allowing
 657 overlapping instances, this would imply that ANY module that imports
 658 Data.Generics would need to explicitly and generally allow overlapping
 659 instances. This is prohibitive and calls for a more constrained model
 660 of allowing overlapping instances.
 661
 662 -- instance Data String where
 663  conOf x = Constr (show x)
 664  consOf _ = []
 665  gunfold f z c = z (read (conString c))
 666
 667 -}
 668
 669 -- Cons-lists are terms with two immediate subterms. Hence, the gmap
 670 -- combinators do NOT coincide with the list fold/map combinators.
 671 --
 672 instance Data a => Data [a] where
 673   gmapT  f   []     = []
 674   gmapT  f   (x:xs) = (f x:f xs)
 675   gmapQ  f   []     = []
 676   gmapQ  f   (x:xs) = [f x,f xs]
 677   gmapM  f   []     = return []
 678   gmapM  f   (x:xs) = f x >>= \x' -> f xs >>= \xs' -> return (x':xs')
 679   gfoldl f z []     = z []
 680   gfoldl f z (x:xs) = z (:) `f` x `f` xs
 681   conOf [] = Constr "[]"
 682   conOf (_:_) = Constr "(:)"
 683   consOf _ = [Constr "[]",Constr "(:)"]
 684   gunfold f z (Constr "[]")  = z []
 685   gunfold f z (Constr "(:)") = f (f (z (:)))
 686
 687 -- Yet enother polymorphic datatype constructor
 688 instance Data a => Data (Maybe a) where
 689  gfoldl f z Nothing  = z Nothing
 690  gfoldl f z (Just x) = z Just `f` x
 691  conOf Nothing  = Constr "Nothing"
 692  conOf (Just _) = Constr "Just"
 693  consOf _ = [Constr "Nothing", Constr "Just"]
 694  gunfold f z c | conString c == "Nothing" = z Nothing
 695  gunfold f z c | conString c == "Just"    = f (z Just)
 696
 697 -- Yet enother polymorphic datatype constructor
 698 instance (Data a, Data b) => Data (a,b) where
 699  gfoldl f z (a,b) = z (,) `f` a `f` b
 700  conOf _ = Constr "(,)"
 701  consOf _ = [Constr "(,)"]
 702  gunfold f z c | conString c == "(,)" = f (f (z (,)))
 703
 704 -- Functions are treated as "non-compound" data regarding folding while
 705 -- unfolding is out of reach, maybe not anymore with Template Haskell.
 706 --
 707 instance (Typeable a, Typeable b) => Data (a -> b) where
 708  conOf _ = Constr "->"
 709  consOf _ = [Constr "->"]
 710  gunfold _ _ _ = undefined