<div class="gmail_quote">On Sun, Jun 27, 2010 at 7:43 AM, Sjoerd Visscher <span dir="ltr"><<a href="mailto:sjoerd@w3future.com">sjoerd@w3future.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Hi Max,<br>
<br>
This is really interesting!<br>
<div class="im"><br>
> 1. There exist total functions:<br>
><br>
>> lift :: X d => d a -> D a<br>
>> lower :: X d => D a -> d a<br>
><br>
> 2. And you can write a valid instance:<br>
><br>
>> instance X D<br>
><br>
> With *no superclass constraints*.<br>
<br>
</div>All your examples have a more specific form:<br>
<br>
> lift :: X d => d a -> D d a<br>
> lower :: X d => D d a -> d a<br>
> instance X (D d)<br>
<br>
This might help when looking for a matching categorical concept. With your original signatures I was thinking of initial/terminal objects, but that's not the case.<br>
<div class="im"><br>
> 2. Is there a mother of all idioms? By analogy with the previous three<br>
> examples, I tried this:<br>
><br>
>> -- (<**>) :: forall a. i a -> (forall b. i (a -> b) -> i b)<br>
>> newtype Thingy i a = Thingy { runThingy :: forall b. i (a -> b) -> i b }<br>
><br>
> But I can't see how to write either pure or <*> with that data type.<br>
> This version seems to work slightly better:<br>
><br>
>> newtype Thingy i a = Thingy { runThingy :: forall b. Yoneda i (a -> b) -> i b }<br>
><br>
> Because you can write pure (pure x = Thingy (\k -> lowerYoneda (fmap<br>
> ($ x) k))). But <*> still eludes me!<br>
<br>
</div>It's usually easier to switch to Monoidal functors when playing with Applicative. (See the original Functional Pearl "Applicative programming with effects".)<br>
<br>
Then I got this:<br>
<br>
newtype Thingy i a = Thingy { runThingy :: forall b. Yoneda i b -> Yoneda i (a, b) }<br>
<br>
(&&&) :: Thingy i c -> Thingy i d -> Thingy i (c, d)<br>
mf &&& mx = Thingy $ fmap (\(d, (c, b)) -> ((c, d), b)) . runThingy mx . runThingy mf<br>
<br>
instance Functor (Thingy i) where<br>
fmap f m = Thingy $ fmap (first f) . runThingy m<br>
<br>
instance Applicative (Thingy i) where<br>
pure x = Thingy $ fmap (x,)<br>
mf <*> mx = fmap (\(f, x) -> f x) (mf &&& mx)<br>
<br>
Note that Yoneda is only there to make it possible to use fmap without the Functor f constraint. So I'm not sure if requiring no class constraints at all is a good requirement. It only makes things more complicated, without providing more insights.<br>
<br>
I'd say that if class X requires a superclass constraint Y, then the instance of X (D d) is allowed to have the constraint Y d. The above code then stays the same, only with Yoneda removed and constraints added.<br></blockquote>
<div><br></div><div>This is an encoding of the fact that all Functors in Haskell are strong, and that Yoneda i is a Functor for any i :: * -> *.</div><div><br></div><div>-Edward Kmett</div></div>