Use representable Moore and Mealy

[ekmett]

https://www.fpcomplete.com/user/edwardk/moore/for-less

This would give us Moore machines with a more efficient mapping operation for one, and all of the recent improvements could be ported over.

[Zemyla]

You may actually want an Adjunction. I've been experimenting with something like:

data Mealy a b where
  Mealy :: (Applicative u, Adjunction f u) => f (u (a -> f b)) -> Mealy a b

This allows you to do things like define arr as follows:

arr = (coerce :: (Identity (Identity (a -> Identity b)) -> Mealy a b) -> (a -> b) -> Mealy a b) Mealy

The Applicative instance is required because (a) Distributive really should have Applicative as a superclass, and (b) so Choice can be defined fairly easily:

instance Choice Mealy where
  left' (Mealy fu) = Mealy $ fmap (liftA2 (\fr fl -> either (fmap Left . fl) (fmap Right . fr)) $ distribute unit) fu
  right' (Mealy fu) = Mealy $ fmap (liftA2 (\fl fr -> either (fmap Left . fl) (fmap Right . fr)) $ distribute unit) fu

You don't technically need Applicative, though, as if you have an Adjunction, you can define a liftA2 analogue:

liftAdj2 :: Adjunction f u => (a -> b -> c) -> u a -> u b -> u c
liftAdj2 f ua ub = leftAdjunct (\fab -> f (rightAdjunct fst fab) (rightAdjunct snd fab)) (ua, ub)

But as mentioned before, every sensible Distributive/Representable instance should have an Applicative instance as well.

[ekmett]

NB: Adjunction f g is equivalent to Representable g.

It isn't until you allow adjunctions to spread to other categories than just Hask -> Hask that anything extra is gained.

[ekmett]

Using Representable instead means we can unpack the f = (,) (Rep g) in the Mealy constructor. Adjunction holds out hope that it might be something exotic, which shrinks the Identity case by 8 bytes in exchange for making the common case have to follow a pointer indirection.

[ekmett]

Interestingly it is possible to implement Applicative using Distributive, it's just messy and requires partial functions under the hood. I do agree that it should have at least that as a superclass, and if Compose was a nicer cultural fit, I'd want Monad as well, but alas.

[treeowl]

You mean with

fs <*> xs = (\(Pair (Left f) (Right x)) <$>
                     distribute (Pair (fmap Left fs) (fmap Right xs))

or something like that? I guess it uses parametricity to ensure totality.
Pretty horrible all right. The unsafeCoerce version is even uglier, but presumably more efficient.