<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Dear Steve, et al.,<div><br></div><div><div><div>On 6 Jan 2012, at 11:00, &lt;<a href="mailto:haskell-cafe-request@haskell.org">haskell-cafe-request@haskell.org</a>&gt;</div><div>&nbsp;&lt;<a href="mailto:haskell-cafe-request@haskell.org">haskell-cafe-request@haskell.org</a>&gt; wrote:</div><br><blockquote type="cite"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;"><span style="font-family:'Helvetica'; font-size:medium; color:rgba(127, 127, 127, 1.0);"><b>From: </b></span><span style="font-family:'Helvetica'; font-size:medium;">Steve Horne &lt;<a href="mailto:sh006d3592@blueyonder.co.uk">sh006d3592@blueyonder.co.uk</a>&gt;<br></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;"><span style="font-family:'Helvetica'; font-size:medium; color:rgba(127, 127, 127, 1.0);"><b>Date: </b></span><span style="font-family:'Helvetica'; font-size:medium;">6 January 2012 10:51:58 GMT<br></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;"><span style="font-family:'Helvetica'; font-size:medium; color:rgba(127, 127, 127, 1.0);"><b>To: </b></span><span style="font-family:'Helvetica'; font-size:medium;">Steffen Schuldenzucker &lt;<a href="mailto:sschuldenzucker@uni-bonn.de">sschuldenzucker@uni-bonn.de</a>&gt;<br></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;"><span style="font-family:'Helvetica'; font-size:medium; color:rgba(127, 127, 127, 1.0);"><b>Cc: </b></span><span style="font-family:'Helvetica'; font-size:medium;">Haskell Cafe Mailing List &lt;<a href="mailto:haskell-cafe@haskell.org">haskell-cafe@haskell.org</a>&gt;<br></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;"><span style="font-family:'Helvetica'; font-size:medium; color:rgba(127, 127, 127, 1.0);"><b>Subject: </b></span><span style="font-family:'Helvetica'; font-size:medium;"><b>Re: [Haskell-cafe] Simple type-class experiment turns out not so simple...</b><br></span></div><br><br>On 06/01/2012 10:29, Steffen Schuldenzucker wrote:<br><blockquote type="cite">With 'd' not being mentioned anywhere, the signature of wbtData means "forall d. n -&gt; Maybe d". In particular, wbtData == const Nothing.</blockquote><blockquote type="cite"><br></blockquote>I'm not sure what to make of that. Even if the result of wbtData is always Nothing, surely it still has a static type?<br></blockquote><div><br></div><div>I think what Steffen was saying here is that the only implementation of wbtData that satisfies the general type "forall d. n -&gt; Maybe d" is "const Nothing" which has precisely that static type (the forall doesn't make it a dynamic type).</div><div><br></div><blockquote type="cite">Precisely that. In that case, I get...<br><br>C:\_SVN\dev_trunk\haskell\examples&gt;ghci -XMultiParamTypeClasses<br>GHCi, version 7.0.4: <a href="http://www.haskell.org/ghc/">http://www.haskell.org/ghc/</a> &nbsp;:? for help<br>Loading package ghc-prim ... linking ... done.<br>Loading package integer-gmp ... linking ... done.<br>Loading package base ... linking ... done.<br>Loading package ffi-1.0 ... linking ... done.<br>Prelude&gt; :load BinTree<br>[1 of 1] Compiling BinTree &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;( BinTree.hs, interpreted )<br><br>BinTree.hs:12:12:<br> &nbsp;&nbsp;&nbsp;Illegal instance declaration for `WalkableBinTree (BT x) x'<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(All instance types must be of the form (T a1 ... an)<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;where a1 ... an are *distinct type variables*,<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;and each type variable appears at most once in the instance head.<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Use -XFlexibleInstances if you want to disable this.)<br> &nbsp;&nbsp;&nbsp;In the instance declaration for `WalkableBinTree (BT x) x'<br>Failed, modules loaded: none.<br>Prelude&gt;<br><br>If I specify both extensions (-XMultiParamTypeClasses and -XFlexibleInstances) it seems to work, but needing two language extensions is a pretty strong hint that I'm doing it the wrong way.<br></blockquote><div><br></div><div>This isn't a general truth, but if you're still in early stages of learning about GHCs type-class implementation, you're probably right.</div><br><blockquote type="cite">The goal is fairly obvious - to have type-classes for binary tree capabilities so that different implementations can support different subsets of those capabilities. Being able to walk a binary tree doesn't need ordering of keys, whereas searching does. A red-black tree needs somewhere to store it's colour in the node, yet the walking and searching functions don't need to know about that.<br></blockquote><div><br></div><div>The problem with the "forall d. n -&gt; Maybe d" type is that it makes d too general (universal, in fact), while d is fixed by n. There is an alternative extension you may want to look into for your furtherance of the capabilities of GHC, being TypeFamilies. These would lead to the following alternative implementation:</div><div><br></div><div><div>{-# LANGUAGE TypeFamilies #-}</div><div><br></div><div>class WalkableBinTree n where</div><div>&nbsp; type ElemTp n</div><div>&nbsp; wbtChildren :: n -&gt; Maybe (n, n)</div><div>&nbsp; wbtData &nbsp; &nbsp; :: n -&gt; Maybe (ElemTp n)</div><div><br></div><div>instance WalkableBinTree (BT x) where</div><div>&nbsp; type ElemTp (BT x) = x</div><div><br></div><div>&nbsp; wbtChildren (Branch d l r) = Just (l, r)</div><div>&nbsp; wbtChildren &nbsp;Empty &nbsp; &nbsp; &nbsp; &nbsp; = Nothing</div><div><br></div><div>&nbsp; wbtData &nbsp; &nbsp; (Branch d l r) = Just d</div><div>&nbsp; wbtData &nbsp; &nbsp; &nbsp;Empty &nbsp; &nbsp; &nbsp; &nbsp; = Nothing</div><div><br></div><div><br></div><div>This says that the instance fixes the "element type" ElemTp to something specific.&nbsp;However, it seems perfectly reasonable for the goal you describe to demand that whatever tree-type this class is instantiated for must be parametric in its element type. This can be done without any language extension, i.e.:</div><div><br></div><div><div>class WalkableBinTree n where</div><div>&nbsp; wbtChildren :: n d -&gt; Maybe (n d, n d)</div><div>&nbsp; wbtData &nbsp; &nbsp; :: n d -&gt; Maybe d</div><div><br></div><div>instance WalkableBinTree BT where</div><div>&nbsp; wbtChildren (Branch d l r) = Just (l, r)</div><div>&nbsp; wbtChildren &nbsp;Empty &nbsp; &nbsp; &nbsp; &nbsp; = Nothing</div><div><br></div><div>&nbsp; wbtData &nbsp; &nbsp; (Branch d l r) = Just d</div><div>&nbsp; wbtData &nbsp; &nbsp; &nbsp;Empty &nbsp; &nbsp; &nbsp; &nbsp; = Nothing</div></div><div><br></div><div>Notice that now, the class is instantiated for "BT" and *not* "(BT x)".</div><div><br></div></div><blockquote type="cite">As far as I remember, none of the tutorials I've read have done this kind of thing - but it seemed an obvious thing to do. Obviously in the real world I should just use library containers, but this is about learning Haskell better in case a similar problem arises that isn't about binary trees.<br></blockquote><div><br></div><div>A good way to learn a lot about type classes is to study the default library. Admittedly, this can be a bit of a daunting task to just dive in. Luckily, Brent Yorgey wrote up a nice article that was transferred and updated by numerous people on the HaskellWiki. It's worth giving it a read:</div><div><br></div><div><a href="http://www.haskell.org/haskellwiki/Typeclassopedia">http://www.haskell.org/haskellwiki/Typeclassopedia</a></div><div><br></div><div>Happy Haskelling!</div><div><br></div><div>Regards,</div><div>Philip</div><div><br></div></div></div></body></html>