Changes between Version 18 and Version 19 of Commentary/Compiler/DeriveFunctor


Ignore:
Timestamp:
Jul 14, 2016 2:38:12 PM (3 years ago)
Author:
RyanGlScott
Comment:

More details

Legend:

Unmodified
Added
Removed
Modified
  • Commentary/Compiler/DeriveFunctor

    v18 v19  
    535535  $(cobimap 'a 'b '(c -> d))      =  \x e -> $(cobimap 'a 'b 'd) (x ($(bimap 'a 'b 'c) e))
    536536}}}
     537
     538This 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
     551There'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
     554instance Bifoldable T where
     555  bifoldMap _ g (T e) = foldMap g e
     556}}}
     557
     558But 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
     561instance Bifunctor T where
     562  bimap f g (T e) = T (bimap f g e)
     563
     564instance Bitraversable T where
     565  bitraverse f g (T e) = fmap T (bitraverse f g e)
     566}}}
     567
     568Therefore, it feels far more natural to generate this `Bifoldable` instance:
     569
     570{{{#!hs
     571instance Bifoldable T where
     572  bifoldMap f g (T e) = bifoldMap f g e
     573}}}
     574
     575This 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
     579Consider the following code:
     580
     581{{{#!hs
     582data Both a b where
     583  BothCon :: x -> x -> Both x x
     584
     585deriving instance Bifoldable Both
     586}}}
     587
     588What 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
     591instance Bifoldable Both where
     592  bifoldMap _ g (BothCon x1 x2) = g x1 <> g x2
     593}}}
     594
     595This definition ensures that `bifoldMap id = foldMap` for a derived `Foldable` instance for `Both`.
     596
     597==== `Data.Functor.Classes` ====
     598
     599Deriving `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`.