<div class="gmail_quote">On Tue, Apr 19, 2011 at 11:29 AM, Henning Thielemann <span dir="ltr"><<a href="mailto:lemming@henning-thielemann.de">lemming@henning-thielemann.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<br>
Is it common to make a type an instance of both Arrow and Functor type class? If a type is both instance of Arrow and Functor, would you expect that fmap = (^<<) ? If yes, how about adding this as expected law to the Control.Arrow documentation? </blockquote>
<div><br></div><div>For any instance of Functor that is also an Arrow this must hold already given existing laws.</div><div><br></div><div>One (particularly obvious) arrow law is that </div><div><br></div><div><font class="Apple-style-span" face="'courier new', monospace">arr id = id</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><br></font></div><div>This law states the fact that arr is the Functor from the category of Haskell types to your arrow category.</div><div><br></div>
<div>Given that:</div><div><font class="Apple-style-span" face="'courier new', monospace"><br></font></div><div><font class="Apple-style-span" face="'courier new', monospace">id ^<< g = arr id <<< g = g . arr id = g . id = g = id g</font></div>
<div><br></div><div>we can see <font class="Apple-style-span" face="'courier new', monospace">(^<<) id = id</font> is satisfied. The "second Functor law" comes for free given<font class="Apple-style-span" face="'courier new', monospace"> (^<<) id = id</font>, and the free theorem for <font class="Apple-style-span" face="'courier new', monospace">(^<<)</font>, so <font class="Apple-style-span" face="'courier new', monospace">(^<<)</font> is admissable as a definition for<font class="Apple-style-span" face="'courier new', monospace"> fmap</font>.</div>
<div><br></div><div>Finally, valid Functor instances for a given type are unique. </div><div><br></div><div>This also follows from the free theorem for fmap and the side condition that <font class="Apple-style-span" face="'courier new', monospace">fmap id = id</font> and has been worked through here on the cafe before. I believe it was done most recently by Russell O'Connor.</div>
<div><br></div><div>So <font class="Apple-style-span" face="'courier new', monospace">fmap = (^<<)</font> must hold for any type that is both a valid instance of Arrow and Functor.<br><br></div><div>The free theorem for fmap does all your work for you and no new laws need to be placed on the books.</div>
<div><br></div><div>-Edward</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">Same question for Applicative functors and liftA2 (,) = (&&&). (Btw. Control.Arrow haddock documentation does not mention any Arrow law so far.)<br>
<br>
_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org" target="_blank">Libraries@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/libraries" target="_blank">http://www.haskell.org/mailman/listinfo/libraries</a><br>
</blockquote></div><br>