Open ekmett opened 8 years ago
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.
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.
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.
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.
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.
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.