... | ... | @@ -543,4 +543,81 @@ This is pretty much the same as $bimap, only without the $(cobimap 'a 'b 'a) and |
|
|
$(cobimap 'a 'b '(T c1 c2 c3)) = bimap $(cobimap 'a 'b 'c2) $(cobimap 'a 'b 'c3) -- when a and b only occur in the last two parameters, c2 and c3
|
|
|
$(cobimap 'a 'b '(T c1 c2 c3)) = fmap $(cobimap 'a 'b 'c2) -- when a and b only occur in the last parameter, c3
|
|
|
$(cobimap 'a 'b '(c -> d)) = \x e -> $(cobimap 'a 'b 'd) (x ($(bimap 'a 'b 'c) e))
|
|
|
``` |
|
|
\ No newline at end of file |
|
|
```
|
|
|
|
|
|
|
|
|
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:
|
|
|
|
|
|
```wiki
|
|
|
$(bifoldMap 'a 'b 'c) = \x -> mempty -- when c does not contain a or b
|
|
|
$(bifoldMap 'a 'b 'a) = f
|
|
|
$(bifoldMap 'a 'b 'b) = g
|
|
|
$(bifoldMap 'a 'b '(c1,c2)) = \x -> case x of (x1, x2) -> mappend ($(bifoldMap 'a 'b 'c1) x1) ($(bifoldMap 'a 'b 'c2) x2)
|
|
|
$(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
|
|
|
$(bifoldMap 'a 'b '(T c1 c2 c3)) = foldMap $(bifoldMap 'a 'b 'c3) -- when a and b only occur in the last parameter, c3
|
|
|
```
|
|
|
|
|
|
|
|
|
(The caveats in [ https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/DeriveFunctor\#AlternativestrategyforderivingFoldableandTraversable](https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/DeriveFunctor#AlternativestrategyforderivingFoldableandTraversable) apply.)
|
|
|
|
|
|
|
|
|
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)`:
|
|
|
|
|
|
|
|
|
{{{!\#hs
|
|
|
instance Bifoldable T where
|
|
|
|
|
|
>
|
|
|
> bifoldMap _ g (T e) = foldMap g e
|
|
|
|
|
|
|
|
|
}}}
|
|
|
|
|
|
|
|
|
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](https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/DeriveFunctor#RelaxeduniversalitycheckforDeriveFoldable) for more info):
|
|
|
|
|
|
```
|
|
|
instanceBifunctorTwhere
|
|
|
bimap f g (T e)=T(bimap f g e)instanceBitraversableTwhere
|
|
|
bitraverse f g (T e)= fmap T(bitraverse f g e)
|
|
|
```
|
|
|
|
|
|
|
|
|
Therefore, it feels far more natural to generate this `Bifoldable` instance:
|
|
|
|
|
|
```
|
|
|
instanceBifoldableTwhere
|
|
|
bifoldMap f g (T e)= bifoldMap f g e
|
|
|
```
|
|
|
|
|
|
|
|
|
This also ensures that [ bifoldMapDefault](http://hackage.haskell.org/package/bifunctors-5.3/docs/Data-Bitraversable.html#v:bifoldMapDefault) gives the same result as `bifoldMap`.
|
|
|
|
|
|
#### Corner case: GADTs
|
|
|
|
|
|
|
|
|
Consider the following code:
|
|
|
|
|
|
```
|
|
|
dataBoth a b whereBothCon:: x -> x ->Both x x
|
|
|
|
|
|
derivinginstanceBifoldableBoth
|
|
|
```
|
|
|
|
|
|
|
|
|
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:
|
|
|
|
|
|
```
|
|
|
instanceBifoldableBothwhere
|
|
|
bifoldMap _ g (BothCon x1 x2)= g x1 <> g x2
|
|
|
```
|
|
|
|
|
|
|
|
|
This definition ensures that `bifoldMap id = foldMap` for a derived `Foldable` instance for `Both`.
|
|
|
|
|
|
#### `Data.Functor.Classes`
|
|
|
|
|
|
|
|
|
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.
|
|
|
|
|
|
`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`. |