Change order of Data.Bifunctor.Fix

[Icelandjack]

The order of Fix is unfortunate, it means that given a standard base functor

data FList a list = FNil | FCons a list 

instance Bifunctor FList where
  bimap :: (a -> a') -> (list -> list') -> (FList a list -> FList a' list')
  bimap f g = \case
    FNil      -> FNil
    FCons a b -> FCons (f a) (g b)

instance Bifoldable FList where
  bifoldMap :: Monoid m => (a -> m) -> (list -> m) -> (FList a list -> m)
  bifoldMap f g = \case
    FNil      -> mempty
    FCons a b -> f a <> g b

we get an unexpected order of elements

type List = Fix FList

pattern Nil :: List a
pattern Nil = In FNil

infixr 5 :::
pattern (:::) :: a -> List a -> List a
pattern a:::as = In (FCons as a)

>>> toList (1:::2:::3:::4:::Nil)
[4,3,2,1]

I had the same problems with defining newtype ZipList a = ZL (Fix (Tannen Maybe (,)) from #57 where I need to wrap it in Reverse to get the Foldable I want.

---

if it were the other way round like The Essence of the Iterator Pattern

data Fix' p a = In' { out' :: p a (Fix' p a) }

we would get the right ordering and the argument of fold fits the shape of an algebra

type Alg f a = f a -> a

fold :: Bifunctor f => Alg (f a) b -> (Fix' f a -> b)
fold f = f . second . (fold f) . out'

[RyanGlScott]

@ekmett deliberately chose the current design, see https://github.com/ekmett/bifunctors/pull/8#issuecomment-121932733.

That being said, perhaps there's room for this incarnation as well (under a different name).

[Icelandjack]

I respect unifying the kind structure and I hope that given #12369 they can be unified formally

data family   Fix :: (k -> *) -> k
data instance Fix f     = In  (f (Fix f))
data instance Fix f a   = In1 (f (Fix f) a)
data instance Fix f a b = In2 (f (Fix f) a b)

Maybe the underlying representation doesn't have to change, and we can inline Reverse / Backwards

instance Bifoldable p => Foldable (Fix p) where
  foldMap f (In p) = getDual (bifoldMap (Dual . foldMap f) (Dual . f) p)

instance Bitraversable p => Traversable (Fix p) where
  traverse :: Applicative f => (a -> f a') -> (Fix p a -> f (Fix p a'))
  traverse f (In p) = In <$> forwards (bitraverse (Backwards . traverse f) (Backwards . f) p)

instance Biapplicative p => Applicative (Fix p) where
  pure a = In (bipure (pure a) a)
  In p <*> In q = In (biliftA2 (<**>) (&) q p)

This restores the correct ordering

>>> traverse (\a -> Const [a]) (1:::2:::3:::4:::Nil)
Const [1,2,3,4]

>>> toList (1:::2:::3:::4:::Nil)
[1,2,3,4]

[Icelandjack]

(#12369 has been implemented)

[RyanGlScott]

(#12369 has been implemented)

Great! FWIW, I doubt we are going to be seeing any return-kind-polymorphic data families put into this package any time soon due to bifunctors' wide support window (the same reason we are holding off on #37 for now). This does sound like the sort of thing that would be great to explore in a different library, however.

[ekmett]

I don't generally have a particular problem with enabling new features conditional on the new version, and providing definitions that just don't get exposed on old compilers.

[RyanGlScott]

In any case, I'm not sure what exactly is being proposed here anymore. There seem to be any number of possible changes that @Icelandjack is hinting at:

1. Changing the order of arguments in the current Fix implementation
2. Adding a new Fix with different argument order alongside the one from Data.Bifunctor.Fix (In the same module? A different module? I'm not sure.)

3. Using a return-kind-polymorphic definition. (Whether that should replace the old one or live alongside the old one is also unclear to me.)

   @Icelandjack, do one of those points accurately characterize what you're proposing?

[ekmett]

Sure. It's just a general principle. The best way to apply it here has to be hammered out. It may not belong here in bifunctors simply because bifunctor isn't the base case.