<div class="gmail_quote">On Fri, Jul 9, 2010 at 8:46 PM, Kevin Quick <span dir="ltr"><<a href="mailto:quick@sparq.org">quick@sparq.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="im">On Fri, 09 Jul 2010 16:26:13 -0700, Ivan Lazar Miljenovic <<a href="mailto:ivan.miljenovic@gmail.com" target="_blank">ivan.miljenovic@gmail.com</a>> wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
"Kevin Quick" <<a href="mailto:quick@sparq.org" target="_blank">quick@sparq.org</a>> writes:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I would think that only mutually recursive default methods would<br>
require respecification and that there could be any number of default<br>
methods that were reasonable as is. Since it's probably quite<br>
difficult for the Haskell compiler to analytically detect<br>
non-terminating v.s. terminating mutual recursion it may be useful to<br>
define an explicit comment flag for this case.<br>
<br>
For example:<br>
<br>
class Show a where<br>
shows = showsPrec 5<br>
showsPrec _ = shows<br>
{-# REDEFINE_ONE: shows showsPrec #-}<br>
<br>
This would fairly simply allow a warning to be generated for an<br>
instance which did not redefine one of the identified methods; it<br>
would capture that requirement in the same place the recursive<br>
definition was defined, it would avoid false warnings, and it would be<br>
backward compatible (and it might be Haddock-able as well).<br>
</blockquote>
<br>
This should be generalised IMO, since there might be cases where you<br>
have to redefine either (foo && bar) || baz; of course, that makes the<br>
syntax specification, etc. of the pragma more difficult...<br>
</blockquote>
<br></div>
I'm having trouble envisioning a restriction case such as you describe. Can you provide an example?<br></blockquote><div><br></div><div>Examples: </div><div><br></div><div><div><font class="Apple-style-span" face="'courier new', monospace">class Bifunctor f where</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> bimap :: (a -> b) -> (c -> d) -> f a c -> f b d</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> first :: (a -> b) -> f a c -> f b c</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> second :: (a -> b) -> f c a -> f c b</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> first f = bimap f id</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> second = bimap id</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> bimap f g = second g . first f</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> {-# MUTUAL = first second | bimap #-}</font></div></div><div><br></div><div>The existing definition of Arrow is somewhat unsatisfying because its product bifunctor definition (given by first, second and (***)) is asymmetric. They choose to require you to define first, but could very well use the same trick. (I am not advocating changing the well documented historical definition of Arrow, just providing another example in the same vein.)</div>
<div><br></div><div><span class="Apple-style-span" style="font-family: monospace; font-size: medium; white-space: pre; "><span class="hs-keyword" style="color: blue; ">class</span> <span class="hs-conid">Category</span> <span class="hs-varid">a</span> <span class="hs-keyglyph" style="color: red; ">=></span> <span class="hs-conid">Arrow</span> <span class="hs-varid">a</span> <span class="hs-keyword" style="color: blue; ">where</span></span></div>
<div><div><span class="Apple-style-span" style="font-family: 'Times New Roman'; font-size: medium; "><pre> <span class="hs-varid">arr</span> <span class="hs-keyglyph" style="color: red; ">::</span> <span class="hs-layout" style="color: red; ">(</span><span class="hs-varid">b</span> <span class="hs-keyglyph" style="color: red; ">-></span> <span class="hs-varid">c</span><span class="hs-layout" style="color: red; ">)</span> <span class="hs-keyglyph" style="color: red; ">-></span> <span class="hs-varid">a</span> <span class="hs-varid">b</span> <span class="hs-varid">c</span>
<span class="hs-varid">first</span> <span class="hs-keyglyph" style="color: red; ">::</span> <span class="hs-varid">a</span> <span class="hs-varid">b</span> <span class="hs-varid">c</span> <span class="hs-keyglyph" style="color: red; ">-></span> <span class="hs-varid">a</span> <span class="hs-layout" style="color: red; ">(</span><span class="hs-varid">b</span><span class="hs-layout" style="color: red; ">,</span><span class="hs-varid">d</span><span class="hs-layout" style="color: red; ">)</span> <span class="hs-layout" style="color: red; ">(</span><span class="hs-varid">c</span><span class="hs-layout" style="color: red; ">,</span><span class="hs-varid">d</span><span class="hs-layout" style="color: red; ">)</span>
<span class="hs-varid">second</span> <span class="hs-keyglyph" style="color: red; ">::</span> <span class="hs-varid">a</span> <span class="hs-varid">b</span> <span class="hs-varid">c</span> <span class="hs-keyglyph" style="color: red; ">-></span> <span class="hs-varid">a</span> <span class="hs-layout" style="color: red; ">(</span><span class="hs-varid">d</span><span class="hs-layout" style="color: red; ">,</span><span class="hs-varid">b</span><span class="hs-layout" style="color: red; ">)</span> <span class="hs-layout" style="color: red; ">(</span><span class="hs-varid">d</span><span class="hs-layout" style="color: red; ">,</span><span class="hs-varid">c</span><span class="hs-layout" style="color: red; ">)</span>
<span class="hs-layout" style="color: red; ">(</span><span class="hs-varop">***</span><span class="hs-layout" style="color: red; ">)</span> <span class="hs-keyglyph" style="color: red; ">::</span> <span class="hs-varid">a</span> <span class="hs-varid">b</span> <span class="hs-varid">c</span> <span class="hs-keyglyph" style="color: red; ">-></span> <span class="hs-varid">a</span> <span class="hs-varid">b'</span> <span class="hs-varid">c'</span> <span class="hs-keyglyph" style="color: red; ">-></span> <span class="hs-varid">a</span> <span class="hs-layout" style="color: red; ">(</span><span class="hs-varid">b</span><span class="hs-layout" style="color: red; ">,</span><span class="hs-varid">b'</span><span class="hs-layout" style="color: red; ">)</span> <span class="hs-layout" style="color: red; ">(</span><span class="hs-varid">c</span><span class="hs-layout" style="color: red; ">,</span><span class="hs-varid">c'</span><span class="hs-layout" style="color: red; ">)</span>
<span class="hs-layout" style="color: red; ">(</span><span class="hs-varop">&&&</span><span class="hs-layout" style="color: red; ">)</span> <span class="hs-keyglyph" style="color: red; ">::</span> <span class="hs-varid">a</span> <span class="hs-varid">b</span> <span class="hs-varid">c</span> <span class="hs-keyglyph" style="color: red; ">-></span> <span class="hs-varid">a</span> <span class="hs-varid">b</span> <span class="hs-varid">c'</span> <span class="hs-keyglyph" style="color: red; ">-></span> <span class="hs-varid">a</span> <span class="hs-varid">b</span> <span class="hs-layout" style="color: red; ">(</span><span class="hs-varid">c</span><span class="hs-layout" style="color: red; ">,</span><span class="hs-varid">c'</span><span class="hs-layout" style="color: red; ">)</span>
<a name="line-93"></a><br></pre><pre><span class="Apple-style-span" style="font-family: 'Times New Roman'; white-space: normal; "><pre><pre> first <span class="hs-keyglyph" style="color: red; ">=</span> (*** id)
</pre><div><span class="hs-varid"><span class="Apple-style-span" style="font-family: 'Times New Roman'; white-space: normal; "><pre><pre> <span class="hs-varid">second</span> <span class="hs-keyglyph" style="color: red; ">=</span> (id ***)
</pre><div> <span class="hs-varid">f</span> <span class="hs-varop">***</span> <span class="hs-varid">g</span> <span class="hs-keyglyph" style="color: red; ">=</span> <span class="hs-varid">first</span> <span class="hs-varid">f</span> <span class="hs-varop">>>></span> <span class="hs-varid">second</span> <span class="hs-varid">g</span></div>
</pre></span></span></div></pre></span></pre><pre> <span class="hs-varid">f</span> <span class="hs-varop">&&&</span> <span class="hs-varid">g</span> <span class="hs-keyglyph" style="color: red; ">=</span> <span class="hs-varid">arr</span> <span class="hs-layout" style="color: red; ">(</span><span class="hs-keyglyph" style="color: red; ">\</span><span class="hs-varid">b</span> <span class="hs-keyglyph" style="color: red; ">-></span> <span class="hs-layout" style="color: red; ">(</span><span class="hs-varid">b</span><span class="hs-layout" style="color: red; ">,</span><span class="hs-varid">b</span><span class="hs-layout" style="color: red; ">)</span><span class="hs-layout" style="color: red; ">)</span> <span class="hs-varop">>>></span> <span class="hs-varid">f</span> <span class="hs-varop">***</span> <span class="hs-varid">g</span></pre>
<pre> {-# MUTUAL first second | (***) #-}</pre></span></div><div><span class="Apple-style-span" style="font-family: 'Times New Roman'; font-size: medium; "><pre><span class="Apple-style-span" style="font-family: arial; white-space: normal; font-size: small; ">An example that almost works would be Monad/Comonad where you can define in terms of return/fmap/join or return/bind. However, the definition of fmap is in another class, but if it wasn't:</span></pre>
<div><span class="hs-layout" style="color: red; "><span class="Apple-style-span" style="color: rgb(0, 0, 0); "><pre><font class="Apple-style-span" face="'Times New Roman'"><span class="Apple-style-span" style="white-space: normal; "><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre; "><span class="Apple-style-span" style="font-family: arial; white-space: normal; font-size: small; "><div>
<span class="Apple-style-span" style="font-family: 'courier new', monospace; ">class Comonad w where</span></div></span></span></font></span></font></pre></span></span></div></span></div></div><div><font class="Apple-style-span" face="'courier new', monospace"> liftW :: (a -> b) -> w a -> w b</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> extract :: w a -> a</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> extend :: (w a -> b) -> w a -> w b</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> duplicate :: w a -> w (w a)</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> extend = fmap f . duplicate</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> duplicate = extend id</font></div><div><font class="Apple-style-span" face="'courier new', monospace"><br></font></div><div><font class="Apple-style-span" face="'courier new', monospace"> {-# MUTUAL liftW duplicate | extend #-}</font></div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
The comment can't dictate that the resulting redefined method isn't still mutually recursive, but the warning for the lack of any override should provide enough of a trigger for the developer to read the docs/code and write an appropriate method. If foo, bar, and baz are all interrelated it seems to me that an appropriate override of any of them could provide the necessary exit from recursion.<br>
</blockquote><div><br></div><div>It turns out to be fairly tricky to pull off the definition in such a way that you can define any one combinator in turn of the others in a big long cycle. Foldable does this for instance in such a way that foldMap and foldr are defined cyclically. </div>
<div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
That's probably an interesting assertion that one of the category theorists around here could prove or disprove. ;-)<br></blockquote><div> </div><div>I hope the above demonstrate that there are at least some fairly reasonable (and, given your request, appropriately category theoretic!) examples where one would want the ability to specify that there is more than one member of a minimal mutual definition. =)</div>
<div><br></div><div>-Edward Kmett</div></div>