<div class="gmail_quote">On Sun, Jun 27, 2010 at 7:43 AM, Sjoerd Visscher <span dir="ltr">&lt;<a href="mailto:sjoerd@w3future.com">sjoerd@w3future.com</a>&gt;</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>
&gt; 1. There exist total functions:<br>
&gt;<br>
&gt;&gt; lift :: X d =&gt; d a -&gt; D a<br>
&gt;&gt; lower :: X d =&gt; D a -&gt; d a<br>
&gt;<br>
&gt; 2. And you can write a valid instance:<br>
&gt;<br>
&gt;&gt; instance X D<br>
&gt;<br>
&gt; With *no superclass constraints*.<br>
<br>
</div>All your examples have a more specific form:<br>
<br>
&gt; lift :: X d =&gt; d a -&gt; D d a<br>
&gt; lower :: X d =&gt; D d a -&gt; d a<br>
&gt; 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&#39;s not the case.<br>
<div class="im"><br>
&gt; 2. Is there a mother of all idioms? By analogy with the previous three<br>
&gt; examples, I tried this:<br>
&gt;<br>
&gt;&gt; -- (&lt;**&gt;) :: forall a. i a -&gt; (forall b. i (a -&gt; b) -&gt; i b)<br>
&gt;&gt; newtype Thingy i a = Thingy { runThingy :: forall b. i (a -&gt; b) -&gt; i b }<br>
&gt;<br>
&gt; But I can&#39;t see how to write either pure or &lt;*&gt; with that data type.<br>
&gt; This version seems to work slightly better:<br>
&gt;<br>
&gt;&gt; newtype Thingy i a = Thingy { runThingy :: forall b. Yoneda i (a -&gt; b) -&gt; i b }<br>
&gt;<br>
&gt; Because you can write pure (pure x = Thingy (\k -&gt; lowerYoneda (fmap<br>
&gt; ($ x) k))). But &lt;*&gt; still eludes me!<br>
<br>
</div>It&#39;s usually easier to switch to Monoidal functors when playing with Applicative. (See the original Functional Pearl &quot;Applicative programming with effects&quot;.)<br>
<br>
Then I got this:<br>
<br>
newtype Thingy i a = Thingy { runThingy :: forall b. Yoneda i b -&gt; Yoneda i (a, b) }<br>
<br>
(&amp;&amp;&amp;) :: Thingy i c -&gt; Thingy i d -&gt; Thingy i (c, d)<br>
mf &amp;&amp;&amp; mx = Thingy $ fmap (\(d, (c, b)) -&gt; ((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 &lt;*&gt; mx = fmap (\(f, x) -&gt; f x) (mf &amp;&amp;&amp; mx)<br>
<br>
Note that Yoneda is only there to make it possible to use fmap without the Functor f constraint. So I&#39;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&#39;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 :: * -&gt; *.</div><div><br></div><div>-Edward Kmett</div></div>