| 537 | |
| 538 | This algorithm isn't terribly different from the one above for generating an `fmap` implementation, and that's the point. It's simply generalizing the same ideas to work over a typeclass of kind `* -> * -> *`. The algorithms for generating `foldMap`/`foldr` and `traverse` can be generalized to generate `bifoldMap`/`bifoldr` and `bitraverse`, respectively. For example, here's what the algorithm for `bifoldMap` would look like: |
| 539 | |
| 540 | {{{ |
| 541 | $(bifoldMap 'a 'b 'c) = \x -> mempty -- when c does not contain a or b |
| 542 | $(bifoldMap 'a 'b 'a) = f |
| 543 | $(bifoldMap 'a 'b 'b) = g |
| 544 | $(bifoldMap 'a 'b '(c1,c2)) = \x -> case x of (x1, x2) -> mappend ($(bifoldMap 'a 'b 'c1) x1) ($(bifoldMap 'a 'b 'c2) x2) |
| 545 | $(bifoldMap 'a 'b '(T c1 c2 c3)) = bifoldMap $(bifoldMap 'a 'b 'c2) $(bifoldMap 'a 'b 'c3) -- when a and b only occur in the last two parameters, c2 and c3 |
| 546 | $(bifoldMap 'a 'b '(T c1 c2 c3)) = foldMap $(bifoldMap 'a 'b 'c3) -- when a and b only occur in the last parameter, c3 |
| 547 | }}} |
| 548 | |
| 549 | (The caveats in https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/DeriveFunctor#AlternativestrategyforderivingFoldableandTraversable apply.) |
| 550 | |
| 551 | There's one part of the `bifoldMap` algorithm that deserves futher discussion: the overlapping cases for `T c1 c1 c3`. Whenever an argument to a constructor has a type where each of the last two type variables mention `a` or `b`, we opt to generate `bifoldMap` instead of `foldMap`. We //could// go the other way, though. For instance, the following is a valid implementation of `Bifoldable` for `newtype T a b = T (Either a b)`: |
| 552 | |
| 553 | {{{!#hs |
| 554 | instance Bifoldable T where |
| 555 | bifoldMap _ g (T e) = foldMap g e |
| 556 | }}} |
| 557 | |
| 558 | But this is unsatisfying for a couple of reasons, though. One obvious issue is that this definition blatantly ignores the first argument to `bifoldMap`, preventing users from folding over the `a` type parameter. Another problem is that doing this would be inconsistent with how `bimap` and `bitraverse` are generated. Unlike with `bifoldMap`, parametricity forces there to be one definition for `bimap` and `bitraverse` (see https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/DeriveFunctor#RelaxeduniversalitycheckforDeriveFoldable for more info): |
| 559 | |
| 560 | {{{#!hs |
| 561 | instance Bifunctor T where |
| 562 | bimap f g (T e) = T (bimap f g e) |
| 563 | |
| 564 | instance Bitraversable T where |
| 565 | bitraverse f g (T e) = fmap T (bitraverse f g e) |
| 566 | }}} |
| 567 | |
| 568 | Therefore, it feels far more natural to generate this `Bifoldable` instance: |
| 569 | |
| 570 | {{{#!hs |
| 571 | instance Bifoldable T where |
| 572 | bifoldMap f g (T e) = bifoldMap f g e |
| 573 | }}} |
| 574 | |
| 575 | This also ensures that [http://hackage.haskell.org/package/bifunctors-5.3/docs/Data-Bitraversable.html#v:bifoldMapDefault bifoldMapDefault] gives the same result as `bifoldMap`. |
| 576 | |
| 577 | ==== Corner case: GADTs ==== |
| 578 | |
| 579 | Consider the following code: |
| 580 | |
| 581 | {{{#!hs |
| 582 | data Both a b where |
| 583 | BothCon :: x -> x -> Both x x |
| 584 | |
| 585 | deriving instance Bifoldable Both |
| 586 | }}} |
| 587 | |
| 588 | What should be the definition of `bifoldMap` for `Both`? We have a choice, since both the function argument of type `(a -> m)` and of type `(b -> m)` can be applied to either argument. In such a scenario, the second fold function takes precedence over the first fold function, so the derived `Bifoldable` instance would be: |
| 589 | |
| 590 | {{{#!hs |
| 591 | instance Bifoldable Both where |
| 592 | bifoldMap _ g (BothCon x1 x2) = g x1 <> g x2 |
| 593 | }}} |
| 594 | |
| 595 | This definition ensures that `bifoldMap id = foldMap` for a derived `Foldable` instance for `Both`. |
| 596 | |
| 597 | ==== `Data.Functor.Classes` ==== |
| 598 | |
| 599 | Deriving `Eq1/2`, `Ord1/2`, and `Show1/2` could be done in a very similar way to deriving `Foldable/Bifoldable`. For instance, you can substitute in `liftEq`/`liftEq2` in place of `foldMap`/`bifoldMap` in the above algorithm and have a sensible way to generate `liftEq`/`liftEq2` expressions. In addition, `Eq1/2`, `Ord1/2`, and `Show1/2` can all be derived for GADTs as well. |
| 600 | |
| 601 | `Read1/2` could not be derived for GADTs, since it mentions type variables in the return types of its methods, but it could still be derived using the same principles as deriving `Foldable`/`Bifoldable`. |