tag:blogger.com,1999:blog-18192802773675248662024-03-08T09:34:45.907-08:00The power of types compels youPaczesiowahttp://www.blogger.com/profile/14436047943969802962noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-1819280277367524866.post-12914174600330953742011-11-06T12:41:00.000-08:002011-11-06T17:18:45.438-08:00Virtual Haskell EnvironmentI am pleased to announce the first public release of the <a href="http://hackage.haskell.org/package/virthualenv">virthualenv</a> tool.<br /><br />virthualenv is a tool (inspired by Python's virtualenv) to create isolated Haskell environments, similar in purpose to tools like cabal-dev. You can read more about it on <a href="http://hackage.haskell.org/package/virthualenv">hackage</a>, or in README, available on <a href="https://github.com/Paczesiowa/virthualenv">github</a>.<br /><br />Why did I bother with writing it, when there's already cabal-dev available? Back in July, I decided to start writing in Haskell again, so I picked up one of my projects and tried to build it. But as usual, too many installed packages and it failed. I knew, I needed something to keep separate environments for every project, something like Python's virtualenv. There were two such tools for Haskell: capri and cabal-dev. capri was just a toy. cabal-dev was unusable on two (all of them) of my projects, for two different reasons (I have to mention, that cabal-dev >= 0.8 works fine). But even if cabal-dev would work back then, I hated the way it worked/works. Before I understood why it wouldn't work with my project (no cabal configure flag switches), I had to consult the readme file, seek help on #haskell. Python's virtualenv was simpler, I had to learn two commands and the environment was ready and activated, then I could work as I worked with Python code before using virtualenv. No new commands, no new switches, no manual reading — it just worked. I wanted something like this for Haskell. After reading capri sources I realized, that it was really easy (and cabal-dev was overcomplicated) and I could create a bash script to do it in a couple of hours. And I did. Then I rewrote it in Haskell, made it user-friendly and added new features. The only thing missing was a README file. Unfortunately (for the project, for me it was very fortunate), some things happened and I didn't have the time and/or motivation to finish the project. But I was tired of having so many dead projects and decided to finally release it.<br /><br />Is it still needed when cabal-dev-0.8 is in a usable state? I think so. Here's why:<br /><br />* It's simpler than cabal-dev so there's less code.<br />* It's simpler to use, regular user can create an environment with a single word command, activate it using another, provided command and then can work just like he's used to. "How do I install a package?" — "Use 'cabal install'.". "How do I check what packages are installed?" — "Use 'ghc-pkg list'.". "How do I ...?" — "Like you always did".<br />* It will be familiar to people coming from Python.<br />* Because of its nature (manipulating environment vars), you continue to use the same binaries (or wrappers). This means things like bash completion continue to work without any extra setup.<br />* There's a simple emacs mode included (virthualenv.el). It was trivial to write, even for such an elisp-noob like me. It was simple because of how simple setting two env vars is, there was no need to modify haskell-mode at all. Emacs integration is very important for me, maybe other emacs people are ok with using cabal-dev only from the terminal, but I prefer typechecking my code using simple keyboard shortcut from emacs, with the regular things like jumping to error locations and other goodies. ghci embedded in emacs also works just fine. I don't know what vimers do with Haskell code, but it's probably equally trivial to write a vim plugin for virthualenv (just fork a virtualenv plugin and you'll be 80% done).<br />* There's a nice feature, not available in cabal-dev — using external GHC from compiled tarball. It's the easiest way (or so I believe) to do things like testing your code with a different version of GHC (even nightly builds!).<br /><br />Are there any disadvantages to using this over cabal-dev? Unfortunately yes. First, it's a new project, it hasn't been tested by anyone beside me, so there can be bugs (please report them on <a href="https://github.com/Paczesiowa/virthualenv/issues">github</a>). The bigger disadvantage is portability. I've tested it only on i386 Linux and FreeBSD (a little). It should work on every Linux, if it doesn't, I can probably fix it. Other unices like *BSD, Solaris and whatever else is there should also work, but I haven't tested it, due to no available machines with those OSes. It could work on MacOS X using system's GHC (already installed one) (at least I think so, since it's derived from BSD). MacOS X and GHC from tarball will probably not work, since it doesn't use regular tarballs, and I have no idea how those .dmg files work. As usual, Windows works completely different, so it would need some research and probably a lot of new code to make it work there.<br /><br />What will I do with this project? Currently, it satisfies all my needs, so I can focus on other projects. But, if other people (it means you!) start to use it, I will try to fix all bugs, develop some new features (I have a few ideas on <a href="https://github.com/Paczesiowa/virthualenv/issues">github</a>, but you can tell me yours as well) and work on porting it to MacOS X and Windows (I'd need access to such machines though).Paczesiowahttp://www.blogger.com/profile/14436047943969802962noreply@blogger.com6tag:blogger.com,1999:blog-1819280277367524866.post-8925561964556901042010-07-12T07:17:00.000-07:002010-07-12T11:20:53.509-07:00Two-Dimensional Analog Literals in Haskell<pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">module</span> <span style="">Intro</span> <span style="color: blue; font-weight: bold;">where</span><br /></code></pre><p>Hello! If you were wondering what happened to me and why I've stopped posting, well, I was found guilty on type abuse charges and was sentenced to three months in maximum type security prison of Coq. Since I'm such a degenerate, I've loved every minute of it. And there were plenty of things to abuse on the inside. Now, I've been released, but I can't believe how fast things move on the outside. I saw an automobile once when I was a kid, but now they're everywhere. And SPJ thinks that <a href="http://thread.gmane.org/gmane.comp.lang.haskell.cafe/77116">OverlappingInstances are unsound</a>. It's been a while, since I made a new post, so I decided, that because of <a href="http://www.reddit.com/r/haskell/comments/cl8d3/quasiquoting_ascii_art_to_define_data_structures/c0td06j">recent events</a> I could make a new post<a href="http://www.youtube.com/watch?v=Yavx9yxTrsw">.</a></p><p>Over a year ago, <a href="http://www.xs4all.nl/~weegen/eelis/analogliterals.xhtml">this post</a> was all the rage on <a href="http://www.reddit.com/r/programming/comments/75bxi/multidimensional_analog_literals_the_reason_why_c/">reddit</a>. The original implementation used C++ and redditors contributed code in such godless languages like Python and Ruby. There was no Haskell solution and we can't have that, can we? I'm going to present two solutions, to prove that it's possible in ML-like languages, and by using Haskell extensions, it's possible to have some advantages over the original implementation. I've limited myself only to rectangles, because lines are boring and cuboids are too hard to even "draw". Here's an example for the impatient:</p><pre><code><span style="">rectangle</span> <span style="color: red;">=</span> <span style="">begin</span><br /> <span style="">o</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span style="">o</span><br /> <span class="hs-sel">ǀ</span> <span class="hs-sel">ǀ</span><br /> <span class="hs-sel">ǀ</span> <span class="hs-sel">ǀ</span><br /> <span style="">o</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span style="">o</span><br /> <span style="">end</span></code></pre><p>If it looks broken, it's because it uses two unusual unicode characters (like "LATIN LETTER DENTAL CLICK"), if your browser or font (or my mad web skills) can't handle it, here's a <a href="http://imgur.com/FMj9r">picture</a>.</p><p>What's so hard about Haskell implementation of those literals? In languages with ML-like syntax, there can't be two operators next to each other and there are no (usable) postfix operators, so the original idea of overloading decrement and subtraction operators fails already on the syntax level. Unless we want to alternate glyphs between operators and identifiers, which seems a bit against the spirit of this hack, it's clear that the solution has to rely on a sequence of single-char combinators, delimited with spaces (otherwise it would be just one token). It helps if those combinators use letters, that look like operators (it's possible in GHC).</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">module</span> <span style="">PostCombinator</span><span style="color: red;">(</span><span style="">post</span><span style="color: red;">)</span> <span style="color: blue; font-weight: bold;">where</span><br /></code></pre><p>Before we start, let's talk about this programming style, that I like to call applicative pointfree/pointless. Here's couple functions to calculate reversed list of odd squares:</p><pre><code><span style="">></span> <span style="">square</span> <span style="">x</span> <span style="color: red;">=</span> <span style="">x</span><span style="">*</span><span style="">x</span><br /><span style="">></span> <span style="">odds</span> <span style="color: red;">=</span> <span style="">filter</span> <span style="">odd</span><br /><span style="">></span> <span style="">squares</span> <span style="color: red;">=</span> <span style="">map</span> <span style="">square</span><br /><span style="">></span> <span style="">oddSquares1</span> <span style="">xs</span> <span style="color: red;">=</span> <span style="">reverse</span> <span style="color: red;">(</span><span style="">odds</span> <span style="color: red;">(</span><span style="">squares</span> <span style="">xs</span><span style="color: red;">)</span><span style="color: red;">)</span><br /><span style="">></span> <span style="">oddSquares2</span> <span style="">xs</span> <span style="color: red;">=</span> <span style="">reverse</span> <span style="">$</span> <span style="">odds</span> <span style="">$</span> <span style="">squares</span> <span style="">xs</span><br /><span style="">></span> <span style="">oddSquares3</span> <span style="color: red;">=</span> <span style="">reverse</span> <span style="">.</span> <span style="">odds</span> <span style="">.</span> <span style="">squares</span><br /></code></pre><p>It's composed of three sub-programs in a good functional style. Category-theory guys would tell you, that the third one is <em>pointfree</em>, but you don't have to be a rocket-scientist to notice, that it's the only solution actually containing points. But don't tell that to CT people, they will answer "does not commute!" and their head will explode. The common thing about those functions is this: sub-expressions are delimited or explicitly composed (be it with '.', '$' or opening paren). It would be nice, to be able to write only function names, without any boiler-plate in between, and make it magically combine itself.</p><p>I've discovered a way to achieve this goal. It's really beautiful, it's based on very smart people results, there are continuations involved and it has interesting connections with concatenative languages like Factor - all the ingredients of a great paper. Unfortunately (for me), Chris Okasaki already took care of it - <a href="http://www.eecs.usma.edu/webs/people/okasaki/hw02.ps">Techniques for Embedding Postfix Languages in Haskell</a>. I encourage you to read it yourself, but here's a quick roundup of this technique.</p><p>We want a function <em>odds'</em>, that will be able to use directly the immediately following sub-program, without any composition means. It must take two arguments: <em>x</em> - the usual input and <em>k</em> - the continuation (Okasaki calls it a partial continuation) that is, the next expression. The following order of those arguments is the easier one:</p><pre><code><span style="">odds'</span> <span style="">x</span> <span style="">k</span> <span style="color: red;">=</span> <span style="">...</span></code></pre><p>On the right hand side, the obvious thing to do with x is to filter odd numbers from x:</p><pre><code><span style="">odds'</span> <span style="">x</span> <span style="">k</span> <span style="color: red;">=</span> <span style="">...</span><br /> <span style="color: blue; font-weight: bold;">where</span> <span style="">y</span> <span style="color: red;">=</span> <span style="">filter</span> <span style="">odd</span> <span style="">x</span></code></pre><p>Now, we have an output of this sub-computation, the only sensible thing to do is to apply it to the next computation:</p><pre><code><span style="">></span> <span style="">odds'</span> <span style="color: red;">::</span> <span style="color: red;">[</span><span style="">Int</span><span style="color: red;">]</span> <span style="color: red;">-></span> <span style="color: red;">(</span><span style="color: red;">[</span><span style="">Int</span><span style="color: red;">]</span> <span style="color: red;">-></span> <span style="">t</span><span style="color: red;">)</span> <span style="color: red;">-></span> <span style="">t</span><br /><span style="">></span> <span style="">odds'</span> <span style="">x</span> <span style="">k</span> <span style="color: red;">=</span> <span style="">k</span> <span style="">y</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">where</span> <span style="">y</span> <span style="color: red;">=</span> <span style="">filter</span> <span style="">odd</span> <span style="">x</span><br /></code></pre><pre><code><span style="">></span> <span style="">squares'</span><span style="color: red;">,</span> <span style="">doubles'</span> <span style="color: red;">::</span> <span style="color: red;">[</span><span style="">Int</span><span style="color: red;">]</span> <span style="color: red;">-></span> <span style="color: red;">(</span><span style="color: red;">[</span><span style="">Int</span><span style="color: red;">]</span> <span style="color: red;">-></span> <span style="">t</span><span style="color: red;">)</span> <span style="color: red;">-></span> <span style="">t</span><br /><span style="">></span> <span style="">squares'</span> <span style="">x</span> <span style="">k</span> <span style="color: red;">=</span> <span style="">k</span> <span style="">y</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">where</span> <span style="">y</span> <span style="color: red;">=</span> <span style="">map</span> <span style="">square</span> <span style="">x</span><br /></code></pre><pre><code><span style="">></span> <span style="">doubles'</span> <span style="">x</span> <span style="">k</span> <span style="color: red;">=</span> <span style="">k</span> <span style="">$</span> <span style="">map</span> <span style="color: red;">(</span><span style="">*</span><span class="hs-num">2</span><span style="color: red;">)</span> <span style="">x</span><br /></code></pre><p>Now we can compose these expressions:</p><pre><code>*PostCombinator> :t odds' [1..10]<br />odds' [1..10] :: ([Int] -> t) -> t<br />*PostCombinator> :t odds' [1..10] squares'<br />odds' [1..10] squares' :: ([Int] -> t) -> t<br />*PostCombinator> :t odds' [1..10] squares' doubles'<br />odds' [1..10] squares' doubles' :: ([Int] -> t) -> t</code></pre><p>In order to not make special case of the first part, by applying to it the initial <em>state</em>, that gets transformed by the whole pipeline, we can add special combinator, that will apply that initial state to the first case:</p><pre><code><span style="">></span> <span style="">begin</span> <span style="">x</span> <span style="">k</span> <span style="color: red;">=</span> <span style="">k</span> <span style="">x</span><br /></code></pre><p>We finish the pipeline computation by adding the final continuation, e.g. <em>id</em>, but any other function would be fine too.</p><pre><code>*PostCombinator> (begin [1..10]) odds' squares' doubles' id<br />[2,18,50,98,162]</code></pre><p>I call this style applicative pointfree, because composition is based on application and there are no points, or any other delimiters.</p><p>We can abstract the pattern from <em>odds'</em>, <em>squares'</em> and <em>doubles'</em> functions. Okasaki calls this combinator <em>post</em>:</p><pre><code><span style="">></span> <span style="">post</span> <span style="color: red;">::</span> <span style="color: red;">(</span><span style="">a</span> <span style="color: red;">-></span> <span style="">b</span><span style="color: red;">)</span> <span style="color: red;">-></span> <span style="">a</span> <span style="color: red;">-></span> <span style="color: red;">(</span><span style="">b</span> <span style="color: red;">-></span> <span style="">t</span><span style="color: red;">)</span> <span style="color: red;">-></span> <span style="">t</span><br /><span style="">></span> <span style="">post</span> <span style="">f</span> <span style="color: red;">=</span> <span style="color: red;">\</span><span style="">x</span> <span style="">k</span> <span style="color: red;">-></span> <span style="">k</span> <span style="">$</span> <span style="">f</span> <span style="">x</span><br /></code></pre><p>Explicit usage of <em>post</em>, while possible, doesn't make much sense, because you still have to use parens, it's better suited for creating wrappers around simple functions.</p><pre><code>*PostCombinator> begin [1..10] (post$ filter odd) (post$ map square) (post$ map (*2)) reverse<br />[162,98,50,18,2]</code></pre><p>If you want to learn more about this style, you should read <a href="http://www.eecs.usma.edu/webs/people/okasaki/hw02.ps">Techniques for Embedding Postfix Languages in Haskell</a>, <a href="http://www.eecs.usma.edu/webs/people/okasaki/jfp03.ps">Flattening combinators: surviving without parentheses</a> and the classic <a href="http://www.brics.dk/RS/98/12/BRICS-RS-98-12.pdf">Functional Unparsing</a> wouldn't hurt either, because it lays the foundations. But be careful, you don't want to start coding in Factor.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">module</span> <span style="">DynamicLiterals</span> <span style="color: blue; font-weight: bold;">where</span><br /></code></pre><p>The first solution is very simple, it should work in any ML-like language (I've tested it in Haskell and OCaml), because it only requires Hindley-Milner type system. If the implementation doesn't support unicode identifiers, rectangles have to be drawn with other characters though. I call it dynamic solution, because though it does work for correct rectangles, it produces wrong results (at runtime) for wrong combinator sequences, that don't represent rectangles.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">import</span> <span style="">PostCombinator</span><br /></code></pre><p>There are three different parts of a rectangle and each gets a combinator. These combinators will transform the rectangle state, consisting of width, current width and height (shortened to w,cw and h respectively):</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">type</span> <span style="">RectState</span> <span style="color: red;">=</span> <span style="color: red;">(</span><span style="">Int</span><span style="color: red;">,</span> <span style="">Int</span><span style="color: red;">,</span> <span style="">Int</span><span style="color: red;">)</span><br /></code></pre><pre><code><span style="">></span> <span style="">corner</span><span style="color: red;">,</span> <span style="">dash</span><span style="color: red;">,</span> <span style="">bar</span> <span style="color: red;">::</span> <span style="">RectState</span> <span style="color: red;">-></span> <span style="">RectState</span><br /></code></pre><pre><code><span style="">></span> <span style="">dash</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">)</span> <span style="color: red;">=</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span> <span style="">+</span> <span class="hs-num">1</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">)</span><br /><span style="">></span> <span style="">bar</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">)</span> <span style="color: red;">=</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span> <span style="">+</span> <span class="hs-num">1</span><span style="color: red;">)</span><br /><span style="">></span> <span style="">corner</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">)</span> <span style="color: red;">=</span> <span style="color: red;">(</span><span style="">w</span> <span style="">`max`</span> <span style="">cw</span><span style="color: red;">,</span> <span class="hs-num">0</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">)</span><br /></code></pre><p><em>dash</em> and <em>bar</em> are obvious, corner takes maximum of width and current width to account for transition from sequence of bars (that didn't touch current width) to corner.</p><p>We wrap these functions with our <em>post</em> combinator:</p><pre><code><span style="">></span> <span style="">c</span><span style="color: red;">,</span> <span style="">d</span><span style="color: red;">,</span> <span style="">b</span> <span style="color: red;">::</span> <span style="">RectState</span> <span style="color: red;">-></span> <span style="color: red;">(</span><span style="">RectState</span> <span style="color: red;">-></span> <span style="">t</span><span style="color: red;">)</span> <span style="color: red;">-></span> <span style="">t</span><br /><span style="">></span> <span style="">c</span> <span style="color: red;">=</span> <span style="">post</span> <span style="">corner</span><br /><span style="">></span> <span style="">d</span> <span style="color: red;">=</span> <span style="">post</span> <span style="">dash</span><br /><span style="">></span> <span style="">b</span> <span style="color: red;">=</span> <span style="">post</span> <span style="">bar</span><br /></code></pre><p>All that's left are definitions of the first combinator, that starts the process, and the final continuation:</p><pre><code><span style="">></span> <span style="">beginRect</span> <span style="color: red;">::</span> <span style="color: red;">(</span><span style="">RectState</span> <span style="color: red;">-></span> <span style="">t</span><span style="color: red;">)</span> <span style="color: red;">-></span> <span style="">t</span><br /><span style="">></span> <span style="">beginRect</span> <span style="">k</span> <span style="color: red;">=</span> <span style="">k</span> <span style="color: red;">(</span><span class="hs-num">0</span><span style="color: red;">,</span> <span class="hs-num">0</span><span style="color: red;">,</span> <span class="hs-num">0</span><span style="color: red;">)</span><br /></code></pre><pre><code><span style="">></span> <span style="">endRect</span> <span style="color: red;">::</span> <span style="">RectState</span> <span style="color: red;">-></span> <span style="color: red;">(</span><span style="">Int</span><span style="color: red;">,</span> <span style="">Int</span><span style="color: red;">)</span><br /><span style="">></span> <span style="">endRect</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">)</span> <span style="color: red;">=</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">h</span> <span style="">`div`</span> <span class="hs-num">2</span><span style="color: red;">)</span><br /></code></pre><p>Now we can <em>draw</em> pretty rectangles:</p><pre><code><span style="">></span> <span style="">rect</span> <span style="color: red;">=</span> <span style="">beginRect</span><br /><span style="">></span> <span style="">c</span> <span style="">d</span> <span style="">d</span> <span style="">d</span> <span style="">d</span> <span style="">c</span><br /><span style="">></span> <span style="">b</span> <span style="">b</span><br /><span style="">></span> <span style="">b</span> <span style="">b</span><br /><span style="">></span> <span style="">b</span> <span style="">b</span><br /><span style="">></span> <span style="">c</span> <span style="">d</span> <span style="">d</span> <span style="">d</span> <span style="">d</span> <span style="">c</span><br /><span style="">></span> <span style="">endRect</span><br /></code></pre><pre><code>*DynamicLiterals> rect<br />(4,3)</code></pre><p>Unfortunately, since there are no requirements on these combinators, they will be perfectly happy to transform any sequence of rectangle states:</p><pre><code><span style="">></span> <span style="">lambda</span> <span style="color: red;">=</span> <span style="">beginRect</span><br /><span style="">></span> <span style="">d</span><br /><span style="">></span> <span style="">b</span> <span style="">d</span><br /><span style="">></span> <span style="">b</span><br /><span style="">></span> <span style="">d</span> <span style="">d</span><br /><span style="">></span> <span style="">d</span> <span style="">d</span> <span style="">b</span><br /><span style="">></span> <span style="">d</span> <span style="">c</span><br /><span style="">></span> <span style="">endRect</span><br /></code></pre><pre><code>*DynamicLiterals> lambda<br />(7,1)</code></pre><p>It's worth mentioning that this solution (and the next one) doesn't scale - the types are huge, in the smallest proper rectangle (1x1), the first corner combinator <em>c</em> has a type, that takes over 250 lines when printed by ghci. This makes type checking extremely slow for bigger examples. Memory usage varies by implementation, ghc for 4x4 rectangle needs 500 mb of memory (I don't have a machine capable of checking 5x5), while OCaml still takes a long time to compute the type, but it doesn't use any significant amount of memory.</p><p>Now it's time for the second solution. This is Haskell after all, find a problem and make it statically impossible to violate. There will be also a few advantages over original C++ implementation.</p><p>While we can't forbid drawing rectangles like the lambda letter, because there's no access to the lexer at the type level (but can you imagine the possibilities?), we can forbid usage of incorrect sequences (e.g. dash following bar). This of course needs a bit of type level programming, but there's nothing really hacky and abusive.</p><pre><code><span style="">></span> <span style="color: green;">{-# LANGUAGE NoMonomorphismRestriction<br />> , OverlappingInstances<br />> , FlexibleInstances<br />> , FlexibleContexts<br />> , UndecidableInstances<br />> , ScopedTypeVariables<br />> , MultiParamTypeClasses<br />> , FunctionalDependencies<br />> , EmptyDataDecls<br />> #-}</span><br /></code></pre><p>Base implementation only uses MPTCs+FunDeps (and UndecidableInstances, but I'm pretty sure this could be solved without them), so it's probably doable with all those new hip TypeFamilies. OverlappingInstances and UndecidableInstances are needed for nice error messages though, but don't worry, any instance choice, that requires UndecidableInstances will result in a type error - but a pretty one!</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">module</span> <span style="">StaticLiterals</span> <span style="color: blue; font-weight: bold;">where</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">import</span> <span style="">Prelude</span> <span style="">hiding</span> <span style="color: red;">(</span><span style="">Either</span><span style="color: red;">(</span><span style="color: red;">..</span><span style="color: red;">)</span><span style="color: red;">)</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">import</span> <span style="">Peano</span><br /></code></pre><p>Let's take a look at the type of the dash combinator from the previous solution:</p><pre><code><span style="">d</span> <span style="color: red;">::</span> <span style="">RectState</span> <span style="color: red;">-></span> <span style="color: red;">(</span><span style="">RectState</span> <span style="color: red;">-></span> <span style="">t</span><span style="color: red;">)</span> <span style="color: red;">-></span> <span style="">t</span></code></pre><p>One of the situations, we wish to forbid, is having bottom side of different length than the top side. This clearly requires tracking rectangle's width at the type level. Since we have to carry the rectangle state through types, there's no need to carry it at the value level, so the RectState argument isn't needed anymore. So, we're left with <em>(t) -> t</em>, and we have to attach type-level equivalent of RectState.</p><p>The first <em>t</em> is the continuation. The problem is, that it takes any continuation, so dash followed by bar type checks just fine. Since all three combinator have the same type, we have to do something to be able to distinguish between them. We're going to wrap every continuation type in a newtype wrapper with a phantom type tag, telling what kind of combinator this is.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">Corner</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">Dash</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">Bar</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">End</span><br /></code></pre><p>Besides width, current width and height we have to carry a position in the rectangle, because e.g. dash can follow the first corner, but it cannot follow the second. Our type level state will be a 4-tuple of 3 Peano numbers and a position.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">Top</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">Bottom</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">Left</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">Right</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">TopLeft</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">TopRight</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">BottomLeft</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">BottomRight</span><br /></code></pre><p>Our continuation wrapper:</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">newtype</span> <span style="">TagCont</span> <span style="">tag</span> <span style="">rectState</span> <span style="">k</span> <span style="color: red;">=</span> <span style="">TagCont</span> <span style="color: red;">{</span> <span style="">unTagCont</span> <span style="color: red;">::</span> <span style="">k</span> <span style="color: red;">}</span><br /></code></pre><p>Now it's time for some type level computations, this is the only class (unfortunately, /dev/meaningfull_names run out of entropy). This class contains the combinator, that will work like all three, because interesting things will happen only at the type level. This class is parameterized by the tag of the combinator, the tag of the following combinator, the type level rectangle state input, and those arguments determine the resulting state.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">class</span> <span style="">Rectangly</span> <span style="">tag</span> <span style="">nextTag</span> <span style="">inpState</span> <span style="">outState</span> <span style="color: red;">|</span> <span style="">tag</span> <span style="">nextTag</span> <span style="">inpState</span> <span style="color: red;">-></span> <span style="">outState</span> <span style="color: blue; font-weight: bold;">where</span><br /></code></pre><p>The <em>r</em> combinator is still of that <em>t -> t</em> type, but that function is tagged with the combinator tag (e.g. Dash), and the inner (left) <em>t</em> is tagged with the tag of the next combinator. State of one combinator determines (together with tags) the state of the following (next) one.</p><pre><code><span style="">></span> <span style="">r</span> <span style="color: red;">::</span> <span style="">TagCont</span> <span style="">tag</span> <span style="">inpState</span> <span style="color: red;">(</span><span style="">TagCont</span> <span style="">nextTag</span> <span style="">outState</span> <span style="">t</span> <span style="color: red;">-></span> <span style="">t</span><span style="color: red;">)</span><br /></code></pre><p>At the value level, all combinators work the same, just tag untagging function, so if we disregard newtypes with phantom arguments, this is just identity function, where everything interesting is happening at the type level.</p><pre><code><span style="">></span> <span style="">r</span> <span style="color: red;">=</span> <span style="">TagCont</span> <span style="">unTagCont</span><br /></code></pre><p>All the instances follow the same pattern: dispatching on the rectangle part, tag of the current combinator, tag of the next combinator, accepting any width, current width and height, and computing from that resulting values and next rectangle part.</p><p>This one says, that after Corner we can use Bar, but only in the TopRight part (it's certainly not true at any other corner). Current width (calculated by sequence of dashes) becomes our new width, we reset current width and set the rectangle part to Left.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Rectangly</span> <span style="">Corner</span> <span style="">Bar</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">TopRight</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">cw</span><span style="color: red;">,</span> <span style="">Z</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">Left</span><span style="color: red;">)</span><br /></code></pre><p>The rest is very similar:</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Rectangly</span> <span style="">Corner</span> <span style="">Dash</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">TopLeft</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">Top</span><span style="color: red;">)</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Rectangly</span> <span style="">Corner</span> <span style="">Dash</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">BottomLeft</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">w</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">Bottom</span><span style="color: red;">)</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Rectangly</span> <span style="">Corner</span> <span style="">End</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">BottomRight</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">Bottom</span><span style="color: red;">)</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Rectangly</span> <span style="">Dash</span> <span style="">Dash</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">Top</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="color: red;">(</span><span style="">S</span> <span style="">cw</span><span style="color: red;">)</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">Top</span><span style="color: red;">)</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Rectangly</span> <span style="">Dash</span> <span style="">Corner</span><span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">Top</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="color: red;">(</span><span style="">S</span> <span style="">cw</span><span style="color: red;">)</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">TopRight</span><span style="color: red;">)</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Rectangly</span> <span style="">Dash</span> <span style="">Dash</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="color: red;">(</span><span style="">S</span> <span style="">cw</span><span style="color: red;">)</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">Bottom</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">Bottom</span><span style="color: red;">)</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Rectangly</span> <span style="">Dash</span> <span style="">Corner</span><span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="color: red;">(</span><span style="">S</span> <span style="">Z</span><span style="color: red;">)</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">Bottom</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">BottomRight</span><span style="color: red;">)</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Rectangly</span> <span style="">Bar</span> <span style="">Bar</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">Left</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">Right</span><span style="color: red;">)</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Rectangly</span> <span style="">Bar</span> <span style="">Bar</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">Right</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="color: red;">(</span><span style="">S</span> <span style="">h</span><span style="color: red;">)</span><span style="color: red;">,</span> <span style="">Left</span><span style="color: red;">)</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Rectangly</span> <span style="">Bar</span> <span style="">Corner</span><span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">Right</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="color: red;">(</span><span style="">S</span> <span style="">h</span><span style="color: red;">)</span><span style="color: red;">,</span> <span style="">BottomLeft</span><span style="color: red;">)</span><br /></code></pre><p>Of course, it's not possible to build rectangles with a single combinator (without explicit type sigs everywhere), because the tag of the combinator is polymorphic so there would be an overlap. Binding these three combinators to the <em>r</em> requires specializing the type to the specific tag:</p><pre><code><span style="">></span> <span style="">o</span> <span style="color: red;">::</span> <span style="">Rectangly</span> <span style="">Corner</span> <span style="">nextTag</span> <span style="">inpState</span> <span style="">outState</span> <span style="color: red;">=></span> <span style="">TagCont</span> <span style="">Corner</span> <span style="">inpState</span> <span style="color: red;">(</span><span style="">TagCont</span> <span style="">nextTag</span> <span style="">outState</span> <span style="">t</span> <span style="color: red;">-></span> <span style="">t</span><span style="color: red;">)</span><br /><span style="">></span> <span style="">o</span> <span style="color: red;">=</span> <span style="">r</span><br /></code></pre><pre><code><span style="">></span> <span class="hs-sel">ᜭ</span> <span style="color: red;">::</span> <span style="">Rectangly</span> <span style="">Dash</span> <span style="">nextTag</span> <span style="">inpState</span> <span style="">outState</span> <span style="color: red;">=></span> <span style="">TagCont</span> <span style="">Dash</span> <span style="">inpState</span> <span style="color: red;">(</span><span style="">TagCont</span> <span style="">nextTag</span> <span style="">outState</span> <span style="">t</span> <span style="color: red;">-></span> <span style="">t</span><span style="color: red;">)</span><br /><span style="">></span> <span class="hs-sel">ᜭ</span> <span style="color: red;">=</span> <span style="">r</span><br /></code></pre><pre><code><span style="">></span> <span class="hs-sel">ǀ</span> <span style="color: red;">::</span> <span style="">Rectangly</span> <span style="">Bar</span> <span style="">nextTag</span> <span style="">inpState</span> <span style="">outState</span> <span style="color: red;">=></span> <span style="">TagCont</span> <span style="">Bar</span> <span style="">inpState</span> <span style="color: red;">(</span><span style="">TagCont</span> <span style="">nextTag</span> <span style="">outState</span> <span style="">t</span> <span style="color: red;">-></span> <span style="">t</span><span style="color: red;">)</span><br /><span style="">></span> <span class="hs-sel">ǀ</span> <span style="color: red;">=</span> <span style="">r</span><br /></code></pre><p>All that's left is <em>begin</em> for starting the process and <em>end</em> - the final continuation.</p><pre><code><span style="">></span> <span style="">begin</span> <span style="color: red;">::</span> <span style="">TagCont</span> <span style="">Corner</span> <span style="color: red;">(</span><span style="">Z</span><span style="color: red;">,</span> <span style="">Z</span><span style="color: red;">,</span> <span style="">Z</span><span style="color: red;">,</span> <span style="">TopLeft</span><span style="color: red;">)</span> <span style="">t</span> <span style="color: red;">-></span> <span style="">t</span><br /><span style="">></span> <span style="">begin</span> <span style="color: red;">=</span> <span style="">unTagCont</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">Rectangle</span> <span style="">w</span> <span style="">h</span> <span style="color: red;">=</span> <span style="">Rectangle</span> <span style="">Int</span> <span style="">Int</span> <span style="color: blue; font-weight: bold;">deriving</span> <span style="">Show</span><br /><span style="">></span> <span style="">area</span> <span style="color: red;">(</span><span style="">Rectangle</span> <span style="">w</span> <span style="">h</span><span style="color: red;">)</span> <span style="color: red;">=</span> <span style="">w</span> <span style="">*</span> <span style="">h</span><br /></code></pre><p><em>end</em> calculates the rectangle with phantom types set to its Peano dimensions, and corresponding integers at the value level.</p><pre><code><span style="">></span> <span style="">end</span> <span style="color: red;">::</span> <span style="color: blue; font-weight: bold;">forall</span> <span style="">w</span> <span style="">cw</span> <span style="">h</span> <span style="">s</span><span style="">.</span> <span style="color: red;">(</span><span style="">NatToInt</span> <span style="">w</span><span style="color: red;">,</span> <span style="">NatToInt</span> <span style="">h</span><span style="color: red;">)</span> <span style="color: red;">=></span> <span style="">TagCont</span> <span style="">End</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">s</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">Rectangle</span> <span style="">w</span> <span style="">h</span><span style="color: red;">)</span><br /><span style="">></span> <span style="">end</span> <span style="color: red;">=</span> <span style="">TagCont</span> <span style="">$</span> <span style="">Rectangle</span> <span style="color: red;">(</span><span style="">natToInt</span> <span style="color: red;">(</span><span style="">undefined</span> <span style="color: red;">::</span> <span style="">w</span><span style="color: red;">)</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">natToInt</span> <span style="color: red;">(</span><span style="">undefined</span> <span style="color: red;">::</span> <span style="">h</span><span style="color: red;">)</span><span style="color: red;">)</span><br /></code></pre><p>This is enough to define the following rectangle:</p><pre><code><span style="">></span> <span style="">rectangle</span> <span style="color: red;">=</span> <span style="">begin</span><br /><span style="">></span> <span style="">o</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span style="">o</span><br /><span style="">></span> <span class="hs-sel">ǀ</span> <span class="hs-sel">ǀ</span><br /><span style="">></span> <span class="hs-sel">ǀ</span> <span class="hs-sel">ǀ</span><br /><span style="">></span> <span style="">o</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span style="">o</span><br /><span style="">></span> <span style="">end</span><br /></code></pre><p>The first advantage over the original implementation is the correctness, it's probably a bug, but C++ version doesn't detect the odd number of bars, and what's worse, it calculates them incorrectly in such a case:</p><pre class="sourceCode Cpp"><code><span class="Normal NormalText"> </span><span class="DataType DataType">unsigned</span><span class="Normal NormalText"> </span><span class="DataType DataType">int</span><span class="Normal NormalText"> r1 </span><span class="Normal Symbol">=</span><span class="Normal NormalText"> </span><span class="Normal Symbol">(</span><span class="Normal NormalText"> o</span><span class="Normal Symbol">-----</span><span class="Normal NormalText">o</span><br /><span class="Normal NormalText"> </span><span class="Normal Symbol">|</span><span class="Normal NormalText"> </span><span class="Normal Symbol">!</span><br /><span class="Normal NormalText"> </span><span class="Normal Symbol">!</span><span class="Normal NormalText"> </span><span class="Normal Symbol">!</span><span class="Normal NormalText"> </span><span class="Normal Symbol">!</span><br /><span class="Normal NormalText"> </span><span class="Normal Symbol">!</span><span class="Normal NormalText"> </span><span class="Normal Symbol">!</span><br /><span class="Normal NormalText"> o</span><span class="Normal Symbol">-----</span><span class="Normal NormalText">o </span><span class="Normal Symbol">).</span><span class="Normal NormalText">area</span><span class="Normal Symbol">;</span><br /><br /><span class="Normal NormalText"> </span><span class="DataType DataType">unsigned</span><span class="Normal NormalText"> </span><span class="DataType DataType">int</span><span class="Normal NormalText"> r2 </span><span class="Normal Symbol">=</span><span class="Normal NormalText"> </span><span class="Normal Symbol">(</span><span class="Normal NormalText"> o</span><span class="Normal Symbol">-----</span><span class="Normal NormalText">o</span><br /><span class="Normal NormalText"> </span><span class="Normal Symbol">|</span><span class="Normal NormalText"> </span><span class="Normal Symbol">!</span><br /><span class="Normal NormalText"> </span><span class="Normal Symbol">!</span><span class="Normal NormalText"> </span><span class="Normal Symbol">!</span><br /><span class="Normal NormalText"> </span><span class="Normal Symbol">!</span><span class="Normal NormalText"> </span><span class="Normal Symbol">!</span><br /><span class="Normal NormalText"> o</span><span class="Normal Symbol">-----</span><span class="Normal NormalText">o </span><span class="Normal Symbol">).</span><span class="Normal NormalText">area</span><span class="Normal Symbol">;</span><br /><br /><span class="Normal NormalText"> assert </span><span class="Normal Symbol">(</span><span class="Normal NormalText">r1 </span><span class="Normal Symbol">==</span><span class="Normal NormalText"> r2</span><span class="Normal Symbol">);</span><br /></code></pre><p>Another advantage is what the author calls <em>storing these literals directly in a variable</em>, there's no need to explicitly provide a type, it is inferred automatically:</p><pre><code><span style="">></span> <span style="">r2</span> <span style="color: red;">=</span> <span style="">begin</span><br /><span style="">></span> <span style="">o</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span style="">o</span><br /><span style="">></span> <span class="hs-sel">ǀ</span> <span class="hs-sel">ǀ</span><br /><span style="">></span> <span style="">o</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span style="">o</span><br /><span style="">></span> <span style="">end</span><br /></code></pre><pre><code>*StaticLiterals> :t r2<br />r2 :: Rectangle (S (S (S Z))) (S Z)</code></pre><pre><code><span style="">></span> <span style="">foo</span> <span style="color: red;">=</span> <span style="color: blue; font-weight: bold;">let</span> <span style="">r</span> <span style="color: red;">=</span> <span style="">begin</span><br /><span style="">></span> <span style="">o</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span style="">o</span><br /><span style="">></span> <span class="hs-sel">ǀ</span> <span class="hs-sel">ǀ</span><br /><span style="">></span> <span style="">o</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span style="">o</span><br /><span style="">></span> <span style="">end</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">in</span> <span style="">print</span> <span style="">r</span><br /></code></pre><pre><code>*StaticLiterals> foo<br />Rectangle 3 1</code></pre><p>What about errors? They're still impossible, types inferred have contexts that are impossible to fulfill, because there are no such instances. But we can do better! By using Oleg's trick with <em>Fail</em> class we can force ghc to return type errors of our choice.</p><p>There's this new paper <a href="http://pubs.doc.ic.ac.uk/error-handling-for-Haskell/">Errors for the Common Man</a> about debugging type errors, but I don't like it:</p><ul><li>they aren't aware of any solutions to this problem, though they mention HList paper (Fail class trick comes from that paper)</li><li>they talk about generalized state monad, again without mentioning <a href="http://okmij.org/ftp/Computation/monads.html#param-monad">Monadish</a></li><li>doing research in the area of Haskell type hacks and not being familiar with Oleg's work is a sin</li><li>using state monad to simulate exceptions is bad.</li><li>their idea imposes different type level coding style</li><li>nice error messages require using different api</li><li>no location provided for the errors</li></ul><p><em>Fail</em> class trick solves all of these problems. We provide additional instances to <em>Rectangly</em> class, with a fake <em>Fail</em> dependency with a specially crafted argument. Since <em>Fail</em> doesn't have any instances, it results in a type error, but this error mentions our argument and correct location.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">class</span> <span style="">Fail</span> <span style="">x</span><br /></code></pre><p>We need some types for pretty error messages:</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">Expected</span> <span style="">x</span> <span style="">y</span> <span style="">z</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">Either</span> <span style="">x</span> <span style="">or</span> <span style="">z</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">Or</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">ButGot</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">BottomLineToo</span> <span style="">x</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">Short</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">Long</span><br /></code></pre><p>These instances complement the previous set, trying to make Rectangly a total function, so there will be no errors like "no instance for Rectangly ....", because in these situations, it will match one of these faily instances and reduce to missing <em>Fail</em> instance with a nice error message.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Fail</span> <span style="color: red;">(</span><span style="">Expected</span> <span style="">Dash</span> <span style="">ButGot</span> <span style="">tag</span><span style="color: red;">)</span> <span style="color: red;">=></span><br /><span style="">></span> <span style="">Rectangly</span> <span style="">Corner</span> <span style="">tag</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">TopLeft</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">w'</span><span style="color: red;">,</span> <span style="">cw'</span><span style="color: red;">,</span> <span style="">h'</span><span style="color: red;">,</span> <span style="">s'</span><span style="color: red;">)</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Fail</span> <span style="color: red;">(</span><span style="">Expected</span> <span style="">Bar</span> <span style="">ButGot</span> <span style="">tag</span><span style="color: red;">)</span> <span style="color: red;">=></span><br /><span style="">></span> <span style="">Rectangly</span> <span style="">Corner</span> <span style="">tag</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">TopRight</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">w'</span><span style="color: red;">,</span> <span style="">cw'</span><span style="color: red;">,</span> <span style="">h'</span><span style="color: red;">,</span> <span style="">s'</span><span style="color: red;">)</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Fail</span> <span style="color: red;">(</span><span style="">Expected</span> <span style="">Dash</span> <span style="">ButGot</span> <span style="">tag</span><span style="color: red;">)</span> <span style="color: red;">=></span><br /><span style="">></span> <span style="">Rectangly</span> <span style="">Corner</span> <span style="">tag</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">BottomLeft</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">w'</span><span style="color: red;">,</span> <span style="">cw'</span><span style="color: red;">,</span> <span style="">h'</span><span style="color: red;">,</span> <span style="">s'</span><span style="color: red;">)</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Fail</span> <span style="color: red;">(</span><span style="">Expected</span> <span style="">End</span> <span style="">ButGot</span> <span style="">tag</span><span style="color: red;">)</span> <span style="color: red;">=></span><br /><span style="">></span> <span style="">Rectangly</span> <span style="">Corner</span> <span style="">tag</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">BottomRight</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">w'</span><span style="color: red;">,</span> <span style="">cw'</span><span style="color: red;">,</span> <span style="">h'</span><span style="color: red;">,</span> <span style="">s'</span><span style="color: red;">)</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Fail</span> <span style="color: red;">(</span><span style="">Expected</span> <span style="color: red;">(</span><span style="">Either</span> <span style="">Dash</span> <span style="">Or</span> <span style="">Corner</span><span style="color: red;">)</span> <span style="">ButGot</span> <span style="">tag</span><span style="color: red;">)</span> <span style="color: red;">=></span><br /><span style="">></span> <span style="">Rectangly</span> <span style="">Dash</span> <span style="">tag</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">Top</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">w'</span><span style="color: red;">,</span> <span style="">cw'</span><span style="color: red;">,</span> <span style="">h'</span><span style="color: red;">,</span> <span style="">s'</span><span style="color: red;">)</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Fail</span> <span style="color: red;">(</span><span style="">BottomLineToo</span> <span style="">Short</span><span style="color: red;">)</span> <span style="color: red;">=></span><br /><span style="">></span> <span style="">Rectangly</span> <span style="">Dash</span> <span style="">Corner</span><span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="color: red;">(</span><span style="">S</span> <span style="color: red;">(</span><span style="">S</span> <span style="">n</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">Bottom</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">w'</span><span style="color: red;">,</span> <span style="">cw'</span><span style="color: red;">,</span> <span style="">h'</span><span style="color: red;">,</span> <span style="">s'</span><span style="color: red;">)</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Fail</span> <span style="color: red;">(</span><span style="">BottomLineToo</span> <span style="">Long</span><span style="color: red;">)</span> <span style="color: red;">=></span><br /><span style="">></span> <span style="">Rectangly</span> <span style="">Dash</span> <span style="">Corner</span><span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">Z</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">Bottom</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">w'</span><span style="color: red;">,</span> <span style="">cw'</span><span style="color: red;">,</span> <span style="">h'</span><span style="color: red;">,</span> <span style="">s'</span><span style="color: red;">)</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Fail</span> <span style="color: red;">(</span><span style="">Expected</span> <span style="color: red;">(</span><span style="">Either</span> <span style="">Dash</span> <span style="">Or</span> <span style="">Corner</span><span style="color: red;">)</span> <span style="">ButGot</span> <span style="">tag</span><span style="color: red;">)</span> <span style="color: red;">=></span><br /><span style="">></span> <span style="">Rectangly</span> <span style="">Dash</span> <span style="">tag</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">Bottom</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">w'</span><span style="color: red;">,</span> <span style="">cw'</span><span style="color: red;">,</span> <span style="">h'</span><span style="color: red;">,</span> <span style="">s'</span><span style="color: red;">)</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Fail</span> <span style="color: red;">(</span><span style="">Expected</span> <span style="">Bar</span> <span style="">ButGot</span> <span style="">tag</span><span style="color: red;">)</span> <span style="color: red;">=></span><br /><span style="">></span> <span style="">Rectangly</span> <span style="">Bar</span> <span style="">tag</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">Left</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">w'</span><span style="color: red;">,</span> <span style="">cw'</span><span style="color: red;">,</span> <span style="">h'</span><span style="color: red;">,</span> <span style="">s'</span><span style="color: red;">)</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Fail</span> <span style="color: red;">(</span><span style="">Expected</span> <span style="color: red;">(</span><span style="">Either</span> <span style="">Bar</span> <span style="">Or</span> <span style="">Corner</span><span style="color: red;">)</span> <span style="">ButGot</span> <span style="">tag</span><span style="color: red;">)</span> <span style="color: red;">=></span><br /><span style="">></span> <span style="">Rectangly</span> <span style="">Bar</span> <span style="">tag</span> <span style="color: red;">(</span><span style="">w</span><span style="color: red;">,</span> <span style="">cw</span><span style="color: red;">,</span> <span style="">h</span><span style="color: red;">,</span> <span style="">Right</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">w'</span><span style="color: red;">,</span> <span style="">cw'</span><span style="color: red;">,</span> <span style="">h'</span><span style="color: red;">,</span> <span style="">s'</span><span style="color: red;">)</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">module</span> <span style="">StaticLiteralsErrors</span> <span style="color: blue; font-weight: bold;">where</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">import</span> <span style="">StaticLiterals</span><br /></code></pre><p>Let's compare quality of error messages between C++ and Haskell version:</p><pre class="sourceCode Cpp"><code><span class="Normal NormalText"> </span><span class="DataType DataType">unsigned</span><span class="Normal NormalText"> </span><span class="DataType DataType">int</span><span class="Normal NormalText"> r1 </span><span class="Normal Symbol">=</span><span class="Normal NormalText"> </span><span class="Normal Symbol">(</span><span class="Normal NormalText"> o</span><span class="Normal Symbol">-----</span><span class="Normal NormalText">o</span><br /><span class="Normal NormalText"> </span><span class="Normal Symbol">|</span><span class="Normal NormalText"> </span><span class="Normal Symbol">-</span><br /><span class="Normal NormalText"> o</span><span class="Normal Symbol">-----</span><span class="Normal NormalText">o </span><span class="Normal Symbol">).</span><span class="Normal NormalText">area</span><span class="Normal Symbol">;</span><br /></code></pre><pre><code>paczesiowa@laptop /tmp $ g++ tutorial.cpp -o tutorial && ./tutorial<br />tutorial.cpp: In function ‘int main()’:<br />tutorial.cpp:34: error: no match for ‘operator-’ in ‘-analog_literals::operator--((analog_literals::<br />line_end)0u, 0).analog_literals::dashes<T, n>::operator-- [with T = analog_literals::line_end, unsig<br />ned int n = 1u](0)’<br />analogliterals.hpp:72: note: candidates are: analog_literals::line<0u> analog_literals::operator-(an<br />alog_literals::line_end, analog_literals::line_end)</code></pre><pre><code><span style="">></span> <span style="">r1</span> <span style="color: red;">=</span> <span style="">area</span> <span style="">$</span> <span style="">begin</span><br /><span style="">></span> <span style="">o</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span style="">o</span><br /><span style="">></span> <span class="hs-sel">ǀ</span> <span class="hs-sel">ᜭ</span><br /><span style="">></span> <span style="">o</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span style="">o</span><br /><span style="">></span> <span style="">end</span><br /></code></pre><pre><code>No instance for (Fail (Expected Bar ButGot Dash))<br /> arising from a use of `ǀ'<br /> at /home/paczesiowa/blog/04-literals/StaticLiteralsErrors.lhs:23:16<br />Possible fix:<br /> add an instance declaration for (Fail (Expected Bar ButGot Dash))<br />In the fifth argument of `begin', namely `ǀ'<br />In the second argument of `($)', namely<br /> `begin o ᜭ ᜭ o ǀ ᜭ o ᜭ ᜭ o end'<br />In the expression: area $ begin o ᜭ ᜭ o ǀ ᜭ o ᜭ ᜭ o end</code></pre><p>Error message with the reason can be easily spotted, there is a location (with a column number!) provided, and even number of the wrong combinator ("fifth argument of begin"), shifted one to the left, though. That fix hint doesn't seem very helpful, but I'm sure that throwing an ascii-art of Clippy there would help a lot.</p><p>Another example:</p><pre class="sourceCode Cpp"><code><span class="Normal NormalText"> </span><span class="DataType DataType">unsigned</span><span class="Normal NormalText"> </span><span class="DataType DataType">int</span><span class="Normal NormalText"> r1 </span><span class="Normal Symbol">=</span><span class="Normal NormalText"> </span><span class="Normal Symbol">(</span><span class="Normal NormalText"> o</span><span class="Normal Symbol">-----</span><span class="Normal NormalText">o</span><br /><span class="Normal NormalText"> </span><span class="Normal Symbol">|</span><span class="Normal NormalText"> </span><span class="Normal Symbol">!</span><br /><span class="Normal NormalText"> o</span><span class="Normal Symbol">---</span><span class="Normal NormalText">o </span><span class="Normal Symbol">).</span><span class="Normal NormalText">area</span><span class="Normal Symbol">;</span><br /></code></pre><pre><code>tutorial.cpp: In function ‘int main()’:<br />tutorial.cpp:34: error: no match for ‘operator|’ in ‘analog_literals::operator-<br />[with unsigned int x<br />= 2u]((analog_literals::operator--((analog_literals::line_end)0u, 0).<br />analog_literals::dashes<T, n>:<br />:operator-- [with T = analog_literals::line_end, unsigned int n = 1u](0),<br />analog_literals::dashes<an<br />alog_literals::line_end, 2u>()), (analog_literals::line_end)0u) |<br />analog_literals::operator- [with u<br />nsigned int excl_marks = 1u, unsigned int x = 1u]((((analog_literals::<br />excls<analog_literals::dashes<<br />analog_literals::line_end, 1u>, 0u>*)(& analog_literals::operator--((<br />analog_literals::line_end)0u, 0<br />)))->analog_literals::excls<T, n>::operator! [with T =<br />analog_literals::dashes<analog_literals::line<br />_end, 1u>, unsigned int n = 0u](), analog_literals::excls<analog_literals::<br />dashes<analog_literals::l<br />ine_end, 1u>, 1u>()), (analog_literals::line_end)0u)’</code></pre><pre><code><span style="">></span> <span style="">r2</span> <span style="color: red;">=</span> <span style="">area</span> <span style="">$</span> <span style="">begin</span><br /><span style="">></span> <span style="">o</span> <span class="hs-sel">ᜭ</span> <span class="hs-sel">ᜭ</span> <span style="">o</span><br /><span style="">></span> <span class="hs-sel">ǀ</span> <span class="hs-sel">ǀ</span><br /><span style="">></span> <span style="">o</span> <span class="hs-sel">ᜭ</span> <span style="">o</span><br /><span style="">></span> <span style="">end</span><br /></code></pre><pre><code>No instance for (Fail (BottomLineToo Short))<br /> arising from a use of `ᜭ'<br /> at /home/paczesiowa/blog/04-literals/StaticLiteralsErrors.lhs:61:18<br />Possible fix:<br /> add an instance declaration for (Fail (BottomLineToo Short))<br />In the 8th argument of `begin', namely `ᜭ'</code></pre><p>That's it, the code is available <a href="http://patch-tag.com/r/Paczesiowa/blog/snapshot/current/content/pretty/04-literals">here</a>. Thanks for reading, comments are welcome.</p>Paczesiowahttp://www.blogger.com/profile/14436047943969802962noreply@blogger.com1tag:blogger.com,1999:blog-1819280277367524866.post-23806056879975691802010-03-17T15:15:00.000-07:002010-03-17T16:14:17.522-07:00Polyvariadic PrimeFib problem<p><font size="1" color="grey">begin Numbers.lhs</font></p><p><style> table.sourceCode, tr.sourceCode, td.lineNumbers, td.sourceCode, table.sourceCode pre { margin: 0; padding: 0; border: 0; vertical-align: baseline; border: none; } td.lineNumbers { border-right: 1px solid #AAAAAA; text-align: right; color: #AAAAAA; padding-right: 5px; padding-left: 5px; } td.sourceCode { padding-left: 5px; } pre.sourceCode { } pre.sourceCode span.Normal { } pre.sourceCode span.Keyword { color: #007020; font-weight: bold; } pre.sourceCode span.DataType { color: #902000; } pre.sourceCode span.DecVal { color: #40a070; } pre.sourceCode span.BaseN { color: #40a070; } pre.sourceCode span.Float { color: #40a070; } pre.sourceCode span.Char { color: #4070a0; } pre.sourceCode span.String { color: #4070a0; } pre.sourceCode span.Comment { color: #60a0b0; font-style: italic; } pre.sourceCode span.Others { color: #007020; } pre.sourceCode span.Alert { color: red; font-weight: bold; } pre.sourceCode span.Function { color: #06287e; } pre.sourceCode span.RegionMarker { } pre.sourceCode span.Error { color: red; font-weight: bold; } .SpellErrorWave { background: url('data:image/gif;base64,R0lGODlhBAADAIABAP8AAP///yH5BAEAAAEALAAAAAAEAAMAAAIFRB5mGQUAOw==') repeat-x left bottom; } </style></p><p>Some time ago, I claimed in a <a href="http://www.reddit.com/r/haskell/comments/apd0b/variadic_functions_in_haskell/c0iqp75">reddit comment</a>, that it's possible to write a function that accepts only prime number of arguments, that are all strings, but occurrences of integers at the indices that are Fibonacci numbers. Sounds cool and a little bit retarded, doesn't it? <em>kalven</em> <a href="http://www.reddit.com/r/haskell/comments/bdd1f/a_typelevel_programming_question_all_of_you/">asked about it</a>, so now I have to prove, that I wasn't bluffing.</p><p>But why would I even say such a thing? Well, it started with <a href="http://www.amateurtopologist.com/2010/01/12/variadic-functions-in-haskell/">this post</a> about polyvariadic functions in Haskell. The author claimed, that most modern languages have support for functions taking variable number of arguments. Let's take a look at <span class="SpellErrorWave"><a href="http://java.sun.com/j2se/1.5.0/docs/guide/language/varargs.html">Java</a></span>: this "support" consists of hidden <span class="SpellErrorWave">array</span> creation and passing that array as a single argument. Other languages work in a similar way, with the exception of <span class="SpellErrorWave">C</span>, where everything is allocated on the stack, and it works thanks to grit, spit and a whole lotta duct tape. This approach isn't as glamorous as it sounds, and there are disadvantages. All arguments have to be of the same type, even in <span class="SpellErrorWave">dynamically typed</span> languages - they only have one universal type. To use arguments that have different types, they have to be upcasted at the call site (e.g. to <span class="SpellErrorWave">Object</span> in <span class="SpellErrorWave">Java</span>) and later <span class="SpellErrorWave">downcasted</span> in such vararg function. It is <span class="SpellErrorWave">unsafe</span> and forces all arguments to have the same size or use autoboxing. In Haskell, thanks to better syntax and boiler-plat free list creation, it's easy to pass many arguments to a function, just pass a list. Compare:</p><p>Apologies for all those underlined words, it seems that my blog software doesn't like certain bad words.</p><pre class="sourceCode java"><code><span class="Keyword">class</span><span class="Normal NormalText"> Test </span><span class="Normal Symbol">{</span><br /><br /><span class="Normal NormalText"> </span><span class="Keyword">public</span><span class="Normal NormalText"> </span><span class="DataType DataType">static</span><span class="Normal NormalText"> </span><span class="DataType DataType">void</span><span class="Normal NormalText"> </span><span class="Function">main</span><span class="Normal Symbol">(</span><span class="Normal Java15">String</span><span class="Normal Symbol">[]</span><span class="Normal NormalText"> args</span><span class="Normal Symbol">)</span><span class="Normal NormalText"> </span><span class="Normal Symbol">{</span><br /><span class="Normal NormalText"> </span><span class="DataType DataType">int</span><span class="Normal NormalText"> x </span><span class="Normal Symbol">=</span><span class="Normal NormalText"> </span><span class="Function">foo</span><span class="Normal Symbol">(</span><span class="DecVal Decimal">1</span><span class="Normal Symbol">,</span><span class="Normal NormalText"> </span><span class="DecVal Decimal">2</span><span class="Normal Symbol">,</span><span class="Normal NormalText"> </span><span class="DecVal Decimal">3</span><span class="Normal Symbol">,</span><span class="Normal NormalText"> </span><span class="DecVal Decimal">4</span><span class="Normal Symbol">);</span><br /><span class="Normal NormalText"> </span><span class="Normal Java15">System</span><span class="Normal Symbol">.</span><span class="Function">out</span><span class="Normal Symbol">.</span><span class="Function">println</span><span class="Normal Symbol">(</span><span class="Normal NormalText">x</span><span class="Normal Symbol">);</span><br /><span class="Normal NormalText"> </span><span class="Normal Symbol">}</span><br /><br /><span class="Normal NormalText"> </span><span class="DataType DataType">static</span><span class="Normal NormalText"> </span><span class="DataType DataType">int</span><span class="Normal NormalText"> </span><span class="Function">foo</span><span class="Normal Symbol">(</span><span class="Normal Java15">Object</span><span class="Keyword">... </span><span class="Normal NormalText">args</span><span class="Normal Symbol">)</span><span class="Normal NormalText"> </span><span class="Normal Symbol">{</span><br /><span class="Normal NormalText"> </span><span class="Keyword">return</span><span class="Normal NormalText"> args</span><span class="Normal Symbol">.</span><span class="Function">length</span><span class="Normal Symbol">;</span><br /><span class="Normal NormalText"> </span><span class="Normal Symbol">}</span><br /><span class="Normal Symbol">}</span><br /></code></pre><p>With this:</p><pre><code><span style="">main</span> <span style="color: red;">=</span> <span style="color: blue; font-weight: bold;">do</span> <span style="color: red;">{</span><br /> <span style="">x</span> <span style="color: red;"><-</span> <span style="">foo</span><span style="color: red;">[</span><span class="hs-num">1</span><span style="color: red;">,</span> <span class="hs-num">2</span><span style="color: red;">,</span> <span class="hs-num">3</span><span style="color: red;">,</span> <span class="hs-num">4</span><span style="color: red;">]</span><span style="color: red;">;</span><br /> <span style="">print</span> <span style="">x</span><span style="color: red;">;</span><br /><span style="color: red;">}</span><br /><br /><span style="">foo</span> <span style="">args</span> <span style="color: red;">=</span> <span style="color: blue; font-weight: bold;">do</span> <span style="color: red;">{</span><br /> <span style="">return</span> <span style="color: red;">(</span><span style="">length</span> <span style="">args</span><span style="color: red;">)</span><span style="color: red;">;</span><br /><span style="color: red;">}</span></code></pre><p>The kind of parens is the only difference in syntax or semantics (of vararg function call). Of course, <em>being of the same type</em> means something different in <span class="SpellErrorWave">Java</span> (sub-typing), than in Haskell, but that's not the point of this post. The point is, that Haskell is the only <em>usable language<sup>*</sup></em>, that truly allows polyvariadic functions, because it's possible to write functions that take variable number of variably typed arguments, which is not possible to fake with a hidden list wrapping. As usual, now is the time to write <em>as usual, Oleg already <a href="http://okmij.org/ftp/Haskell/polyvariadic.html">did it</a></em>. Some polyvariadic functions are easy to implement (e.g. one that takes even number of arguments, with alternating integer and string arguments, do try to implement it), some could actually be useful.</p><p>* <em>usable language</em> is one, that makes it possible to download <em>pics</em> from the internet.</p><p>Others are just a useless, contrived example, but can prove that anything is possible in Haskell. The problem with the function of prime number of arguments, where Fibonacci indices are integers, while the rest are strings has been <a href="http://cdsmith.wordpress.com/2010/03/15/type-level-programming-example/">solved</a> by <em>cdsmith</em>. Nevertheless, I want to present another two solutions - one is easier to implement, but full of type hacks, and the other needed some thinking specific to this problem, but works much better - no boiler-plate required. Solutions are independent, so don't get discouraged by the first one, you can still be able to enjoy the second.</p><p>This post, like the previous one, needs ghc-6.12.2, 6.10 or 6.12.1 with <em>hacked</em> HList library. It's splitted across 4 files for modular reasons, the code is available at the <a href="http://patch-tag.com/r/Paczesiowa/blog">blog repo</a>.</p><p>Both solutions rely on prime and Fibonacci numbers, so we need type predicates for deciding if the number is prime/fib. I'm lazy and I didn't feel like translating regular algorithms to the type level, so I've assumed, that there are no prime/fib numbers bigger then 20, that way, it's possible to enumerate the positives, and choose all the other numbers as negatives.</p><p>Both predicates are similar, type-level function, that results in HTrue/HFalse, method has default bottom definition, because it will be only used at the type-level. Implementation uses <a href="http://www.haskell.org/haskellwiki/GHC/AdvancedOverlap">classic trick</a>, but as usual, I prefer equality constraints to TypeCasts wherever possible.</p><pre><code><span style="">></span> <span style="color: green;">{-# LANGUAGE MultiParamTypeClasses<br />> , FunctionalDependencies<br />> , FlexibleInstances<br />> , TypeFamilies<br />> , UndecidableInstances<br />> , TypeSynonymInstances<br />> , OverlappingInstances<br />> #-}</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">module</span> <span style="">Numbers</span> <span style="color: blue; font-weight: bold;">where</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">import</span> <span style="">Data</span><span style="">.</span><span style="">HList</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">type</span> <span style="">S</span> <span style="">n</span> <span style="color: red;">=</span> <span style="">HSucc</span> <span style="">n</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">type</span> <span style="">Z</span> <span style="color: red;">=</span> <span style="">HZero</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">class</span> <span style="">IsPrime</span> <span style="">n</span> <span style="">result</span> <span style="color: red;">|</span> <span style="">n</span> <span style="color: red;">-></span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">isPrime</span> <span style="color: red;">::</span> <span style="">n</span> <span style="color: red;">-></span> <span style="">result</span><br /><span style="">></span> <span style="">isPrime</span> <span style="color: red;">=</span> <span style="">undefined</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">IsPrime</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span> <span style="">Z</span><span style="color: red;">)</span><span style="color: red;">)</span> <span style="">HTrue</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">IsPrime</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span> <span style="">Z</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span> <span style="">HTrue</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">IsPrime</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span> <span style="">Z</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span> <span style="">HTrue</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">IsPrime</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span> <span style="">Z</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span> <span style="">HTrue</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">IsPrime</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span> <span style="">Z</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span> <span style="">HTrue</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">IsPrime</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span> <span style="">Z</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span> <span style="">HTrue</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">IsPrime</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span> <span style="">Z</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span> <span style="">HTrue</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">IsPrime</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span> <span style="">Z</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span> <span style="">HTrue</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">result</span> <span style="color: red;">~</span> <span style="">HFalse</span> <span style="color: red;">=></span> <span style="">IsPrime</span> <span style="">a</span> <span style="">result</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">class</span> <span style="">IsFib</span> <span style="">n</span> <span style="">result</span> <span style="color: red;">|</span> <span style="">n</span> <span style="color: red;">-></span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">isFib</span> <span style="color: red;">::</span> <span style="">n</span> <span style="color: red;">-></span> <span style="">result</span><br /><span style="">></span> <span style="">isFib</span> <span style="color: red;">=</span> <span style="">undefined</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">IsFib</span><span style="color: red;">(</span><span style="">Z</span><span style="color: red;">)</span> <span style="">HTrue</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">IsFib</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">Z</span><span style="color: red;">)</span><span style="color: red;">)</span> <span style="">HTrue</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">IsFib</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span> <span style="">Z</span><span style="color: red;">)</span><span style="color: red;">)</span> <span style="">HTrue</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">IsFib</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span> <span style="">Z</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span> <span style="">HTrue</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">IsFib</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span> <span style="">Z</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span> <span style="">HTrue</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">IsFib</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span> <span style="">Z</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span> <span style="">HTrue</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">IsFib</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span><span style="color: red;">(</span><span style="">S</span> <span style="">Z</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span> <span style="">HTrue</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">result</span> <span style="color: red;">~</span> <span style="">HFalse</span> <span style="color: red;">=></span> <span style="">IsFib</span> <span style="">n</span> <span style="">result</span><br /></code></pre><p><font size="1" color="grey">begin HListExtras.lhs</font></p><p>Before we get to the first solution, we need two list functions, that are missing from HList library. <em>hPartition</em> and <em>hAll</em> are type-level equivalents of <em>partition</em> and <em>all</em> functions from <em>Data.List</em> module. The implementation follows closely the style of the other, higher-order functions from HList, so there aren't any explanations, you can always read the excellent <a href="http://homepages.cwi.nl/~ralf/HList/">HList paper</a>. If you want more explanations, please ask in comments/email/irc, I could explain it some more if there's a need.</p><pre><code><span style="">></span> <span style="color: green;">{-# LANGUAGE MultiParamTypeClasses<br />> , FunctionalDependencies<br />> , FlexibleInstances<br />> , UndecidableInstances<br />> #-}</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">module</span> <span style="">HListExtras</span> <span style="color: blue; font-weight: bold;">where</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">import</span> <span style="">Data</span><span style="">.</span><span style="">HList</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">class</span> <span style="">HPartition</span> <span style="">p</span> <span style="">l</span> <span style="">r1</span> <span style="">r2</span> <span style="color: red;">|</span> <span style="">p</span> <span style="">l</span> <span style="color: red;">-></span> <span style="">r1</span> <span style="">r2</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">hPartition</span> <span style="color: red;">::</span> <span style="">p</span> <span style="color: red;">-></span> <span style="">l</span> <span style="color: red;">-></span> <span style="color: red;">(</span><span style="">r1</span><span style="color: red;">,</span><span style="">r2</span><span style="color: red;">)</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">class</span> <span style="">HPartition'</span> <span style="">flag</span> <span style="">p</span> <span style="">l</span> <span style="">r1</span> <span style="">r2</span> <span style="color: red;">|</span> <span style="">flag</span> <span style="">p</span> <span style="">l</span> <span style="color: red;">-></span> <span style="">r1</span> <span style="">r2</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">hPartition'</span> <span style="color: red;">::</span> <span style="">flag</span> <span style="color: red;">-></span> <span style="">p</span> <span style="color: red;">-></span> <span style="">l</span> <span style="color: red;">-></span> <span style="color: red;">(</span><span style="">r1</span><span style="color: red;">,</span><span style="">r2</span><span style="color: red;">)</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">HPartition</span> <span style="">p</span> <span style="">HNil</span> <span style="">HNil</span> <span style="">HNil</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">hPartition</span> <span style="color: blue; font-weight: bold;">_</span> <span style="color: blue; font-weight: bold;">_</span> <span style="color: red;">=</span> <span style="color: red;">(</span><span style="">HNil</span><span style="color: red;">,</span> <span style="">HNil</span><span style="color: red;">)</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="color: red;">(</span> <span style="">Apply</span> <span style="">p</span> <span style="">x</span> <span style="">flag</span><br /><span style="">></span> <span style="color: red;">,</span> <span style="">HPartition'</span> <span style="">flag</span> <span style="">p</span> <span style="color: red;">(</span><span style="">HCons</span> <span style="">x</span> <span style="">xs</span><span style="color: red;">)</span> <span style="">r1</span> <span style="">r2</span><br /><span style="">></span> <span style="color: red;">)</span> <span style="color: red;">=></span> <span style="">HPartition</span> <span style="">p</span> <span style="color: red;">(</span><span style="">HCons</span> <span style="">x</span> <span style="">xs</span><span style="color: red;">)</span> <span style="">r1</span> <span style="">r2</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">hPartition</span> <span style="">p</span> <span style="">l</span><span style="color: red;">@</span><span style="color: red;">(</span><span style="">HCons</span> <span style="">x</span> <span style="color: blue; font-weight: bold;">_</span><span style="color: red;">)</span> <span style="color: red;">=</span> <span style="">hPartition'</span> <span style="color: red;">(</span><span style="">apply</span> <span style="">p</span> <span style="">x</span><span style="color: red;">)</span> <span style="">p</span> <span style="">l</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">HPartition</span> <span style="">p</span> <span style="">xs</span> <span style="">r1</span> <span style="">r2</span> <span style="color: red;">=></span> <span style="">HPartition'</span> <span style="">HTrue</span> <span style="">p</span> <span style="color: red;">(</span><span style="">HCons</span> <span style="">x</span> <span style="">xs</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">HCons</span> <span style="">x</span> <span style="">r1</span><span style="color: red;">)</span> <span style="">r2</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">hPartition'</span> <span style="color: blue; font-weight: bold;">_</span> <span style="">p</span> <span style="color: red;">(</span><span style="">HCons</span> <span style="">x</span> <span style="">xs</span><span style="color: red;">)</span> <span style="color: red;">=</span> <span style="color: blue; font-weight: bold;">let</span> <span style="color: red;">(</span><span style="">r1</span><span style="color: red;">,</span> <span style="">r2</span><span style="color: red;">)</span> <span style="color: red;">=</span> <span style="">hPartition</span> <span style="">p</span> <span style="">xs</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">in</span> <span style="color: red;">(</span><span style="">HCons</span> <span style="">x</span> <span style="">r1</span><span style="color: red;">,</span> <span style="">r2</span><span style="color: red;">)</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">HPartition</span> <span style="">p</span> <span style="">xs</span> <span style="">r1</span> <span style="">r2</span> <span style="color: red;">=></span> <span style="">HPartition'</span> <span style="">HFalse</span> <span style="">p</span> <span style="color: red;">(</span><span style="">HCons</span> <span style="">x</span> <span style="">xs</span><span style="color: red;">)</span> <span style="">r1</span> <span style="color: red;">(</span><span style="">HCons</span> <span style="">x</span> <span style="">r2</span><span style="color: red;">)</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">hPartition'</span> <span style="color: blue; font-weight: bold;">_</span> <span style="">p</span> <span style="color: red;">(</span><span style="">HCons</span> <span style="">x</span> <span style="">xs</span><span style="color: red;">)</span> <span style="color: red;">=</span> <span style="color: blue; font-weight: bold;">let</span> <span style="color: red;">(</span><span style="">r1</span><span style="color: red;">,</span> <span style="">r2</span><span style="color: red;">)</span> <span style="color: red;">=</span> <span style="">hPartition</span> <span style="">p</span> <span style="">xs</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">in</span> <span style="color: red;">(</span><span style="">r1</span><span style="color: red;">,</span> <span style="">HCons</span> <span style="">x</span> <span style="">r2</span><span style="color: red;">)</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">class</span> <span style="">HAll</span> <span style="">p</span> <span style="">l</span> <span style="">r</span> <span style="color: red;">|</span> <span style="">p</span> <span style="">l</span> <span style="color: red;">-></span> <span style="">r</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">hAll</span> <span style="color: red;">::</span> <span style="">p</span> <span style="color: red;">-></span> <span style="">l</span> <span style="color: red;">-></span> <span style="">r</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">HAll</span> <span style="">p</span> <span style="">HNil</span> <span style="">HTrue</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">hAll</span> <span style="color: blue; font-weight: bold;">_</span> <span style="">HNil</span> <span style="color: red;">=</span> <span style="">hTrue</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="color: red;">(</span><span style="">Apply</span> <span style="">p</span> <span style="">x</span> <span style="">b1</span><span style="color: red;">,</span> <span style="">HAll</span> <span style="">p</span> <span style="">xs</span> <span style="">b2</span><span style="color: red;">,</span> <span style="">HAnd</span> <span style="">b1</span> <span style="">b2</span> <span style="">b</span><span style="color: red;">)</span> <span style="color: red;">=></span> <span style="">HAll</span> <span style="">p</span> <span style="color: red;">(</span><span style="">HCons</span> <span style="">x</span> <span style="">xs</span><span style="color: red;">)</span> <span style="">b</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">hAll</span> <span style="">p</span> <span style="color: red;">(</span><span style="">HCons</span> <span style="">x</span> <span style="">xs</span><span style="color: red;">)</span> <span style="color: red;">=</span> <span style="">apply</span> <span style="">p</span> <span style="">x</span> <span style="">`hAnd`</span> <span style="">hAll</span> <span style="">p</span> <span style="">xs</span><br /></code></pre><p><font size="1" color="grey">begin Solution1.lhs</font></p><p>Before we can write a function that meets the specification, we have to decide what this function should actually do:) It's funny, if a <em>type-blind</em> person would read the problem, the only conclusion would be, that it's possible to write a function in Haskell - truly amazing. The easiest thing to do (beside ignoring arguments and returning unit value), is to return a pair of lists, one will collect integers, and the other strings.</p><p>So what is the first solution about? It's based on a simple idea, we start with a function that accepts any number of integer and string arguments, in any configuration, and then we write a constrained wrapper.</p><pre><code><span style="">></span> <span style="color: green;">{-# LANGUAGE MultiParamTypeClasses<br />> , FunctionalDependencies<br />> , FlexibleInstances<br />> , UndecidableInstances<br />> , TypeFamilies<br />> , TypeSynonymInstances<br />> , NoMonomorphismRestriction<br />> , OverlappingInstances<br />> #-}</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">module</span> <span style="">Solution1</span> <span style="color: blue; font-weight: bold;">where</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">import</span> <span style="">Data</span><span style="">.</span><span style="">HList</span> <span style="">hiding</span> <span style="color: red;">(</span><span style="">TypeEq</span><span style="color: red;">,</span> <span style="">typeEq</span><span style="color: red;">)</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">import</span> <span style="">Data</span><span style="">.</span><span style="">HList</span><span style="">.</span><span style="">TypeEqGeneric2</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">import</span> <span style="">HListExtras</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">import</span> <span style="">Numbers</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">type</span> <span style="">X</span> <span style="color: red;">=</span> <span style="color: red;">(</span><span style="color: red;">[</span><span style="">Int</span><span style="color: red;">]</span><span style="color: red;">,</span> <span style="color: red;">[</span><span style="">String</span><span style="color: red;">]</span><span style="color: red;">)</span><br /></code></pre><p>Function foo is defined inductively, very similar to <em>c</em> function from <a href="http://okmij.org/ftp/Haskell/polyvariadic.html">introduction</a> of Oleg's polyvariadic page, nothing fancy here:</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">class</span> <span style="">Foo</span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">foo</span> <span style="color: red;">::</span> <span style="">X</span> <span style="color: red;">-></span> <span style="">result</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Foo</span> <span style="">X</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">foo</span> <span style="color: red;">(</span><span style="">ints</span><span style="color: red;">,</span><span style="">strings</span><span style="color: red;">)</span> <span style="color: red;">=</span> <span style="color: red;">(</span><span style="">reverse</span> <span style="">ints</span><span style="color: red;">,</span> <span style="">reverse</span> <span style="">strings</span><span style="color: red;">)</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Foo</span> <span style="">r</span> <span style="color: red;">=></span> <span style="">Foo</span> <span style="color: red;">(</span><span style="">Int</span> <span style="color: red;">-></span> <span style="">r</span><span style="color: red;">)</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">foo</span> <span style="color: red;">(</span><span style="">ints</span><span style="color: red;">,</span><span style="">strings</span><span style="color: red;">)</span> <span style="color: red;">=</span> <span style="color: red;">\</span><span style="">k</span> <span style="color: red;">-></span> <span style="">foo</span> <span style="color: red;">(</span><span style="">k</span><span style="">:</span><span style="">ints</span><span style="color: red;">,</span><span style="">strings</span><span style="color: red;">)</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Foo</span> <span style="">r</span> <span style="color: red;">=></span> <span style="">Foo</span> <span style="color: red;">(</span><span style="">String</span> <span style="color: red;">-></span> <span style="">r</span><span style="color: red;">)</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">foo</span> <span style="color: red;">(</span><span style="">ints</span><span style="color: red;">,</span><span style="">strings</span><span style="color: red;">)</span> <span style="color: red;">=</span> <span style="color: red;">\</span><span style="">s</span> <span style="color: red;">-></span> <span style="">foo</span> <span style="color: red;">(</span><span style="">ints</span><span style="color: red;">,</span><span style="">s</span><span style="">:</span><span style="">strings</span><span style="color: red;">)</span><br /></code></pre><pre><code><span style="">></span> <span style="">testFoo</span> <span style="color: red;">=</span> <span style="">foo</span> <span style="color: red;">(</span><span style="">[]</span><span style="color: red;">,</span><span style="">[]</span><span style="color: red;">)</span> <span style="color: red;">(</span><span class="hs-num">1</span><span style="color: red;">::</span><span style="">Int</span><span style="color: red;">)</span> <span style="color: teal;">"2"</span> <span style="color: teal;">"3"</span> <span style="color: red;">(</span><span class="hs-num">4</span><span style="color: red;">::</span><span style="">Int</span><span style="color: red;">)</span><br /></code></pre><p>We have to specify Int types of every argument, because otherwise it's just a type variable. Strings are already monomorphic. When we decide that foo has enough, we force it to be of final X type.</p><pre><code>*Solution1> :t testFoo<br />testFoo :: (Foo t) => t<br />*Solution1> testFoo :: X<br />([1,4],["2","3"])</code></pre><p>Now, if we could get a hold of the final type of particular usage of foo function, extract from that the list of argument types, it would be very easy to verify correct usage.</p><p>Turning type of function into a heterogeneous list of types (values are bottoms) of arguments is performed by the following, type-level function. It's very similar to ResultType from my previous post, but it returns every type but the last one, which is the type of the result. It relies on the same trick to overcome problems with functional dependencies and overlapping instances.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">class</span> <span style="">FunctionArguments</span> <span style="">f</span> <span style="">r</span> <span style="color: red;">|</span> <span style="">f</span> <span style="color: red;">-></span> <span style="">r</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">functionArguments</span> <span style="color: red;">::</span> <span style="">f</span> <span style="color: red;">-></span> <span style="">r</span><br /></code></pre><p>Base instance, if the type is not a function, return empty list, we don't care about result type:</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">result</span> <span style="color: red;">~</span> <span style="">HNil</span> <span style="color: red;">=></span> <span style="">FunctionArguments</span> <span style="">x</span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">functionArguments</span> <span style="color: blue; font-weight: bold;">_</span> <span style="color: red;">=</span> <span style="">HNil</span><br /></code></pre><p>Recursive case - if argument is of arrow type, put the argument into list head and recurse down the rest of the type. Value of this type is of course bottom, it's not possible to come up with anything meaningful, but it's not needed fortunately, we only care about the types. Similarly, the rest of the type is a result of applying dummy bottom value to our input function.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="color: red;">(</span> <span style="">FunctionArguments</span> <span style="">rest</span> <span style="">others</span><br /><span style="">></span> <span style="color: red;">,</span> <span style="">result</span> <span style="color: red;">~</span> <span style="color: red;">(</span><span style="">HCons</span> <span style="">x</span> <span style="">others</span><span style="color: red;">)</span><br /><span style="">></span> <span style="color: red;">)</span> <span style="color: red;">=></span> <span style="">FunctionArguments</span> <span style="color: red;">(</span><span style="">x</span> <span style="color: red;">-></span> <span style="">rest</span><span style="color: red;">)</span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">functionArguments</span> <span style="">f</span> <span style="color: red;">=</span> <span style="">HCons</span> <span style="">undefined</span> <span style="">$</span> <span style="">functionArguments</span> <span style="">$</span> <span style="">f</span> <span style="">undefined</span><br /></code></pre><p>In Haskell it's easy to get a hold of value of the result type, and use it inside its definition, thanks to the following trick:</p><pre><code><span style="">primeFib</span> <span style="color: red;">=</span> <span style="color: blue; font-weight: bold;">let</span> <span style="">r</span> <span style="color: red;">=</span> <span style="">foo</span> <span style="color: red;">(</span><span style="">[]</span><span style="color: red;">,</span><span style="">[]</span><span style="color: red;">)</span><br /> <span style="color: blue; font-weight: bold;">_</span> <span style="color: red;">=</span> <span style="">....</span><br /> <span style="color: blue; font-weight: bold;">in</span> <span style="">r</span></code></pre><p>In that dotted block, we can operate on the final value. The problem with let-expressions is, that they are polymorphic, and this together with other very polymorphic, type-level code can result in ambiguities, that can be resolved only with explicit type signatures and usage of ScopedTypeVariables. But, I don't want to write down that type, it's very complicated (over 10 lines!), because it records the whole algorithm. Fortunately, we can choose the case-expression, which has monomorphic bindings, and let ghc figure out the type:</p><pre><code><span style="">></span> <span style="">primeFib</span> <span style="color: red;">=</span> <span style="color: blue; font-weight: bold;">case</span> <span style="">foo</span> <span style="color: red;">(</span><span style="">[]</span><span style="color: red;">,</span><span style="">[]</span><span style="color: red;">)</span> <span style="color: blue; font-weight: bold;">of</span><br /><span style="">></span> <span style="">r</span> <span style="color: red;">-></span> <span style="color: blue; font-weight: bold;">let</span> <span style="color: blue; font-weight: bold;">_</span> <span style="color: red;">=</span> <span style="">checkList</span> <span style="">$</span> <span style="">functionArguments</span> <span style="">r</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">in</span> <span style="">r</span><br /></code></pre><p>It's easy to see, that this block doesn't <em>do</em> anything, but type-checker still takes it under consideration, so it's possible for it to constrain the resulting type. The only thing left, is to define checkList function, that will do all those calculations.</p><p>There's one more type-level (defined in terms of classes) piece of code needed: equivalent of <em>zip [1..]</em> value-level function, that will pair every element of the list with its index, which will allow to check its primality and <em>fibonality</em>.</p><p>NumberList takes a counter, that represents the first free index number, list, and returns list of numbered pairs:</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">class</span> <span style="">NumberList</span> <span style="">n</span> <span style="">l</span> <span style="">result</span> <span style="color: red;">|</span> <span style="">n</span> <span style="">l</span> <span style="color: red;">-></span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">numberList'</span> <span style="color: red;">::</span> <span style="">n</span> <span style="color: red;">-></span> <span style="">l</span> <span style="color: red;">-></span> <span style="">result</span><br /></code></pre><p>Base case is trivial, there's nothing to number, return empty list:</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">NumberList</span> <span style="">n</span> <span style="">HNil</span> <span style="">HNil</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">numberList'</span> <span style="color: blue; font-weight: bold;">_</span> <span style="color: blue; font-weight: bold;">_</span> <span style="color: red;">=</span> <span style="">HNil</span><br /></code></pre><p>Inductive case, tag the head value of the input list with the current counter, and recurse down the list with incremented counter:</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="color: red;">(</span><span style="">HNat</span> <span style="">n</span><span style="color: red;">,</span> <span style="">NumberList</span> <span style="color: red;">(</span><span style="">S</span> <span style="">n</span><span style="color: red;">)</span> <span style="">xs</span> <span style="">ys</span><span style="color: red;">)</span> <span style="color: red;">=></span> <span style="">NumberList</span> <span style="">n</span> <span style="color: red;">(</span><span style="">HCons</span> <span style="">x</span> <span style="">xs</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">HCons</span> <span style="color: red;">(</span><span style="">n</span><span style="color: red;">,</span><span style="">x</span><span style="color: red;">)</span> <span style="">ys</span><span style="color: red;">)</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">numberList'</span> <span style="">n</span> <span style="color: red;">(</span><span style="">HCons</span> <span style="">x</span> <span style="">xs</span><span style="color: red;">)</span> <span style="color: red;">=</span> <span style="">HCons</span> <span style="color: red;">(</span><span style="">n</span><span style="color: red;">,</span><span style="">x</span><span style="color: red;">)</span> <span style="">$</span> <span style="">numberList'</span> <span style="color: red;">(</span><span style="">hSucc</span> <span style="">n</span><span style="color: red;">)</span> <span style="">xs</span><br /></code></pre><p>Numbering starts with one:</p><pre><code><span style="">></span> <span style="">numberList</span> <span style="color: red;">=</span> <span style="">numberList'</span> <span style="color: red;">(</span><span style="">hSucc</span> <span style="">hZero</span><span style="color: red;">)</span><br /></code></pre><p>checkList function, like any code operating on a list in a functional language, will use higher-order functions, if you remember explanations from my previous post, this requires defunctionalization. There are 4 HOFs used, and their arguments have to be adjusted accordingly:</p><ol style="list-style-type: decimal;"><li><em>map snd</em></li></ol><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">Snd</span> <span style="color: red;">=</span> <span style="">Snd</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Apply</span> <span style="">Snd</span> <span style="color: red;">(</span><span style="">a</span><span style="color: red;">,</span> <span style="">b</span><span style="color: red;">)</span> <span style="">b</span><br /></code></pre><ol start="2" style="list-style-type: decimal;"><li><em>partition fibIndex</em> partitions list of pairs, according to predicate that checks <em>fibonality</em> of the index.</li></ol><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">FibIndex</span> <span style="color: red;">=</span> <span style="">FibIndex</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">IsFib</span> <span style="">n</span> <span style="">r</span> <span style="color: red;">=></span> <span style="">Apply</span> <span style="">FibIndex</span> <span style="color: red;">(</span><span style="">n</span><span style="color: red;">,</span><span style="">x</span><span style="color: red;">)</span> <span style="">r</span><br /></code></pre><ol start="3" style="list-style-type: decimal;"><li>(and 4.) there's <em>all isInt</em> and <em>all isString</em>, this could be implemented as two different functions, but it's possible to defunctionalize partial application of type-level equivalent of ==, TypeEq. This creates closures, that have to be reifed as data types in normal circumstances, but at the type level we use type parameter, and since we don't really care about value level in these predicates, we don't need any constructors, but I'm not a fan of <em>EmptyDataDecls</em>. This makes <em>Is</em> a phantom type.</li></ol><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">Is</span> <span style="">x</span> <span style="color: red;">=</span> <span style="">Is</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">TypeEq</span> <span style="">x</span> <span style="">y</span> <span style="">r</span> <span style="color: red;">=></span> <span style="">Apply</span> <span style="color: red;">(</span><span style="">Is</span> <span style="">x</span><span style="color: red;">)</span> <span style="">y</span> <span style="">r</span><br /></code></pre><p>I think, that checkList's definition doesn't need any explanations, we already have all the hard type-level parts defined, the rest is just functional programming:</p><pre><code><span style="">></span> <span style="">checkList</span> <span style="">l</span> <span style="color: red;">=</span> <span style="">intsOk</span> <span style="">`hAnd`</span> <span style="">stringsOk</span> <span style="">`hAnd`</span> <span style="">isPrime</span> <span style="">len</span> <span style="color: red;">::</span> <span style="">HTrue</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">where</span> <span style="color: red;">(</span><span style="">fibIndices</span><span style="color: red;">,</span> <span style="">nonFibIndices</span><span style="color: red;">)</span> <span style="color: red;">=</span> <span style="">hPartition</span> <span style="">FibIndex</span> <span style="">$</span> <span style="">numberList</span> <span style="">l</span><br /><span style="">></span> <span style="">removeIndices</span> <span style="color: red;">=</span> <span style="">hMap</span> <span style="">Snd</span><br /><span style="">></span> <span style="">isInt</span> <span style="color: red;">=</span> <span style="">Is</span> <span style="color: red;">::</span> <span style="">Is</span> <span style="">Int</span><br /><span style="">></span> <span style="">isString</span> <span style="color: red;">=</span> <span style="">Is</span> <span style="color: red;">::</span> <span style="">Is</span> <span style="">String</span><br /><span style="">></span> <span style="">intsOk</span> <span style="color: red;">=</span> <span style="">hAll</span> <span style="">isInt</span> <span style="">$</span> <span style="">removeIndices</span> <span style="">fibIndices</span><br /><span style="">></span> <span style="">stringsOk</span> <span style="color: red;">=</span> <span style="">hAll</span> <span style="">isString</span> <span style="">$</span> <span style="">removeIndices</span> <span style="">nonFibIndices</span><br /><span style="">></span> <span style="">len</span> <span style="color: red;">=</span> <span style="">hLength</span> <span style="">l</span><br /></code></pre><pre><code><span style="">></span> <span style="">testPrimeFib1</span> <span style="color: red;">=</span> <span style="">primeFib</span> <span style="color: red;">(</span><span class="hs-num">1</span><span style="color: red;">::</span><span style="">Int</span><span style="color: red;">)</span> <span style="color: red;">(</span><span class="hs-num">2</span><span style="color: red;">::</span><span style="">Int</span><span style="color: red;">)</span> <span style="color: red;">(</span><span class="hs-num">3</span><span style="color: red;">::</span><span style="">Int</span><span style="color: red;">)</span> <span style="color: teal;">"4"</span> <span style="color: red;">(</span><span class="hs-num">5</span><span style="color: red;">::</span><span style="">Int</span><span style="color: red;">)</span> <span style="color: green;">-- correct</span><br /><span style="">></span> <span style="">testPrimeFib2</span> <span style="color: red;">=</span> <span style="">primeFib</span> <span style="color: red;">(</span><span class="hs-num">1</span><span style="color: red;">::</span><span style="">Int</span><span style="color: red;">)</span> <span style="color: teal;">"2"</span> <span style="color: green;">-- string at fib index</span><br /><span style="">></span> <span style="">testPrimeFib3</span> <span style="color: red;">=</span> <span style="">primeFib</span> <span style="color: red;">(</span><span class="hs-num">1</span><span style="color: red;">::</span><span style="">Int</span><span style="color: red;">)</span> <span style="color: red;">(</span><span class="hs-num">2</span><span style="color: red;">::</span><span style="">Int</span><span style="color: red;">)</span> <span style="color: red;">(</span><span class="hs-num">3</span><span style="color: red;">::</span><span style="">Int</span><span style="color: red;">)</span> <span style="color: teal;">"4"</span> <span style="color: green;">-- not prime number of args</span><br /></code></pre><pre><code>*Solution1> testPrimeFib1 :: X<br />([1,2,3,5],["4"])<br />*Solution1> testPrimeFib2 :: X<br />Top level:<br /> Couldn't match expected type `HTrue' against inferred type `HFalse'<br /> When using functional dependencies to combine<br /> HAnd HFalse HTrue HFalse,<br /> (...)<br />*Solution1> testPrimeFib3 :: X<br />Top level:<br /> Couldn't match expected type `HTrue' against inferred type `HFalse'<br /><br />*Solution1> :t testPrimeFib1<br />testPrimeFib1<br /> :: (HMap Snd r2 ys2,<br /> HMap Snd r11 ys1,<br /> HAnd r r1 t'',<br /> IsPrime (HSucc (HSucc (HSucc (HSucc (HSucc n))))) result,<br /> HAnd t'' result HTrue,<br /> HAnd HTrue b23 r1,<br /> HAll (Is String) ys2 b23,<br /> HAnd HTrue b2 r,<br /> HAnd HTrue b21 b2,<br /> HAnd HTrue b22 b21,<br /> HAll (Is Int) ys1 b211,<br /> HAnd HTrue b211 b22,<br /> HPartition FibIndex ys r11 r2,<br /> NumberList<br /> (S (HSucc (HSucc (HSucc (HSucc (HSucc HZero)))))) others ys,<br /> HLength others n,<br /> FunctionArguments t others,<br /> Foo t) =><br /> t</code></pre><p>It works. Pros of this approach:</p><ul><li>easy implementation:<ul><li>many things available in HList</li><li>others (like FunctionArguments) are very general and are usable with other, non variadic problems</li><li>problem boils down to list manipulation</li></ul></li><li>it scales to other contrived examples - only checkList has to be modified</li></ul><p>Cons:</p><ul><li>a lot of boiler-plate at call-site</li><li>huge types of intermediate expressions</li><li>unreadable type errors</li></ul><p><font size="1" color="grey">begin Solution2.lhs</font></p><p>This time, we'll analyze this specific problem, and come up with much better and easier solution. What's the first problem with <em>primeFib</em> from my <em>Solution1</em>, and <em>test</em> from <em>cdsmith's</em> solution? Asking ghci about the type of both those functions results in <em>x</em> - simple type variable. Sure, there's also entire algorithm hidden in the type context, that could hide in the wardrobe and scare little children at night. But, we could tell more about that type, because we understand the problem. The function has to take only prime number of arguments, and the smallest prime number is 2. 1 and 2 are Fibonacci numbers, so clearly the type of bare primeFib function should be <em>Int -> Int -> r</em>, that much we can tell without choosing what to do later.</p><p>The second solution will be more aggressive, instead of checking the type at the end, when the only possible outcome is a type error, this approach will try to generate the correct type. It won't use any type-level tricks, in fact there will be three classes without functional dependencies - I almost forgot how to use those.</p><p>Here's how the algorithm will work. Let's assume that we are in the middle of computation and our functions has the following type:</p><pre><code>primeFib :: a<sub>1</sub> -> ... -> a<sub>n</sub> -> r</code></pre><p>and we want to generate the <em>r</em> part. The first thing to check, is to decide if <em>n</em> is a prime number. If so, we have two choices (let's call this situation <em>overlap</em>), we can either stop and return the accumulator (did I mention, that we are carrying an accumulator?), because we already have accepted prime number of arguments, or we can generate a bigger solution (this boils down to the other primality branch). If <em>n</em> isn't prime, it's clear that we must accept more arguments (this situation will be called <em>generate</em>), so <em>r</em> will be a function type <em>a<sub>n+1</sub> -> r'</em>. Now we have to decide the type of <em>a<sub>n+1</sub></em>: if <em>n+1</em> is a Fibonacci number, <em>a<sub>n+1</sub></em> will be <em>Int</em>, otherwise it is <em>String</em>. What about <em>r'</em> ? Well, we repeat the process with the successor of <em>n</em>.</p><pre><code><span style="">></span> <span style="color: green;">{-# LANGUAGE MultiParamTypeClasses<br />> , FunctionalDependencies<br />> , FlexibleInstances<br />> , FlexibleContexts<br />> , UndecidableInstances<br />> , TypeSynonymInstances<br />> , NoMonomorphismRestriction<br />> , OverlappingInstances<br />> #-}</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">import</span> <span style="">Data</span><span style="">.</span><span style="">HList</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">import</span> <span style="">Numbers</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">type</span> <span style="">X</span> <span style="color: red;">=</span> <span style="color: red;">(</span><span style="color: red;">[</span><span style="">Int</span><span style="color: red;">]</span><span style="color: red;">,</span> <span style="color: red;">[</span><span style="">String</span><span style="color: red;">]</span><span style="color: red;">)</span><br /></code></pre><p><em>Foo</em> will be the entry point to the algorithm. <em>n</em> is our counter - how many arguments have been already eaten. <em>foo</em> method has to carry our accumulator. Notice that there are no functional dependencies - we want it to have many instances (as many as there are prime numbers, which is a finite number, when there are no primes bigger than 20 :)</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">class</span> <span style="">Foo</span> <span style="">n</span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">foo</span> <span style="color: red;">::</span> <span style="">n</span> <span style="color: red;">-></span> <span style="">X</span> <span style="color: red;">-></span> <span style="">result</span><br /></code></pre><p><em>Foo</em> has only one instance, which means that it's a class synonym, and it's possible to write it as a function. I prefer a class here, because it will be used in two places, function approach would mean writing down twice this synonym, class approach can use type simplifier to do this rewriting.</p><p>This instance calls the next, auxiliary class, with an additional knowledge of the primality of <em>n</em>. It will be calculated as soon as <em>n</em> is known, because IsPrime is a type-level function.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="color: red;">(</span><span style="">IsPrime</span> <span style="">n</span> <span style="">flag</span><span style="color: red;">,</span> <span style="">Foo'</span> <span style="">flag</span> <span style="">n</span> <span style="">result</span><span style="color: red;">)</span> <span style="color: red;">=></span> <span style="">Foo</span> <span style="">n</span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">foo</span> <span style="">n</span> <span style="">acc</span> <span style="color: red;">=</span> <span style="">foo'</span> <span style="color: red;">(</span><span style="">isPrime</span> <span style="">n</span><span style="color: red;">)</span> <span style="">n</span> <span style="">acc</span><br /></code></pre><p><em>Foo'</em> class can now dispatch on the primality of the counter (flag argument):</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">class</span> <span style="">Foo'</span> <span style="">flag</span> <span style="">n</span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">foo'</span> <span style="color: red;">::</span> <span style="">flag</span> <span style="color: red;">-></span> <span style="">n</span> <span style="color: red;">-></span> <span style="">X</span> <span style="color: red;">-></span> <span style="">result</span><br /></code></pre><p>So, <em>n</em> isn't prime, we forward to the <em>Generate</em> class, but we also provide <em>Generate</em> class the result of <em>IsFib</em> on the successor of <em>n</em>, so it can dispatch on that fact.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="color: red;">(</span><span style="">HNat</span> <span style="">n</span><span style="color: red;">,</span> <span style="">IsFib</span> <span style="color: red;">(</span><span style="">HSucc</span> <span style="">n</span><span style="color: red;">)</span> <span style="">flag</span><span style="color: red;">,</span> <span style="">Generate</span> <span style="">flag</span> <span style="">n</span> <span style="">result</span><span style="color: red;">)</span> <span style="color: red;">=></span> <span style="">Foo'</span> <span style="">HFalse</span> <span style="">n</span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">foo'</span> <span style="color: blue; font-weight: bold;">_</span> <span style="">n</span> <span style="">acc</span> <span style="color: red;">=</span> <span style="">generate</span> <span style="color: red;">(</span><span style="">isFib</span> <span style="">$</span> <span style="">hSucc</span> <span style="">n</span><span style="color: red;">)</span> <span style="">n</span> <span style="">acc</span><br /></code></pre><p><em>Generate</em> class has a functional dependency, if we know that <em>n+1</em> is a Fibonacci number, we know which instance to choose - thus we know part or the resulting type.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">class</span> <span style="">Generate</span> <span style="">flag</span> <span style="">n</span> <span style="">result</span> <span style="color: red;">|</span> <span style="">flag</span> <span style="color: red;">-></span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">generate</span> <span style="color: red;">::</span> <span style="">flag</span> <span style="color: red;">-></span> <span style="">n</span> <span style="color: red;">-></span> <span style="">X</span> <span style="color: red;">-></span> <span style="">result</span><br /></code></pre><p><em>n+1</em> isn't a Fibonacci number, generate a function from <em>String</em> and continue the recursive process by calling <em>Foo</em> with a bigger counter. At the value level, return a function that will insert eaten argument to the accumulator.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="color: red;">(</span><span style="">HNat</span> <span style="">n</span><span style="color: red;">,</span> <span style="">Foo</span> <span style="color: red;">(</span><span style="">S</span> <span style="">n</span><span style="color: red;">)</span> <span style="">result</span><span style="color: red;">)</span> <span style="color: red;">=></span> <span style="">Generate</span> <span style="">HFalse</span> <span style="">n</span> <span style="color: red;">(</span><span style="">String</span> <span style="color: red;">-></span> <span style="">result</span><span style="color: red;">)</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">generate</span> <span style="color: blue; font-weight: bold;">_</span> <span style="">n</span> <span style="color: red;">(</span><span style="">ints</span><span style="color: red;">,</span><span style="">strings</span><span style="color: red;">)</span> <span style="color: red;">=</span> <span style="color: red;">\</span><span style="">s</span> <span style="color: red;">-></span> <span style="">foo</span> <span style="color: red;">(</span><span style="">hSucc</span> <span style="">n</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">ints</span><span style="color: red;">,</span> <span style="">s</span><span style="">:</span><span style="">strings</span><span style="color: red;">)</span><br /></code></pre><p>The other case, similar to the previous one, but for integers:</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="color: red;">(</span><span style="">HNat</span> <span style="">n</span><span style="color: red;">,</span> <span style="">Foo</span> <span style="color: red;">(</span><span style="">S</span> <span style="">n</span><span style="color: red;">)</span> <span style="">result</span><span style="color: red;">)</span> <span style="color: red;">=></span> <span style="">Generate</span> <span style="">HTrue</span> <span style="">n</span> <span style="color: red;">(</span><span style="">Int</span> <span style="color: red;">-></span> <span style="">result</span><span style="color: red;">)</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">generate</span> <span style="color: blue; font-weight: bold;">_</span> <span style="">n</span> <span style="color: red;">(</span><span style="">ints</span><span style="color: red;">,</span><span style="">strings</span><span style="color: red;">)</span> <span style="color: red;">=</span> <span style="color: red;">\</span><span style="">k</span> <span style="color: red;">-></span> <span style="">foo</span> <span style="color: red;">(</span><span style="">hSucc</span> <span style="">n</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">k</span><span style="">:</span><span style="">ints</span><span style="color: red;">,</span> <span style="">strings</span><span style="color: red;">)</span><br /></code></pre><p>Now the other branch of our first <em>if</em>, if counter was a prime number, go to the <em>Overlap</em> situation:</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Overlap</span> <span style="">n</span> <span style="">result</span> <span style="color: red;">=></span> <span style="">Foo'</span> <span style="">HTrue</span> <span style="">n</span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">foo'</span> <span style="color: blue; font-weight: bold;">_</span> <span style="">n</span> <span style="">acc</span> <span style="color: red;">=</span> <span style="">overlap</span> <span style="">n</span> <span style="">acc</span><br /></code></pre><p>This class has two overlapping instances - this is what stops the process, because it cannot decide which one to choose without further knowledge.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">class</span> <span style="">Overlap</span> <span style="">n</span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">overlap</span> <span style="color: red;">::</span> <span style="">n</span> <span style="color: red;">-></span> <span style="">X</span> <span style="color: red;">-></span> <span style="">result</span><br /></code></pre><p>Final case - our result type has been forced to <em>X</em>, return reversed accumulators:</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Overlap</span> <span style="">n</span> <span style="">X</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">overlap</span> <span style="color: blue; font-weight: bold;">_</span> <span style="color: red;">(</span><span style="">ints</span><span style="color: red;">,</span> <span style="">strings</span><span style="color: red;">)</span> <span style="color: red;">=</span> <span style="color: red;">(</span><span style="">reverse</span> <span style="">ints</span><span style="color: red;">,</span> <span style="">reverse</span> <span style="">strings</span><span style="color: red;">)</span><br /></code></pre><p>Otherwise, go to the <em>Overlap</em> case. There's no need to decide if <em>n+1</em> is a Fibonacci number, we can reuse <em>Foo' HFalse</em> instance, which does just that:</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="color: red;">(</span><span style="">Foo'</span> <span style="">HFalse</span> <span style="">n</span> <span style="">result</span><span style="color: red;">)</span> <span style="color: red;">=></span> <span style="">Overlap</span> <span style="">n</span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">overlap</span> <span style="">n</span> <span style="">acc</span> <span style="color: red;">=</span> <span style="">foo'</span> <span style="">hFalse</span> <span style="">n</span> <span style="">acc</span><br /></code></pre><p>Obviously, we start with empty accumulators and counter value of zero - we haven't accepted any arguments yet.</p><pre><code><span style="">></span> <span style="">primeFib</span> <span style="color: red;">=</span> <span style="">foo</span> <span style="">hZero</span> <span style="color: red;">(</span><span style="">[]</span><span style="color: red;">,</span><span style="">[]</span><span style="color: red;">)</span><br /></code></pre><p>This solution always generates the best approximation of the final type:</p><pre><code>*Main> :t primeFib<br />primeFib :: (Overlap (HSucc (HSucc HZero)) result) => Int -> Int -> result<br />*Main> :t \a b c d -> primeFib a b c d<br />\a b c d -> primeFib a b c d<br /> :: (Overlap (HSucc (HSucc (HSucc (HSucc (HSucc HZero))))) result) =><br /> Int -> Int -> Int -> String -> Int -> result</code></pre><p>This results in less boiler-plate required at the call-site:</p><pre><code><span style="">></span> <span style="">testPrimeFib1</span> <span style="color: red;">=</span> <span style="">primeFib</span> <span class="hs-num">1</span> <span class="hs-num">2</span> <span class="hs-num">3</span> <span style="color: teal;">"4"</span> <span class="hs-num">5</span><br /></code></pre><pre><code>*Main> :t testPrimeFib1<br />testPrimeFib1 :: (Overlap (HSucc (HSucc (HSucc (HSucc (HSucc HZero))))) result) => result<br />*Main> testPrimeFib1 :: X<br />([1,2,3,5],["4"])</code></pre><p>And better error messages:</p><pre><code>*Main> primeFib "1"<br /><interactive>:1:9:<br /> Couldn't match expected type `Int' against inferred type `[Char]'<br /> In the first argument of `primeFib', namely `"1"'<br /><br />*Main> primeFib 1 2 3 "4" :: X<br />Top level:<br /> Couldn't match expected type `([Int], [String])'<br /> against inferred type `Int -> result'</code></pre><p>The only disadvantage of this approach is the fact, that it required thinking specific to this problem, it could be much harder (impossible?) in different, contrived problems.</p><p>That is all, thanks for reading, comments are welcome.</p>Paczesiowahttp://www.blogger.com/profile/14436047943969802962noreply@blogger.com1tag:blogger.com,1999:blog-1819280277367524866.post-2179479850305849522010-03-05T09:49:00.000-08:002010-03-05T10:00:28.442-08:00Generalized zipWithN<p><FONT SIZE="1" COLOR="grey">BEGIN Part1.lhs</FONT></p><p>Some technical info about this post: it looks like literate Haskell file, but it isn't one. I'm not sure if it is possible to write this in a single Haskell file (I'll explain later why), it had to be split into two files. Since the extra part should be read in the middle, this post ended up being split into three Haskell modules, that can be type-checked and compiled, then concatenated into single file, that no longer type-checks, but it parses just fine, and that's enough to use <a href="http://hackage.haskell.org/package/BlogLiterately">BlogLiterately</a> on such files. It cannot be copy-pasted into a Haskell file, but it's useful anyway - there's syntax highlighting for free, and you should be familiar with literate Haskell structure - only lines prefixed with "> " are Haskell code, other code (even highlighted one) isn't taken into consideration by the Haskell compiler. Contents of this post (in regular Haskell files) are available at my <a href="http://patch-tag.com/r/Paczesiowa/blog">blog repository</a></p><p>The code depends on HList library. It works with ghc 6.10. It works with ghc 6.12.1, but HList 0.2 won't compile with 6.12.1 because of <a href="http://hackage.haskell.org/trac/ghc/ticket/3850">ghc bug</a>, so you can either hack HList to work around this bug, or wait for 6.12.2. It won't work with ghc 6.8, it uses equality constraints from TypeFamilies extension, introduced in 6.10.</p><p>This post is about generalized function zipWithN. Why?</p><ul><li><p>many people think it's impossible</p></li><li><p>there were a lot of attempts, but they all required boilerplate - extra type annotations, idiom brackets, some value or type-level counters in one way or another</p></li><li><p>I've seen only <a href="http://65.254.53.221:8000/8899">one version</a> of such function, that didn't require any boilerplate from the user, but that version couldn't deal with some polymorphic functions, without staying boilerplate-free (I know how to fix it now)</p></li><li><p>but, all of these versions, simple HM ones and those full of type-hackery, are based on the same idea, which is a step in the right direction, but somehow no one noticed what this idea is really about.</p></li></ul><p>I'll present a solution, that works for all polymorphic functions, without any boiler-plate, and has a very beautiful implementation, that's very easy to explain. What can be considered beautiful? Short code, that is built from more general pieces. What to do, when you have ugly, verbose code? Either you can spot a known structure and re-use its implementation, which makes code shorter, or you discover a new, previously unknown abstraction, then you can publish it, gain fame and fortune and perhaps even some up votes on reddit.</p><p>First some background. There's a 12 year old paper on this matter: <a href="http://www.brics.dk/RS/98/38/BRICS-RS-98-38.ps.gz">"An n-ary zipWith in Haskell"</a> by Daniel Frindler and Mia Indrika, you can read about it there, but don't try to understand the code - I [hope, that I] can explain it much better. So, there's a family of functions in functional languages, that allows to "zip" n lists of arguments with a a n-argument function, and get back a list of results. Just like in that paper, I'll refer to them as zipWithk, where k stands for the number of function arguments, or equivalently number of list arguments. In Haskell's Prelude we have zipWith3 - zipWith7, zipWith2 is called just zipWith, zipWith1 is called map, and zipWith0 is called repeat. Other Haskell libraries have smaller number of zipWith functions - vector has up to 6, stream-fusion has up to 7, but only 0-4 are fusible. OCaml only has zipWith1 and zipWith2 in the List module, they're called map and map2 respectively. It's not a good situation, user has to match zipping function arity to the name of zipWith function. There once was a similar problem with matching name of function to the type of its argument - people were tired of using printInt and printString. The solution was easy, just use (and invent first) type classes. In case of OCaml it was even easier - just switch to Haskell.</p><p>The paper presented the following solution (module header is obviously needed for other code, they didn't know back then how to abuse Haskell like that):</p><pre><code><span style="">></span> <span style="color: green;">{-# LANGUAGE MultiParamTypeClasses<br />> , FunctionalDependencies<br />> , FlexibleInstances<br />> , FlexibleContexts<br />> , UndecidableInstances<br />> , OverlappingInstances<br />> , TypeFamilies<br />> , NoMonomorphismRestriction<br />> #-}</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">module</span> <span style="">Part1</span> <span style="color: blue; font-weight: bold;">where</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">import</span> <span style="">Data</span><span style="">.</span><span style="">HList</span><br /></code></pre><pre><code><span style="">></span> <span style="">inzip</span> <span style="color: red;">::</span> <span style="color: red;">[</span><span style="">a</span><span style="color: red;">]</span> <span style="color: red;">-></span> <span style="color: red;">[</span><span style="">a</span> <span style="color: red;">-></span> <span style="">b</span><span style="color: red;">]</span> <span style="color: red;">-></span> <span style="color: red;">[</span><span style="">b</span><span style="color: red;">]</span><br /><span style="">></span> <span style="">inzip</span> <span style="color: red;">(</span><span style="">a</span><span style="">:</span><span style="color: blue; font-weight: bold;">as</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">f</span><span style="">:</span><span style="">fs</span><span style="color: red;">)</span> <span style="color: red;">=</span> <span style="">f</span> <span style="">a</span> <span style="">:</span> <span style="">inzip</span> <span style="color: blue; font-weight: bold;">as</span> <span style="">fs</span><br /><span style="">></span> <span style="">inzip</span> <span style="color: blue; font-weight: bold;">_</span> <span style="color: blue; font-weight: bold;">_</span> <span style="color: red;">=</span> <span style="">[]</span><br /></code></pre><pre><code><span style="">></span> <span style="color: red;">(</span><span style="">~~~</span><span style="color: red;">)</span> <span style="color: red;">::</span> <span style="color: red;">(</span><span style="">a</span> <span style="color: red;">-></span> <span style="">b</span><span style="color: red;">)</span> <span style="color: red;">-></span> <span style="color: red;">(</span><span style="">b</span> <span style="color: red;">-></span> <span style="">c</span><span style="color: red;">)</span> <span style="color: red;">-></span> <span style="">a</span> <span style="color: red;">-></span> <span style="">c</span><br /><span style="">></span> <span style="color: red;">(</span><span style="">~~~</span><span style="color: red;">)</span> <span style="color: red;">=</span> <span style="">flip</span> <span style="color: red;">(</span><span style="">.</span><span style="color: red;">)</span><br /></code></pre><pre><code><span style="">></span> <span style="color: red;">(</span><span style="">~~</span><span style="color: red;">)</span> <span style="color: red;">::</span> <span style="color: red;">[</span><span style="">b</span><span style="color: red;">]</span> <span style="color: red;">-></span> <span style="color: red;">(</span><span style="color: red;">[</span><span style="">b1</span><span style="color: red;">]</span> <span style="color: red;">-></span> <span style="">c</span><span style="color: red;">)</span> <span style="color: red;">-></span> <span style="color: red;">[</span><span style="">b</span> <span style="color: red;">-></span> <span style="">b1</span><span style="color: red;">]</span> <span style="color: red;">-></span> <span style="">c</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">as</span> <span style="">~~</span> <span style="">rest</span> <span style="color: red;">=</span> <span style="">inzip</span> <span style="color: blue; font-weight: bold;">as</span> <span style="">~~~</span> <span style="">rest</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">infixr</span> <span style="">~~</span><br /></code></pre><pre><code><span style="">></span> <span style="">zipWithFI</span> <span style="">f</span> <span style="">t</span> <span style="color: red;">=</span> <span style="">t</span> <span style="color: red;">(</span><span style="">repeat</span> <span style="">f</span><span style="color: red;">)</span><br /></code></pre><p>zipWith function from the paper got a different name (FI stands for names of the authors)</p><pre><code><span style="">></span> <span style="">test1</span> <span style="color: red;">=</span> <span style="">zipWithFI</span> <span style="">(,,)</span> <span style="color: red;">(</span><span style="color: red;">[</span><span class="hs-num">1</span><span style="color: red;">..</span><span style="color: red;">]</span> <span style="">~~</span> <span style="color: teal;">"hi"</span> <span style="">~~</span> <span style="color: teal;">"world"</span> <span style="">~~</span> <span style="">id</span><span style="color: red;">)</span><br /></code></pre><pre><code>*Part1> :t test1<br />test1 :: (Num a, Enum a) => [(a, Char, Char)]<br />*Part1> test1<br />[(1,'h','w'),(2,'i','o')]</code></pre><p>It was certainly usable, but there were two problems - a lot of boilerplate and it was extremely complicated - there were some continuations involved. I didn't understand it - sure, I could use it, but I wouldn't be able to explain it to someone else. Now I know why, and I'll tell you later, so forget about it for the moment.</p><p>There was also another solution mentioned, by Magnus Carlsson:</p><pre><code><span style="">></span> <span style="">zap</span> <span style="color: red;">=</span> <span style="">flip</span> <span style="">inzip</span><br /></code></pre><pre><code><span style="">></span> <span style="">test2</span> <span style="color: red;">=</span> <span style="">repeat</span> <span style="">(,,)</span> <span style="">`zap`</span> <span style="color: red;">[</span><span class="hs-num">1</span><span style="color: red;">..</span><span style="color: red;">]</span> <span style="">`zap`</span> <span style="color: teal;">"hi"</span> <span style="">`zap`</span> <span style="color: teal;">"world"</span><br /></code></pre><pre><code>*Part1> :t test2<br />test2 :: (Num a, Enum a) => [(a, Char, Char)]<br />*Part1> test2<br />[(1,'h','w'),(2,'i','o')]</code></pre><p>If you're wondering why I didn't just test if test1 == test2, it's because such expressions could help disambiguate some type variables in test2. That's not the case here, but it's a good habit when wri^H^H^Habusing Haskell code.</p><p>After noticing, that zap == Prelude.zipWith ($) (it's also <*> for ZipLists), this solution starts to look very good - it has pretty semantics: we start with infinite list of initial functions, and apply to them list of arguments, getting lists of partial applications, until we end up with the final result.</p><p>Have you ever read anything on sigfpe's blog? He always has pretty drawings of smart things (e.g. <a href="http://blog.sigfpe.com/2010/01/target-enumeration-with-euler.html">here</a>). Let's give it a shot, here's a picture that shows left to right evaluation of test2:</p><p><img src="http://img717.imageshack.us/img717/1671/zaprepeat.png" alt="evaluation of test" /></p><p>Oh well... yes, I am art-impaired. I did this with kolourpaint and this is the best I can do.</p><p>Now, that you've managed to stop laughing, let's get back to zipWiths. What's the problem with this solution? Turns out, it can be expressed as a very general recursion pattern, but instead, it does it manually. This is the idea behind Carlsson's version of zipWithN:</p><pre><code>zipWithN f a1 a2 ... an == repeat f `zap` a1 `zap` a2 `zap` ... `zap` an</code></pre><p>After adding parens around repeat f, and using prefix form of zap, which is left-associative, we get this:</p><pre><code>zipWithN f a1 a2 ... an == zap (... (zap (zap (repeat f) a1) a2) ...) an</code></pre><p>Any programmer, that accepted functional programming into his heart, should recognize that it's just a left fold over the list of arguments. Can it be rewritten like the following?</p><pre><code><span style="">zipWithN</span> <span style="">f</span> <span style="">a1</span> <span style="">a2</span> <span style="">...</span> <span style="">an</span> <span style="color: red;">=</span> <span style="">foldl</span> <span style="">zap</span> <span style="color: red;">(</span><span style="">repeat</span> <span style="">f</span><span style="color: red;">)</span> <span style="color: red;">[</span><span style="">a1</span><span style="color: red;">,</span> <span style="">a2</span><span style="color: red;">,</span> <span style="">...</span><span style="color: red;">,</span> <span style="">an</span><span style="color: red;">]</span></code></pre><p>Well, not really, after all, these lists don't need to be of the same type, and you cannot put them into one list. But the solution will look just like that fold.</p><p>Now, when we know that zipWithN is just a left fold, let's go back to the original solution of Frindler and Indrika. After inlining definition of zipWithFI, we get this scheme:</p><pre><code>zipWithN f a1 a2 ... an = (a1 ~~ a2 ~~ ... ~~ an ~~ id) (repeat f)</code></pre><p>Understanding (~~) should suffice, to get a hold of this idea. Let's unfold all sub-expressions into (~~) definition. inzip will be replaced with flip zap:</p><pre><code>as ~~ rest = inzip as ~~~ rest<br />   { prefix forms }<br />(~~) as rest = (~~~) (inzip as) rest<br />   { def (~~~) }<br />(~~) as rest = (flip (.)) (inzip as) rest<br />   { def flip }<br />(~~) as rest = (.) rest (inzip as)<br />   { eta expansion }<br />(~~) as rest a = (.) rest (inzip as) a<br />   { def (.) }<br />(~~) as rest a = rest (inzip as a)<br />   { inzip == flip zap }<br />(~~) as rest a = rest (flip zap as a)<br />   { def flip }<br />(~~) as rest a = rest (zap a as)</code></pre><p>We use some alpha conversions, to not get confused about arguments and their names:</p><pre><code>(~~) x y z = y (zap z x)</code></pre><p>We can treat zap in the prev equation as a free variable. You were probably expecting, that now I'll say "but this is just ...". No. My only thought about it was "it's weird" (actually it was something else, but let's pretend that I'm more civilized). Then I realised, that I've already seen similar "weird" code, and it was also followed by id function. Where? The paper "Cheap deforestation for non-strict functional languages" by Andy Gill. There's a theorem/equation that states, that any left fold can be rewritten as a right fold:</p><pre><code>foldl f z xs = foldr (\b g a -> g (f a b)) id xs z</code></pre><p>After transforming the "folded" idea of Magnus Carlsson with this equality, we get the following:</p><pre><code>zipWithN f a1 a2 ... an = foldl zap (repeat f) [a1, a2, ..., an] = foldr (~~) id [a1, a2, ..., an] (repeat f)</code></pre><p>The authors were claiming, that Carlsson's idea was sidestepping some dependent-type problems, but as it turns out, their preferred version was identical, only extremely obfuscated and hard to understand.</p><p>I've promised you a beautiful solution to the zipWithN problem. According to the previous definition of beautiful implementations, it has to be short and made from bigger pieces. It'll take two lines of code (unfortunately, because of Haskell type system, one of those has to be transformed, with a simple transformation that could be automatic, to 4 lines of code, so in the end there are 5 lines of code) and it will use 5 or 6 other, very general functions, that have nothing to do with zipWiths and can be used to implement other things.</p><p>We'll start with a simpler problem - uncurried version of zipWithN. uncurriedZipWithN will take a zipping function and a tuple of list arguments. There's no point in using normal Haskell tuples, 2-tuple (,) and 3-tuple (,,) have as much in common, as Ints and Strings - there's no recursive structure. Better option is to use nested 2-tuples, that lean to the right (e.g. (a,(b,(c,d)))). While it's possible to use nested tuples directly, it's easier to use nested tuples, that have an explicit terminator at the end, which makes it isomorphic to lists, that can contain values of different types. There's a whole library for use with these heterogeneous lists - HList, created by the one and only - Oleg Kiselyov.</p><p>As any list library, HList contains a fold function, unfortunately only right one, we have to write HFoldl ourselves. This definition follows the style of other list functions from HList, so you can read more about it in the HList paper (HFoldr is explained in one of the appendices).</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">class</span> <span style="">HFoldl</span> <span style="">f</span> <span style="">z</span> <span style="">l</span> <span style="">r</span> <span style="color: red;">|</span> <span style="">f</span> <span style="">z</span> <span style="">l</span> <span style="color: red;">-></span> <span style="">r</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">hFoldl</span> <span style="color: red;">::</span> <span style="">f</span> <span style="color: red;">-></span> <span style="">z</span> <span style="color: red;">-></span> <span style="">l</span> <span style="color: red;">-></span> <span style="">r</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">HFoldl</span> <span style="">f</span> <span style="">z</span> <span style="">HNil</span> <span style="">z</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">hFoldl</span> <span style="color: blue; font-weight: bold;">_</span> <span style="">z</span> <span style="color: blue; font-weight: bold;">_</span> <span style="color: red;">=</span> <span style="">z</span><br /></code></pre><p>There's one problem with hFoldl (compared to other functions like hTail) - it's a higher-order function and it's not possible (in general) to use such functions at the type level in Haskell. What do we do, when we want to write a higher-order function in first-order language (in this case - Haskell's type system)? We apply Reynolds defunctionalization. There is a open type function Apply, modelled as a class with a single method apply. hFoldl's argument takes 2 arguments, but it's easier to model it with a pair of arguments, that way single class Apply is sufficient for all functions. Here's the defunctionalized version of inductive case of HFoldl:</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="color: red;">(</span> <span style="">HFoldl</span> <span style="">f</span> <span style="">y</span> <span style="">xs</span> <span style="">r</span><br /><span style="">></span> <span style="color: red;">,</span> <span style="">Apply</span> <span style="">f</span> <span style="color: red;">(</span><span style="">z</span><span style="color: red;">,</span><span style="">x</span><span style="color: red;">)</span> <span style="">y</span><br /><span style="">></span> <span style="color: red;">)</span> <span style="color: red;">=></span> <span style="">HFoldl</span> <span style="">f</span> <span style="">z</span> <span style="color: red;">(</span><span style="">HCons</span> <span style="">x</span> <span style="">xs</span><span style="color: red;">)</span> <span style="">r</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">hFoldl</span> <span style="">f</span> <span style="">z</span> <span style="color: red;">(</span><span style="">HCons</span> <span style="">x</span> <span style="">xs</span><span style="color: red;">)</span> <span style="color: red;">=</span> <span style="">hFoldl</span> <span style="">f</span> <span style="color: red;">(</span><span style="">apply</span> <span style="">f</span> <span style="color: red;">(</span><span style="">z</span><span style="color: red;">,</span><span style="">x</span><span style="color: red;">)</span><span style="color: red;">)</span> <span style="">xs</span><br /></code></pre><p>Now we have to adjust our zap to this defunctionalized hFoldl. We need "avatar" for zap function. It doesn't need any values inside (those would probably be modelled as type variables), because there are no closures involved.</p><p>Naive solution would look like this:</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">ApplyZapNaive</span> <span style="color: red;">=</span> <span style="">ApplyZapNaive</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Apply</span> <span style="">ApplyZapNaive</span> <span style="color: red;">(</span><span style="color: red;">[</span><span style="">x</span><span style="color: red;">-></span><span style="">y</span><span style="color: red;">]</span><span style="color: red;">,</span> <span style="color: red;">[</span><span style="">x</span><span style="color: red;">]</span><span style="color: red;">)</span> <span style="color: red;">[</span><span style="">y</span><span style="color: red;">]</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">apply</span> <span style="">ApplyZapNaive</span> <span style="color: red;">=</span> <span style="">uncurry</span> <span style="">zap</span><br /></code></pre><p>This seems to be working:</p><pre><code><span style="">></span> <span style="">testNaiveApply1</span> <span style="color: red;">=</span> <span style="">apply</span> <span style="">ApplyZapNaive</span> <span style="color: red;">(</span><span style="color: red;">[</span><span style="">not</span><span style="color: red;">]</span><span style="color: red;">,</span> <span style="color: red;">[</span><span style="">True</span><span style="color: red;">,</span> <span style="">False</span><span style="color: red;">]</span><span style="color: red;">)</span><br /></code></pre><pre><code>*Part1> :t testNaiveApply1<br />testNaiveApply1 :: [Bool]<br />*Part1> testNaiveApply1<br />[False]</code></pre><p>But, there are problems:</p><pre><code><span style="">></span> <span style="">testNaiveApply2</span> <span style="color: red;">=</span> <span style="">apply</span> <span style="">ApplyZapNaive</span> <span style="color: red;">(</span><span style="color: red;">[</span><span style="">negate</span><span style="color: red;">]</span><span style="color: red;">,</span> <span style="color: red;">[</span><span class="hs-num">1</span><span style="color: red;">]</span><span style="color: red;">)</span><br /></code></pre><pre><code>*Part1> :t testNaiveApply2<br />testNaiveApply2 :: (Num a, Num t, Apply ApplyZapNaive ([a -> a], [t]) r) => r</code></pre><p><CODE>([negate], [1])</CODE> has polymorphic type, over two different type variables.<BR> Haskell type-checker tries to satisfy the <CODE>Apply ApplyZapNaive ([a -> a], [t]) r</CODE> constraint, but there is no instance that matches this pattern - the only instance that matches ApplyZapNaive, has the same types in both lists, which is too specific.</p><p>The usual solution is to use <a href="http://okmij.org/ftp/Haskell/typecast.html#local-fd">local functional dependencies</a>, that allow to use more general patterns in the instance head (which is the only thing taken under consideration when choosing instances), and after the instance is chosen, force the required equalities, which "improves" the types, or if they're different, there's a type error. I'll use equality constraints for this purpose, they are very similar to TypeCasts, but they look better (almost like "="), and they don't require any functions at the value level.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">data</span> <span style="">ApplyZap</span> <span style="color: red;">=</span> <span style="">ApplyZap</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="color: red;">(</span><span style="">a</span> <span style="color: red;">~</span> <span style="color: red;">[</span><span style="">x</span><span style="color: red;">-></span><span style="">y</span><span style="color: red;">]</span><span style="color: red;">,</span> <span style="">b</span> <span style="color: red;">~</span> <span style="color: red;">[</span><span style="">x</span><span style="color: red;">]</span><span style="color: red;">)</span> <span style="color: red;">=></span> <span style="">Apply</span> <span style="">ApplyZap</span> <span style="color: red;">(</span><span style="">a</span><span style="color: red;">,</span><span style="">b</span><span style="color: red;">)</span> <span style="color: red;">[</span><span style="">y</span><span style="color: red;">]</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">apply</span> <span style="color: blue; font-weight: bold;">_</span> <span style="color: red;">=</span> <span style="">uncurry</span> <span style="">zap</span><br /></code></pre><p>This works as expected:</p><pre><code>*Part1> :t apply ApplyZap ([negate], [1])<br />apply ApplyZap ([negate], [1]) :: (Num a) => [a]<br />*Part1> apply ApplyZap ([negate], [1])<br />[-1]</code></pre><p>Now, we're ready to define the first of the two lines, that form the solution to the main problem (notice that there's no need for any type signatures):</p><pre><code><span style="">></span> <span style="">uncurriedZipWithN</span> <span style="">f</span> <span style="color: red;">=</span> <span style="">hFoldl</span> <span style="">ApplyZap</span> <span style="color: red;">(</span><span style="">repeat</span> <span style="">f</span><span style="color: red;">)</span><br /></code></pre><pre><code><span style="">></span> <span style="">test3</span> <span style="color: red;">=</span> <span style="">uncurriedZipWithN</span> <span style="">(,,)</span> <span style="color: red;">(</span><span style="color: red;">[</span><span class="hs-num">1</span><span style="color: red;">..</span><span style="color: red;">]</span> <span style="">`HCons`</span> <span style="color: red;">(</span><span style="color: teal;">"hi"</span> <span style="">`HCons`</span> <span style="color: red;">(</span><span style="color: teal;">"world"</span> <span style="">`HCons`</span> <span style="">HNil</span><span style="color: red;">)</span><span style="color: red;">)</span><span style="color: red;">)</span><br /></code></pre><pre><code>*Part1> :t test3<br />test3 :: (Enum a, Num a) => [(a, Char, Char)]<br />*Part1> test3<br />[(1,'h','w'),(2,'i','o')]</code></pre><p>It works, but it looks similar (or even worse, thanks to the left-associative HCons) to the original, obfuscated version. But we're not done yet!</p><p>Now, let's develop some of those "bigger pieces" for creating pretty code. Let's start with a function that will count the number of arguments of another function. It's clear, that it has to be a class method. Don't mind the HNat constraints in contexts, I use Peano numbers from HList, and they use this constraint. It's not needed for anything, it's just a "comment", that helps writing code in a dynamically typed language - Haskell's type system.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">class</span> <span style="">HNat</span> <span style="">result</span> <span style="color: red;">=></span> <span style="">Arity</span> <span style="">x</span> <span style="">result</span> <span style="color: red;">|</span> <span style="">x</span> <span style="color: red;">-></span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">arity</span> <span style="color: red;">::</span> <span style="">x</span> <span style="color: red;">-></span> <span style="">result</span><br /></code></pre><p>Base case for non-functions:</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="color: red;">(</span><span style="">result</span> <span style="color: red;">~</span> <span style="">HZero</span><span style="color: red;">,</span> <span style="">HNat</span> <span style="">result</span><span style="color: red;">)</span> <span style="color: red;">=></span> <span style="">Arity</span> <span style="">x</span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">arity</span> <span style="color: blue; font-weight: bold;">_</span> <span style="color: red;">=</span> <span style="">hZero</span><br /></code></pre><p>Recursive case for function arguments. We create dummy, undefined value, force it to match the type of this functions arguments to get a dummy value of the resulting type, and use it (actually, only it's type) to call arity recursively, and finally increment it.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="color: red;">(</span><span style="">Arity</span> <span style="">y</span> <span style="">n</span><span style="color: red;">,</span> <span style="">result</span> <span style="color: red;">~</span> <span style="color: red;">(</span><span style="">HSucc</span> <span style="">n</span><span style="color: red;">)</span><span style="color: red;">,</span> <span style="">HNat</span> <span style="">result</span><span style="color: red;">)</span> <span style="color: red;">=></span> <span style="">Arity</span> <span style="color: red;">(</span><span style="">x</span> <span style="color: red;">-></span> <span style="">y</span><span style="color: red;">)</span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">arity</span> <span style="">f</span> <span style="color: red;">=</span> <span style="color: blue; font-weight: bold;">let</span> <span style="">x</span> <span style="color: red;">=</span> <span style="">undefined</span><br /><span style="">></span> <span style="">y</span> <span style="color: red;">=</span> <span style="">f</span> <span style="">x</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">in</span> <span style="">hSucc</span> <span style="">$</span> <span style="">arity</span> <span style="">y</span><br /></code></pre><p>If you're wondering why the type of the result is bound with equality constraint, instead of being used directly in the instance head, it's because it wouldn't compile. There would be an error, because functional dependencies don't play along with overlapping instances. The <a href="http://okmij.org/ftp/Haskell/typecast.html#is-function-type">solution</a> again relies on TypeCasts, and once again I choose equality constraints.</p><p>If you're familiar with Oleg's papers/code (e.g. the previous link), you know that Oleg doesn't like overlapping instances, and tries to limit their use to writing overlapping type predicates (like IsFunction), that are later combined with the two class trick, one of which is a wrapper class (and could be substituted with a function), and the other dispatches on the type of "flag" argument. I decided against this style, because overlapping instances extension is still needed. Moreover, the wrapper class, with a single instance, gets inlined by the type simplifier at every call place, which leads to longer (additional call to that type predicate) type signatures, that have an extra type variable (flag). When using 2 or 3 complicated functions, inferred types get filled with unneeded info pretty quickly.</p><pre><code><span style="">></span> <span style="">arityTest1</span> <span style="color: red;">=</span> <span style="">arity</span> <span style="">map</span><br /><span style="">></span> <span style="">arityTest2</span> <span style="color: red;">=</span> <span style="">arity</span> <span style="">(,,,,)</span><br /><span style="">></span> <span style="">arityTest3</span> <span style="color: red;">=</span> <span style="">arity</span> <span style="color: red;">(</span><span style="">+</span><span style="color: red;">)</span><br /></code></pre><pre><code>*Part1> :t arityTest1<br />arityTest1 :: HSucc (HSucc HZero)<br />*Part1> :t arityTest2<br />arityTest2 :: HSucc (HSucc (HSucc (HSucc (HSucc HZero))))<br />*Part1> :t arityTest3<br />arityTest3 :: (Arity a n, Num a) => HSucc (HSucc n)</code></pre><p>It works correctly in the first two cases, but fails to count the arity of (+). The difference between functions like map and (+) is the type of the result. The recursive case is correct, it did what it could when checking (+) arity, we know that it is greater or equal to two. But, at the end, when the type-checker has to decide the type of the result, which is just a type variable, it doesn't know which instance to choose, because they both match. So the type-checker decides to be lazy and wait until it knows something more about this type variable. There is no problem with map or tuple constructor, because the result type is known to not unify with the arrow type, so the more general, base case can be chosen safely.</p><p>The next type function is ResultType, it returns the type of the result. It uses the same pattern of recursion as Arity, and the same issues apply. This must only be used at the type-level, because its value has to be bottom. You wouldn't want to live in a world, where you could implement this as a total function (unless you're a lawyer).</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">class</span> <span style="">ResultType</span> <span style="">x</span> <span style="">result</span> <span style="color: red;">|</span> <span style="">x</span> <span style="color: red;">-></span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">resultType</span> <span style="color: red;">::</span> <span style="">x</span> <span style="color: red;">-></span> <span style="">result</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">result</span> <span style="color: red;">~</span> <span style="">x</span> <span style="color: red;">=></span> <span style="">ResultType</span> <span style="">x</span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">resultType</span> <span style="">x</span> <span style="color: red;">=</span> <span style="">x</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">ResultType</span> <span style="">y</span> <span style="">result</span> <span style="color: red;">=></span> <span style="">ResultType</span> <span style="color: red;">(</span><span style="">x</span> <span style="color: red;">-></span> <span style="">y</span><span style="color: red;">)</span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">resultType</span> <span style="">f</span> <span style="color: red;">=</span> <span style="color: blue; font-weight: bold;">let</span> <span style="">x</span> <span style="color: red;">=</span> <span style="">undefined</span><br /><span style="">></span> <span style="">y</span> <span style="color: red;">=</span> <span style="">f</span> <span style="">x</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">in</span> <span style="">resultType</span> <span style="">y</span><br /></code></pre><p><FONT SIZE="1" COLOR="grey">END Part1.lhs</FONT></p><p><FONT SIZE="1" COLOR="grey">BEGIN Part2.lhs</FONT></p><p>Previously on Lost, oh wait... anyway, those issues with Arity function have to be fixed. How? More abuse and more type system extensions. IncoherentInstances extension is an obscure extension of OverlappingInstances. Whenever there's a situation, that there are two instances, matching some unknown type variable, knocking on the door, instead of cowardly hiding in the kitchen, like OverlappingInstances, it flings the door open and says "IncoherentInstances here, what do you got?". Then, it eagerly chooses the more general one.</p><p>IncoherentArity is the exact copy of Arity, but it is defined in a module with IncoherentInstances extension enabled. In theory all the code could be defined in such a module, but that would break many things, and it would be very confusing.</p><p>Instead of equality constraints, it uses explicit TypeCasts, because the former don't work so good with IncoherentInstances extension. While it is possible, it requires many explicit type annotations, or else type simplifier simplifies things too early.</p><pre><code><span style="">></span> <span style="color: green;">{-# LANGUAGE MultiParamTypeClasses<br />> , FunctionalDependencies<br />> , FlexibleInstances<br />> , UndecidableInstances<br />> , IncoherentInstances<br />> , NoMonomorphismRestriction<br />> #-}</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">module</span> <span style="">Part2</span> <span style="color: blue; font-weight: bold;">where</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">import</span> <span style="">Data</span><span style="">.</span><span style="">HList</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">import</span> <span style="">Data</span><span style="">.</span><span style="">HList</span><span style="">.</span><span style="">TypeCastGeneric2</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">class</span> <span style="">HNat</span> <span style="">result</span> <span style="color: red;">=></span> <span style="">IncoherentArity</span> <span style="">x</span> <span style="">result</span> <span style="color: red;">|</span> <span style="">x</span> <span style="color: red;">-></span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">incoherentArity</span> <span style="color: red;">::</span> <span style="">x</span> <span style="color: red;">-></span> <span style="">result</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="color: red;">(</span><span style="">TypeCast</span> <span style="">HZero</span> <span style="">result</span><span style="color: red;">,</span> <span style="">HNat</span> <span style="">result</span><span style="color: red;">)</span> <span style="color: red;">=></span> <span style="">IncoherentArity</span> <span style="">x</span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">incoherentArity</span> <span style="color: blue; font-weight: bold;">_</span> <span style="color: red;">=</span> <span style="">typeCast</span> <span style="">hZero</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="color: red;">(</span> <span style="">IncoherentArity</span> <span style="">y</span> <span style="">n</span><br /><span style="">></span> <span style="color: red;">,</span> <span style="">TypeCast</span> <span style="color: red;">(</span><span style="">HSucc</span> <span style="">n</span><span style="color: red;">)</span> <span style="">result</span><br /><span style="">></span> <span style="color: red;">,</span> <span style="">HNat</span> <span style="">result</span><span style="color: red;">)</span> <span style="color: red;">=></span> <span style="">IncoherentArity</span> <span style="color: red;">(</span><span style="">x</span> <span style="color: red;">-></span> <span style="">y</span><span style="color: red;">)</span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">incoherentArity</span> <span style="">f</span> <span style="color: red;">=</span> <span style="color: blue; font-weight: bold;">let</span> <span style="">x</span> <span style="color: red;">=</span> <span style="">undefined</span><br /><span style="">></span> <span style="">y</span> <span style="color: red;">=</span> <span style="">f</span> <span style="">x</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">in</span> <span style="">typeCast</span> <span style="">$</span> <span style="">hSucc</span> <span style="">$</span> <span style="">incoherentArity</span> <span style="">y</span><br /></code></pre><p>How does it work?</p><pre><code><span style="">></span> <span style="">arityTest1</span> <span style="color: red;">=</span> <span style="">incoherentArity</span> <span style="">map</span><br /><span style="">></span> <span style="">arityTest2</span> <span style="color: red;">=</span> <span style="">incoherentArity</span> <span style="color: red;">(</span><span style="">+</span><span style="color: red;">)</span><br /><span style="">></span> <span style="">arityTest3</span> <span style="color: red;">=</span> <span style="">incoherentArity</span> <span style="">undefined</span><br /></code></pre><pre><code>*Part2> :t arityTest1<br />arityTest1 :: HSucc (HSucc HZero)<br />*Part2> :t arityTest2<br />arityTest2 :: HSucc (HSucc HZero)<br />*Part2> :t arityTest3<br />arityTest3 :: HZero</code></pre><p>There is a downside to this extension:</p><pre><code>*Part2> :t incoherentArity<br />incoherentArity :: x -> HZero</code></pre><p>Since <CODE>incoherentArity == (\x -> incoherentArity x)</CODE>, and there are two matching instances for this case, the more general, base case was chosen. It can be very confusing. It is possible to write an expression in a Haskell file that type-checks, but asking about its type in ghci results in a type error.</p><p>There's another problem with using it in a sane way. Trying to write a simple alias for it:</p><pre><code><span style="">></span> <span style="">incoherentArityAlias</span> <span style="color: red;">=</span> <span style="">incoherentArity</span><br /></code></pre><p>Results in a statically chosen instance (but the dreaded MonomorphismRestriction is disabled), that really doesn't care about its argument type:</p><pre><code>*Part2> :t incoherentArityAlias (+)<br />incoherentArityAlias (+) :: HZero</code></pre><p>To define correct alias (or any other function that should use it in a normal way), we have to add explicit type signature, which delays the whole process:</p><pre><code><span style="">></span> <span style="">incoherentArityAlias2</span> <span style="color: red;">::</span> <span style="">IncoherentArity</span> <span style="">x</span> <span style="">result</span> <span style="color: red;">=></span> <span style="">x</span> <span style="color: red;">-></span> <span style="">result</span><br /><span style="">></span> <span style="">incoherentArityAlias2</span> <span style="color: red;">=</span> <span style="">incoherentArity</span><br /></code></pre><pre><code>*Part2> :t incoherentArityAlias2 (+)<br />incoherentArityAlias2 (+) :: HSucc (HSucc HZero)</code></pre><p><FONT SIZE="1" COLOR="grey">END Part2.lhs</FONT></p><p><FONT SIZE="1" COLOR="grey">BEGIN Part3.lhs</FONT></p><pre><code><span style="">></span> <span style="color: green;">{-# LANGUAGE MultiParamTypeClasses<br />> , FunctionalDependencies<br />> , FlexibleInstances<br />> , UndecidableInstances<br />> , FlexibleContexts<br />> , NoMonomorphismRestriction<br />> #-}</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">module</span> <span style="">Part3</span> <span style="color: blue; font-weight: bold;">where</span><br /></code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">import</span> <span style="">Data</span><span style="">.</span><span style="">HList</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">import</span> <span style="">Part1</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">import</span> <span style="">Part2</span><br /></code></pre><p>OK, back to zipWithN problem. We have uncurriedZipWithN available, so it would seem that we're one curry away from the final solution. But is it even possible to write such a magic curry function? The answer is: Yes! Haskell can do that.</p><p>We want to write a function curryN, that takes an uncurried function from a tuple/heterogeneous list, and returns a curried version. So how does curry really work?</p><pre><code><span style="">curry</span> <span style="color: red;">::</span> <span style="color: red;">(</span><span style="color: red;">(</span><span style="">a</span><span style="color: red;">,</span> <span style="">b</span><span style="color: red;">)</span> <span style="color: red;">-></span> <span style="">c</span><span style="color: red;">)</span> <span style="color: red;">-></span> <span style="">a</span> <span style="color: red;">-></span> <span style="">b</span> <span style="color: red;">-></span> <span style="">c</span><br /><span style="">curry</span> <span style="">f</span> <span style="">x</span> <span style="">y</span> <span style="color: red;">=</span> <span style="">f</span> <span style="color: red;">(</span><span style="">x</span><span style="color: red;">,</span><span style="">y</span><span style="color: red;">)</span></code></pre><p>It may seem trivial, but most of that triviality comes from the fact, that it is fixed for functions working on a pair. Let's try to disassemble it - take a look at the following version:</p><pre><code><span style="">curry</span> <span style="color: red;">::</span> <span style="color: red;">(</span><span style="color: red;">(</span><span style="">a</span><span style="color: red;">,</span> <span style="">b</span><span style="color: red;">)</span> <span style="color: red;">-></span> <span style="">c</span><span style="color: red;">)</span> <span style="color: red;">-></span> <span style="">a</span> <span style="color: red;">-></span> <span style="">b</span> <span style="color: red;">-></span> <span style="">c</span><br /><span style="">curry</span> <span style="">f</span> <span style="color: red;">=</span> <span style="color: red;">\</span><span style="">x</span> <span style="">y</span> <span style="color: red;">-></span> <span style="color: blue; font-weight: bold;">let</span> <span style="">z</span> <span style="color: red;">=</span> <span style="color: red;">(</span><span style="">x</span><span style="color: red;">,</span><span style="">y</span><span style="color: red;">)</span><br /> <span style="color: blue; font-weight: bold;">in</span> <span style="">f</span> <span style="">z</span></code></pre><p>It makes things much more clear. curry does 3 things:</p><ol style="list-style-type: decimal;"><li>"eats" function arguments</li><li>constructs a tuple from them</li><li>calls the original function with this tuple as an argument</li></ol><p>This can be generalized. First step is to write a function eat, that will fulfil steps 1 and 2. Eat is a type function (with mirroring value level method), that takes a type numeral, and returns a function, that will "eat" that many arguments and construct heterogeneous list from them. As many similar functions from the value level, it will be defined in a more general way, with an accumulator that will carry list of already eaten arguments. Again, just like in Arity case, ignore HNat constraints, compiler can tell you where they are expected.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">class</span> <span style="">HNat</span> <span style="">n</span> <span style="color: red;">=></span> <span style="">Eat</span> <span style="">n</span> <span style="">acc</span> <span style="">result</span> <span style="color: red;">|</span> <span style="">n</span> <span style="">acc</span> <span style="color: red;">-></span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">eat'</span> <span style="color: red;">::</span> <span style="">n</span> <span style="color: red;">-></span> <span style="">acc</span> <span style="color: red;">-></span> <span style="">result</span><br /></code></pre><p>Base case - the list is full and couldn't eat another bite. Return reversed accumulator.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">HReverse</span> <span style="">acc</span> <span style="">result</span> <span style="color: red;">=></span> <span style="">Eat</span> <span style="">HZero</span> <span style="">acc</span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">eat'</span> <span style="color: blue; font-weight: bold;">_</span> <span style="">acc</span> <span style="color: red;">=</span> <span style="">hReverse</span> <span style="">acc</span><br /></code></pre><p>Recursive case: how to eat n+1 arguments? Return a function, that eats the first one, and then eats n more, remembering the one just eaten by adding it the accumulator.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">Eat</span> <span style="">n</span> <span style="color: red;">(</span><span style="">HCons</span> <span style="">x</span> <span style="">acc</span><span style="color: red;">)</span> <span style="">result</span> <span style="color: red;">=></span> <span style="">Eat</span> <span style="color: red;">(</span><span style="">HSucc</span> <span style="">n</span><span style="color: red;">)</span> <span style="">acc</span> <span style="color: red;">(</span><span style="">x</span> <span style="color: red;">-></span> <span style="">result</span><span style="color: red;">)</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">eat'</span> <span style="">n</span> <span style="">acc</span> <span style="color: red;">=</span> <span style="color: red;">\</span><span style="">x</span> <span style="color: red;">-></span> <span style="">eat'</span> <span style="color: red;">(</span><span style="">hPred</span> <span style="">n</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">HCons</span> <span style="">x</span> <span style="">acc</span><span style="color: red;">)</span><br /></code></pre><pre><code><span style="">></span> <span style="">eat</span> <span style="">n</span> <span style="color: red;">=</span> <span style="">eat'</span> <span style="">n</span> <span style="">HNil</span><br /></code></pre><pre><code><span style="">></span> <span style="">eatTest</span> <span style="color: red;">=</span> <span style="">eat</span> <span style="">four</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">where</span> <span style="">four</span> <span style="color: red;">=</span> <span style="">hSucc</span> <span style="">$</span> <span style="">hSucc</span> <span style="">$</span> <span style="">hSucc</span> <span style="">$</span> <span style="">hSucc</span> <span style="">hZero</span><br /></code></pre><pre><code>*Part3> :t eatTest<br />eatTest :: x -> x1 -> x2 -> x3 -> HCons x (HCons x1 (HCons x2 (HCons x3 HNil)))</code></pre><p>All that's remaining is step 3. curry from Prelude can easily call the original function on the tuple, because it has a value of that tuple, whereas generalized curryN only has a function that will in the end return such tuple. Situation may look pointless, but fear not! All we have to do, is to compose such tuple-producing function with the original, tuple-consuming function. It has to be so called "furthest" composition, and as usual, Oleg already <a href="http://okmij.org/ftp/Haskell/polyvar-comp.lhs">did it</a>. I didn't use it, because that code looks really old (pre-OverlappingInstances era), and it is only defined for some basic, monomorphic types. I also didn't understand all those 5 class variables. I ended up writing version with only 3 class arguments, while it worked correctly, it wasn't too helpful for the type-checker, and couldn't deal when composing very polymorphic functions. Otherwise there were these uncommon problems, that ghc doesn't like the type it inferred (I'll explain later why it was a problem). The final version uses 4 arguments, and thanks to additional functional dependency it helps a lot when disambiguating types. Interesting thing is, that all versions (mine 3 and 4 parameter, and Oleg's 5) had different types, but method definitions were always the same.</p><p>MComp class has mcomp' method, that takes two functions of the following types:</p><pre><code>f :: a1 -> ... -> cp<br />g :: cp -> d</code></pre><p>where cp is not a function, and returns composed function of type:</p><pre><code>f `mcomp` g :: a1 -> ... -> d</code></pre><p>Yes, it takes arguments in different order than (.), more like (>>>). It's not a bad thing, after all, we are used to reading (code) from left to right.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">class</span> <span style="">MComp</span> <span style="">f</span> <span style="">cp</span> <span style="">d</span> <span style="">result</span> <span style="color: red;">|</span> <span style="">f</span> <span style="">cp</span> <span style="">d</span> <span style="color: red;">-></span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">mcomp'</span> <span style="color: red;">::</span> <span style="">f</span> <span style="color: red;">-></span> <span style="color: red;">(</span><span style="">cp</span> <span style="color: red;">-></span> <span style="">d</span><span style="color: red;">)</span> <span style="color: red;">-></span> <span style="">result</span><br /></code></pre><p>Base case is even more base (sub-base?) than Oleg's - when first function isn't even a function, just apply it to the second function.</p><pre><code>f :: cp<br />g :: cp -> d<br />f `mcomp`g :: d</code></pre><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">MComp</span> <span style="">cp</span> <span style="">cp</span> <span style="">result</span> <span style="">result</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">mcomp'</span> <span style="">f</span> <span style="">g</span> <span style="color: red;">=</span> <span style="">g</span> <span style="">f</span><br /></code></pre><p>Recursive case. Value level method has the obvious implementation, instance signature is the only one, that would type-check with such method.</p><pre><code><span style="">></span> <span style="color: blue; font-weight: bold;">instance</span> <span style="">MComp</span> <span style="">rest</span> <span style="">cp</span> <span style="">d</span> <span style="">result</span> <span style="color: red;">=></span> <span style="">MComp</span> <span style="color: red;">(</span><span style="">a</span> <span style="color: red;">-></span> <span style="">rest</span><span style="color: red;">)</span> <span style="">cp</span> <span style="">d</span> <span style="color: red;">(</span><span style="">a</span> <span style="color: red;">-></span> <span style="">result</span><span style="color: red;">)</span> <span style="color: blue; font-weight: bold;">where</span><br /><span style="">></span> <span style="">mcomp'</span> <span style="">f</span> <span style="">g</span> <span style="color: red;">=</span> <span style="color: red;">\</span><span style="">a</span> <span style="color: red;">-></span> <span style="">mcomp'</span> <span style="color: red;">(</span><span style="">f</span> <span style="">a</span><span style="color: red;">)</span> <span style="">g</span><br /></code></pre><p>I mentioned additional functional dependency earlier, it couldn't be added to the class, because of that problem that overlapping instances don't play along with functional dependencies. So it was added to extra, wrapper class with a single instance. And classes with a single instance can be rewritten as regular functions. Constraint <CODE>ResultType f cp</CODE> helps to disambiguate (part of) the type of the second function.</p><pre><code><span style="">></span> <span style="">mcomp</span> <span style="color: red;">::</span> <span style="color: red;">(</span><span style="">ResultType</span> <span style="">f</span> <span style="">cp</span><span style="color: red;">,</span> <span style="">MComp</span> <span style="">f</span> <span style="">cp</span> <span style="">d</span> <span style="">result</span><span style="color: red;">)</span> <span style="color: red;">=></span> <span style="">f</span> <span style="color: red;">-></span> <span style="color: red;">(</span><span style="">cp</span> <span style="color: red;">-></span> <span style="">d</span><span style="color: red;">)</span> <span style="color: red;">-></span> <span style="">result</span><br /><span style="">></span> <span style="">mcomp</span> <span style="color: red;">=</span> <span style="">mcomp'</span><br /></code></pre><p>MComp has the same problems as the coherent version of Arity - it can't deal with functions (as the first argument) that have type variable as a result type. This works fine:</p><pre><code>*Part3> :t (,,,) `mcomp` show<br />(,,,) `mcomp` show :: (Show a, Show b, Show c, Show d) => a -> b -> c -> d -> [Char]</code></pre><p>because (,,,) has return type that doesn't unify with an arrow type (it's a tuple). (+) isn't so lucky:</p><pre><code>*Part3> :t (+) `mcomp` show<br />(+) `mcomp` show :: (Num a, Show cp, ResultType a cp, MComp a cp [Char] result) => a -> a -> result</code></pre><p>While it could be solved with IncoherentInstances, there's no need for this - we use if with eat function, that results in a tuple/heterogeneous list, so there's no ambiguity. Here's the definition of curryN' function, it still needs some type number:</p><pre><code><span style="">></span> <span style="">curryN'</span> <span style="">n</span> <span style="">f</span> <span style="color: red;">=</span> <span style="">eat</span> <span style="">n</span> <span style="">`mcomp`</span> <span style="">f</span><br /></code></pre><p>Here's the definition of curryN, that computes the number from the function itself, by generating dummy value of the function's argument type, and counting its length (it's a type level operation, so there are no problems with bottoms). That "case undefined of x ->" trick is needed to make x monomorphic, thanks to copumpkin from #haskell for this.</p><pre><code><span style="">></span> <span style="">curryN</span> <span style="">f</span> <span style="color: red;">=</span> <span style="color: blue; font-weight: bold;">case</span> <span style="">undefined</span> <span style="color: blue; font-weight: bold;">of</span><br /><span style="">></span> <span style="">x</span> <span style="color: red;">-></span> <span style="color: blue; font-weight: bold;">let</span> <span style="color: blue; font-weight: bold;">_</span> <span style="color: red;">=</span> <span style="">f</span> <span style="">x</span><br /><span style="">></span> <span style="color: blue; font-weight: bold;">in</span> <span style="">curryN'</span> <span style="color: red;">(</span><span style="">hLength</span> <span style="">x</span><span style="color: red;">)</span> <span style="">f</span><br /></code></pre><p>curryN cannot be used for the final zipWithN definition, because it's based on computing length of tuple function argument, which is not possible for hFoldl - it works with all lists. But we can reuse curryN' and compute needed number another way. Here's the final solution:</p><pre><code><span style="">></span> <span style="">zipWithN</span> <span style="">f</span> <span style="color: red;">=</span> <span style="">curryN'</span> <span style="color: red;">(</span><span style="">incoherentArity</span> <span style="">f</span><span style="color: red;">)</span> <span style="color: red;">(</span><span style="">uncurriedZipWithN</span> <span style="">f</span><span style="color: red;">)</span><br /></code></pre><p>If you remember the problems with incoherent functions, we have to delay choosing instance by providing the type signature:</p><pre><code><span style="">></span> <span style="">zipWithN</span> <span style="color: red;">::</span> <span style="color: red;">(</span> <span style="">MComp</span> <span style="">r1</span> <span style="">cp</span> <span style="">r2</span> <span style="">r3</span><br /><span style="">></span> <span style="color: red;">,</span> <span style="">ResultType</span> <span style="">r1</span> <span style="">cp</span><br /><span style="">></span> <span style="color: red;">,</span> <span style="">Eat</span> <span style="">r</span> <span style="">HNil</span> <span style="">r1</span><br /><span style="">></span> <span style="color: red;">,</span> <span style="">IncoherentArity</span> <span style="">a</span> <span style="">r</span><br /><span style="">></span> <span style="color: red;">,</span> <span style="">HFoldl</span> <span style="">ApplyZap</span> <span style="color: red;">[</span><span style="">a</span><span style="color: red;">]</span> <span style="">cp</span> <span style="">r2</span><span style="color: red;">)</span><br /><span style="">></span> <span style="color: red;">=></span> <span style="">a</span> <span style="color: red;">-></span> <span style="">r3</span><br /></code></pre><p>How did I come up with that? I didn't. I substituted incoherentArity for regular, coherent arity in zipWithN's definition, asked ghc to infer the type, copy-pasted it here, and replaced arity/Arity with incoherentArity/IncoherentArity.</p><p>The other "incoherent" problem remains unfortunately - asking ghci about zipWithN's type is confusing:</p><pre><code>*Part3> :t zipWithN<br />zipWithN :: a -> [a]</code></pre><p>But it stops being confusing when it's applied to the argument. Some tests demonstrating, that it can be used without any boiler-plate, even for functions polymorphic in their result type:</p><pre><code><span style="">></span> <span style="">ones</span> <span style="color: red;">=</span> <span style="">zipWithN</span> <span class="hs-num">1</span><br /><span style="">></span> <span style="">succList</span> <span style="color: red;">=</span> <span style="">zipWithN</span> <span style="color: red;">(</span><span style="">+</span><span class="hs-num">1</span><span style="color: red;">)</span><br /><span style="">></span> <span style="">hiWorld</span> <span style="color: red;">=</span> <span style="">zipWithN</span> <span style="">(,,)</span> <span style="color: red;">[</span><span class="hs-num">1</span><span style="color: red;">..</span><span style="color: red;">]</span> <span style="color: teal;">"hi"</span> <span style="color: teal;">"world"</span><br /><span style="">></span> <span style="">fibs</span> <span style="color: red;">=</span> <span class="hs-num">0</span> <span style="">:</span> <span class="hs-num">1</span> <span style="">:</span> <span style="">zipWithN</span> <span style="color: red;">(</span><span style="">+</span><span style="color: red;">)</span> <span style="">fibs</span> <span style="color: red;">(</span><span style="">tail</span> <span style="">fibs</span><span style="color: red;">)</span><br /></code></pre><pre><code>*Part3> :t ones<br />ones :: (Num t) => [t]<br />*Part3> ones !! 10<br />1<br />*Part3> :t succList<br />succList :: (Num a) => [a] -> [a]<br />*Part3> succList [1..5]<br />[2,3,4,5,6]<br />*Part3> :t hiWorld<br />hiWorld :: (Enum a, Num a) => [(a, Char, Char)]<br />*Part3> hiWorld<br />[(1,'h','w'),(2,'i','o')]<br />*Part3> :t fibs<br />fibs :: (Num y) => [y]<br />*Part3> fibs !! 10<br />55</code></pre><p>Well, that is all. What Frindler and Indrika thought to be impossible, implemented in two lines of code, that got defunctionalized to 5 lines. Everything based on a simple idea, boiler-plate free, and also there's some general purpose (if you like to abuse Haskell that is) utility functions.</p><p>Thanks for reading, comments are welcome.</p><p><FONT SIZE="1" COLOR="grey">END Part3.lhs</FONT></p>Paczesiowahttp://www.blogger.com/profile/14436047943969802962noreply@blogger.com3tag:blogger.com,1999:blog-1819280277367524866.post-33974316761600800982010-01-24T01:13:00.000-08:002010-01-24T06:14:22.474-08:00Pure, extensible exceptions and self-returning functions<pre><span style="color:Blue;">> <i>{-# LANGUAGE MultiParamTypeClasses<br />> , FunctionalDependencies <br />> , FlexibleInstances <br />> , FlexibleContexts <br />> , UndecidableInstances <br />> , OverlappingInstances <br />> , TypeFamilies <br />> , TypeSynonymInstances <br />> , ScopedTypeVariables <br />> , NoMonomorphismRestriction <br />> #-}</i></span> <br /></pre> <br /> <br />I'm sorry, it's rude to enable type system extensions, before introducing yourself, so: Hi, my name is Bartek and I'm an addict. I started doing Haskell 3 years ago, because everyone else in my programming class did so. I know, that peer pressure is the oldest excuse in the book, but that's the way it is. In the beginning, everything was great - it felt wonderful. Finally, I was able to write programs without the usual, imperative problems (such as off-by-one errors), thanks to regular functional programming features - recursion and pattern matching. Creating programs, that worked the first time they compiled, was exhilarating. And purity, the most noble thing any piece of code can achieve. Pure programs are never gonna make you cry, never gonna say goodbye, never gonna tell a lie and hurt you. <br /><br />But it wasn't all fun and games. The types. At first, they helped me to write programs, then it turned into an obsession. Compulsive need to turn every possible programming error into statically checked type error, consumed my soul. Soon, it was impossible for me to code anymore - inability to express the proper solution in types and constant strive for perfection rendered me unable to accept inferior solutions. <br />Would I stop myself, three years ago, from writing the first fold? Of course not, I choose to believe what I was programmed to believe. <br /><br />OK, enough of that, it probably wasn't funny anyway.<br /><br /><br />So... exceptions. They always fascinated me, since I understood the Either monad:<br /><br /><br /><pre><span style="color:Cyan;">></span> <span style="color:Green;"><u>instance</u></span> Monad <span style="color:Cyan;">(</span>Either e<span style="color:Cyan;">)</span> <span style="color:Green;"><u>where</u></span><br /><span style="color:Cyan;">></span> fail s <span style="color:Red;">=</span> error<span style="color:Cyan;">$</span><span style="color:Magenta;">"The 90's called, they want their 'fail' back. also: "</span> <span style="color:Cyan;">++</span> s<br /><span style="color:Cyan;">></span> return <span style="color:Red;">=</span> Right<br /><span style="color:Cyan;">></span> Left e <span style="color:Cyan;">>>=</span> <span style="color:Green;"><u>_</u></span> <span style="color:Red;">=</span> Left e<br /><span style="color:Cyan;">></span> Right x <span style="color:Cyan;">>>=</span> f <span style="color:Red;">=</span> f x<br /></pre> <br />No more magic explanations about <span style="font-style: italic;">walking the stack</span>, just a simple, direct implementation of exception semantic. <br /><br />But, there was a problem - there were many ways to report errors - <a href="http://www.randomhacks.net/articles/2007/03/10/haskell-8-ways-to-report-errors">haskell-8-ways-to-report-errors</a> but even using the most advanced one (I obviously don't consider anything IO-related), MonadError with ErrorT monad transformer was still too weak to use comfortably with different types of errors, because it wasn't extensible. <br /><br />I couldn't accept, that such an inferior language as Java had such a great exception system, whereas we, god's chosen people of Haskell, were destined to live in shame of using dynamically typed and imperative hacks to use extensible exception mechanism. The very thing, that we grew up in opposition to, became the foundation of our libraries. What is worse, it didn't stop people from lying with straight face to others, about virtues of purity and the power of type system of Haskell. <br /><br />It took me 2 years of studying teachings of Oleg Kiselyov (who was raised among types, where he learned to speak their language), but finally, I have the solution. It's so simple, that you're probably wondering why it took me 2 years. Well, I've wasted a lot of time, that's my specialty. <br /><br />I'm about to release a library - pure-exception (<a href="http://patch-tag.com/r/Paczesiowa/pure-exception">repository</a> is available. needs some more polishing of haddock docs and cabal stuff) that provides means to use computations with checked, extensible and hierarchical exceptions. If you're wondering why do we need another exception library (especially after <a href="http://hackage.haskell.org/package/control-monad-exception">control-monad-exception</a>), we don't. It has some practical advantages over control-monad-exception: <br /><br /><ul><li>absolutely no boilerplate needed</li><li>better API (similar to MonadError, which is already familiar to many haskellers)</li><li>better error messages (for minimal amount of boilerplate - 4 tokens per exception type)<br /></li></ul><br />But, I suspect control-monad-exception could evolve into something similar.<br /><br />The biggest difference, and the main reason behind pure-exception, is implementation - it's not based on Control.Exception from <a href="http://hackage.haskell.org/package/extensible-exceptions">extensible-exceptions</a> package. Some properties: <br /><br /><ul><li>the exception mechanism is pure - no unsafePerformIO inside</li><li>all functions are total - there are no missing cases and not a single 'undefined' token is used.</li><li>it's statically typed - no unsafeCoerce, cast or Typeable. <br /></li></ul><br />Pure, total and statically typed - the way god intended programs to be written.<br /><br />It relies on type-level programming, thus uses type system extensions. Which ones? Short answer - all of them. Better answer:<br /><br /><ul><li>MultiParamTypeClasses</li><li>FunctionalDependencies</li><li>OverlappingInstances</li><li>IncoherentInstances - needed to provide extra functionality, not required for core functionality</li><li>GADTs - not really required, they make implementation nicer (type-level code should also be pretty!)</li><li>UndecidableInstances</li><li>TypeFamilies - TypeFamilies are only used for equality constraints, there are no actual type families used. Equality constraints could be substituted with TypeCast from HList</li><li>'lazy instance selection' - not an extension, but type-checker property. This means, that the solution is ghc-only. <br /></li></ul><br />You're probably thinking, that it's not practical to use these extensions, that such code belongs on <a href="http://okmij.org/ftp/Haskell/types.html">Oleg's website</a> and we would be better off with <span style="font-style: italic;">Dynamic</span>s. Here's a fun fact: I've tried reimplementing exception mechanism described in the <a href="http://www.haskell.org/%7Esimonmar/bib/extexceptions06_abstract.html">paper behind extensible-exceptions library</a>, I've written some code that type-checked but didn't work and it took me a lot of time to find the bug. That's not the Haskell way. But maybe it's because I'm stupid, right? Well according to the footnote on page 4 of that paper, even Simon Marlow introduced a bug, that was spotted by someone else. It's hard to be smarter than Simon Marlow (*), so it's clearly the wrong way of programming.<br /><br /><span style="font-size:78%;">(*) - unless you are Simon Marlow</span><br /><br />On the other hand, when I was writing my code, with all those extensions (that supposedly lead to problems) and multiple redesigns, I didn't find a single bug in a code that type-checked. Not even some stupid mistake that's spotted 5 seconds after compilation. That's the way I want to code. <br /><br /><br />If you have objections to checked exceptions, then riddle me this: you like Haskell (otherwise why are you reading this?), you love when your programs work on the first try, because purity and rich types help creating correct programs, right? Don't you think, that there's a coincidence between that and the fact, that you cannot implement in Haskell unchecked exceptions, without using <span style="font-style: italic;">unsafePerformIO</span>? "But, checked exceptions force me to" - great! Every time some application crashes for me with <span style="font-style: italic;">NullPointerException</span>, I'd love to force something into some body part of some developer. My shoe of course. <br /><br /><br />OK, so let's see some code. Here's a simple, partial (escape function is partial) monad (not transformer) for computations with extensible exceptions.<br /><br />But first, a warm-up. Self-returning functions. What's a self-returning function? It's a function that (sometimes, no point if it always does) satisfies the equation: <br /><blockquote>foo x = foo</blockquote><br />Some of you probably think "it's not possible... Hindley-Milner...", well, have you considered switching to SML?<br /><br />Others know, that it's possible to sprinkle it with newtypes, Ins, outs and it would work.<br /><br />No! We'll ram it down ghc's throat and it better like it.<br /><br /><pre><span style="color:Cyan;">></span> <span style="color:Green;"><u>class</u></span> Foo x y <span style="color:Red;">|</span> x <span style="color:Red;">-></span> y <span style="color:Green;"><u>where</u></span><br /><span style="color:Cyan;">></span> foo <span style="color:Red;">::</span> x <span style="color:Red;">-></span> y <br /></pre> <br /><blockquote>instance Foo x y => Foo z (x->y) where<br /> <br />foo x = foo </blockquote><br /><br />Unfortunately, with only one instance and functional dependency, ghc will try to simplify the type of foo to:<br /><br /><span style="font-style: italic;"> z1 -> z2 -> z3 -> ....</span><br /><br />and it results in a loop.<br /><br />To stop it from simplifying, we have to add another instance, so the type stays polymorphic, with an explicit Foo context. It also makes sense, for foo to only sometimes return itself, otherwise it's useless. <br /><br /><pre><span style="color:Cyan;">></span> <span style="color:Green;"><u>instance</u></span> Foo String String <span style="color:Green;"><u>where</u></span><br /><span style="color:Cyan;">></span> foo <span style="color:Red;">=</span> id <br /></pre> <br />Now, the previous instance cannot be added, because functional dependencies don't play along with overlapping instances. There is the usual <a href="http://www.haskell.org/haskellwiki/GHC/AdvancedOverlap">solution of TypeCasts</a>.<br /><br />But it's also possible to use equality constraints:<br /><br /><pre><span style="color:Cyan;">></span> <span style="color:Green;"><u>instance</u></span> <span style="color:Cyan;">(</span>b <span style="color:Red;">~</span> <span style="color:Cyan;">(</span>x<span style="color:Red;">-></span>y<span style="color:Cyan;">)</span><span style="color:Cyan;">,</span> Foo x y<span style="color:Cyan;">)</span> <span style="color:Red;">=></span> Foo a b <span style="color:Green;"><u>where</u></span><br /><span style="color:Cyan;">></span> foo x <span style="color:Red;">=</span> foo <br /></pre> <br /><blockquote>*Main> :t foo <br />foo :: (Foo x y) => x -> y <br />*Main> :t foo () <br />foo () :: (Foo x y) => x -> y <br />*Main> :t foo () 'h' <br />foo () 'h' :: (Foo x y) => x -> y <br />*Main> foo () 'h' "Hello World!" <br />"Hello World!" </blockquote><br /><br />Let's evolve Foo. First modification is for foo to carry a String in its closure, and use it in the end:<br /><br /><pre><span style="color:Cyan;">></span> <span style="color:Green;"><u>class</u></span> Foo2 x y <span style="color:Red;">|</span> x <span style="color:Red;">-></span> y <span style="color:Green;"><u>where</u></span><br /><span style="color:Cyan;">></span> foo2 <span style="color:Red;">::</span> String <span style="color:Red;">-></span> x <span style="color:Red;">-></span> y<br /></pre> <br /><pre><span style="color:Cyan;">></span> <span style="color:Green;"><u>instance</u></span> Foo2 String String <span style="color:Green;"><u>where</u></span><br /><span style="color:Cyan;">></span> foo2 s <span style="color:Red;">=</span> <span style="color:Cyan;">(</span>s<span style="color:Cyan;">++</span><span style="color:Cyan;">)</span><br /></pre> <br /><pre><span style="color:Cyan;">></span> <span style="color:Green;"><u>instance</u></span> <span style="color:Cyan;">(</span>b <span style="color:Red;">~</span> <span style="color:Cyan;">(</span>x<span style="color:Red;">-></span>y<span style="color:Cyan;">)</span><span style="color:Cyan;">,</span> Foo2 x y<span style="color:Cyan;">)</span> <span style="color:Red;">=></span> Foo2 a b <span style="color:Green;"><u>where</u></span><br /><span style="color:Cyan;">></span> foo2 s <span style="color:Green;"><u>_</u></span> <span style="color:Red;">=</span> foo2 s<br /></pre> <br /><blockquote>*Main> :t foo2 "Hello" <br />foo2 "Hello" :: (Foo2 x y) => x -> y <br />*Main> :t foo2 "Hello" () <br />foo2 "Hello" () :: (Foo2 x y) => x -> y <br />*Main> foo2 "Hello" () " World!" <br />"Hello World!" </blockquote><br /><br />Second modification will invert the thing a little - the 'base' case will accept a function, and apply to it the String it carries: <br /><pre><span style="color:Cyan;">></span> <span style="color:Green;"><u>class</u></span> Foo3 x y <span style="color:Red;">|</span> x <span style="color:Red;">-></span> y <span style="color:Green;"><u>where</u></span><br /><span style="color:Cyan;">></span> foo3 <span style="color:Red;">::</span> String <span style="color:Red;">-></span> x <span style="color:Red;">-></span> y<br /></pre> <br /><pre><span style="color:Cyan;">></span> <span style="color:Green;"><u>instance</u></span> Foo3 <span style="color:Cyan;">(</span>String<span style="color:Red;">-></span>v<span style="color:Cyan;">)</span> v <span style="color:Green;"><u>where</u></span><br /><span style="color:Cyan;">></span> foo3 s f <span style="color:Red;">=</span> f s <br /></pre> <br /><pre><span style="color:Cyan;">></span> <span style="color:Green;"><u>instance</u></span> <span style="color:Cyan;">(</span>b <span style="color:Red;">~</span> <span style="color:Cyan;">(</span>x<span style="color:Red;">-></span>y<span style="color:Cyan;">)</span><span style="color:Cyan;">,</span> Foo3 x y<span style="color:Cyan;">)</span> <span style="color:Red;">=></span> Foo3 a b <span style="color:Green;"><u>where</u></span><br /><span style="color:Cyan;">></span> foo3 s <span style="color:Green;"><u>_</u></span> <span style="color:Red;">=</span> foo3 s<br /></pre> <blockquote><br />*Main> :t foo3 "!dlroW olleH" <br />foo3 "!dlroW olleH" :: (Foo3 x y) => x -> y <br />*Main> :t foo3 "!dlroW olleH" () <br />foo3 "!dlroW olleH" () :: (Foo3 x y) => x -> y <br />*Main> foo3 "!dlroW olleH" () (\(s::String) -> reverse s) <br />"Hello World!"</blockquote><br /><br />The type of the final function has to be ground/monomorphic.<br /><br />Next modification is to parametrize over Strings:<br /><br /><pre><span style="color:Cyan;">></span> <span style="color:Green;"><u>class</u></span> Foo4 e x y <span style="color:Red;">|</span> x <span style="color:Red;">-></span> y <span style="color:Green;"><u>where</u></span><br /><span style="color:Cyan;">></span> foo4 <span style="color:Red;">::</span> e <span style="color:Red;">-></span> x <span style="color:Red;">-></span> y<br /></pre> <br /><pre><span style="color:Cyan;">></span> <span style="color:Green;"><u>instance</u></span> Foo4 e <span style="color:Cyan;">(</span>e<span style="color:Red;">-></span>v<span style="color:Cyan;">)</span> v <span style="color:Green;"><u>where</u></span><br /><span style="color:Cyan;">></span> foo4 e f <span style="color:Red;">=</span> f e <br /></pre> <br /><pre><span style="color:Cyan;">></span> <span style="color:Green;"><u>instance</u></span> <span style="color:Cyan;">(</span>b <span style="color:Red;">~</span> <span style="color:Cyan;">(</span>x<span style="color:Red;">-></span>y<span style="color:Cyan;">)</span><span style="color:Cyan;">,</span> Foo4 e x y<span style="color:Cyan;">)</span> <span style="color:Red;">=></span> Foo4 e a b <span style="color:Green;"><u>where</u></span><br /><span style="color:Cyan;">></span> foo4 s <span style="color:Green;"><u>_</u></span> <span style="color:Red;">=</span> foo4 s<br /></pre> <br /><blockquote>*Main> foo4 "!dlroW olleH" () (\(s::String) -> reverse s) <br />"Hello World!" <br />*Main> foo4 'c' () Char.toUpper <br />'C' </blockquote><br /><br />But what does it have to with exceptions? Well, here's the final modification: the case that ignores its argument and returns itself, now will return itself wrapped in Left. The name of the class also changes: <br /><br /><pre><span style="color:Cyan;">></span> <span style="color:Green;"><u>class</u></span> Throws e x y <span style="color:Red;">|</span> x <span style="color:Red;">-></span> y <span style="color:Green;"><u>where</u></span><br /><span style="color:Cyan;">></span> throws <span style="color:Red;">::</span> e <span style="color:Red;">-></span> x <span style="color:Red;">-></span> y<br /></pre> <br /><pre><span style="color:Cyan;">></span> <span style="color:Green;"><u>instance</u></span> Throws e <span style="color:Cyan;">(</span>e<span style="color:Red;">-></span>v<span style="color:Cyan;">)</span> v <span style="color:Green;"><u>where</u></span><br /><span style="color:Cyan;">></span> throws e f <span style="color:Red;">=</span> f e<br /></pre> <br /><pre><span style="color:Cyan;">></span> <span style="color:Green;"><u>instance</u></span> <span style="color:Cyan;">(</span>b <span style="color:Red;">~</span> Either <span style="color:Cyan;">(</span>x<span style="color:Red;">-></span>y<span style="color:Cyan;">)</span> z<span style="color:Cyan;">,</span> Throws e x y<span style="color:Cyan;">)</span> <span style="color:Red;">=></span> Throws e a b <span style="color:Green;"><u>where</u></span><br /><span style="color:Cyan;">></span> throws s <span style="color:Green;"><u>_</u></span> <span style="color:Red;">=</span> Left <span style="color:Cyan;">$</span> throws s<br /></pre> <br />Whatever this is, it sure is extensible: <br /><br />*Main> :t throws ()<br />throws () :: (Throws () x y) => x -> y<br />*Main> :t throws "" <br />throws "" :: (Throws [Char] x y) => x -> y<br />*Main> :t if True then throws "" else throws ()<br />if True then throws "" else throws () <br />:: (Throws [Char] x y, Throws () x y) => x -> y<br /><br />What about the following functions?<br /><br /><pre><span style="color:Cyan;">></span> raise <span style="color:Red;">=</span> Left <span style="color:Cyan;">.</span> throws<br /></pre> <br /><pre><span style="color:Cyan;">></span> Left e <span style="color:Cyan;">`handle`</span> h <span style="color:Red;">=</span> e h<br /><span style="color:Cyan;">></span> Right x <span style="color:Cyan;">`handle`</span> <span style="color:Green;"><u>_</u></span> <span style="color:Red;">=</span> Right x<br /></pre> <br /><pre><span style="color:Cyan;">></span> runEither <span style="color:Cyan;">(</span>Right x<span style="color:Cyan;">)</span> <span style="color:Red;">=</span> x<br /></pre> <br /><blockquote>*Main> :t raise () <br />raise () :: (Throws () x y) => Either (x -> y) z <br />*Main> :t raise "" <br />raise "" :: (Throws [Char] x y) => Either (x -> y) z <br />*Main> :t if True then raise "" else raise () <br />if True then raise "" else raise () <br />:: (Throws [Char] x y, Throws () x y) => Either (x -> y) z </blockquote><br /><br />Now this becomes possible (types are inferred automatically):<br /><br /><pre><span style="color:Cyan;">></span> <span style="color:Green;"><u>data</u></span> Expr <span style="color:Red;">=</span> Const Int <span style="color:Red;">|</span> Div Expr Expr <span style="color:Green;"><u>deriving</u></span> <span style="color:Cyan;">(</span>Show<span style="color:Cyan;">,</span> Read<span style="color:Cyan;">)</span><br /><span style="color:Cyan;">></span> <span style="color:Green;"><u>data</u></span> ParseError <span style="color:Red;">=</span> ParseError<br /><span style="color:Cyan;">></span> <span style="color:Green;"><u>data</u></span> DivByZero <span style="color:Red;">=</span> DivByZero<br /></pre> <br /><pre><span style="color:Cyan;">></span> parse <span style="color:Red;">::</span> <span style="color:Cyan;">(</span>Read a<span style="color:Cyan;">,</span> Throws ParseError x y<span style="color:Cyan;">)</span> <span style="color:Red;">=></span> String <span style="color:Red;">-></span> Either <span style="color:Cyan;">(</span>x <span style="color:Red;">-></span> y<span style="color:Cyan;">)</span> a<br /><span style="color:Cyan;">></span> parse s <span style="color:Red;">=</span> <span style="color:Green;"><u>case</u></span> reads s <span style="color:Green;"><u>of</u></span><br /><span style="color:Cyan;">></span> <span style="color:Red;">[</span><span style="color:Cyan;">(</span>e<span style="color:Cyan;">,</span><span style="color:Magenta;">""</span><span style="color:Cyan;">)</span><span style="color:Red;">]</span> <span style="color:Red;">-></span> return e<br /><span style="color:Cyan;">></span> <span style="color:Green;"><u>_</u></span> <span style="color:Red;">-></span> raise ParseError<br /></pre> <br /><pre><span style="color:Cyan;">></span> evalExpr <span style="color:Red;">::</span> <span style="color:Cyan;">(</span>Throws DivByZero x y<span style="color:Cyan;">)</span> <span style="color:Red;">=></span> Expr <span style="color:Red;">-></span> Either <span style="color:Cyan;">(</span>x <span style="color:Red;">-></span> y<span style="color:Cyan;">)</span> Int<br /><span style="color:Cyan;">></span> evalExpr <span style="color:Cyan;">(</span>Const n<span style="color:Cyan;">)</span> <span style="color:Red;">=</span> return n<br /><span style="color:Cyan;">></span> evalExpr <span style="color:Cyan;">(</span>Div e1 e2<span style="color:Cyan;">)</span> <span style="color:Red;">=</span> <span style="color:Green;"><u>do</u></span><br /><span style="color:Cyan;">></span> v1 <span style="color:Red;"><-</span> evalExpr e1<br /><span style="color:Cyan;">></span> v2 <span style="color:Red;"><-</span> evalExpr e2<br /><span style="color:Cyan;">></span> <span style="color:Green;"><u>if</u></span> v2 <span style="color:Cyan;">==</span> <span style="color:Magenta;">0</span> <span style="color:Green;"><u>then</u></span><br /><span style="color:Cyan;">></span> raise DivByZero<br /><span style="color:Cyan;">></span> <span style="color:Green;"><u>else</u></span><br /><span style="color:Cyan;">></span> return <span style="color:Cyan;">$</span> v1 <span style="color:Cyan;">`div`</span> v2<br /></pre> <br /><pre><span style="color:Cyan;">></span> calc <span style="color:Red;">::</span> <span style="color:Cyan;">(</span>Throws ParseError x y<span style="color:Cyan;">,</span> Throws DivByZero x y<span style="color:Cyan;">)</span> <span style="color:Red;">=></span> String <span style="color:Red;">-></span> Either <span style="color:Cyan;">(</span>x <span style="color:Red;">-></span> y<span style="color:Cyan;">)</span> Int<br /><span style="color:Cyan;">></span> calc s <span style="color:Red;">=</span> parse s <span style="color:Cyan;">>>=</span> evalExpr<br /></pre> <br />It's not possible to run a computation, without handling all exceptions: <br /><br /><blockquote>*Main> runEither $ calc "Div (Const 2) (Const 0)"<br /><br /><interactive>:1:12:<br />Overlapping instances for Throws ParseError x y<br />... <br /><br /><interactive>:1:12:<br />Overlapping instances for Throws DivByZero x y<br /> <br />*Main> runEither $ calc "Div (Const 2) (Const 0)" `handle` (\ParseError -> return 0)<br /><br /><interactive>:1:12:<br />Overlapping instances for Throws DivByZero x y</interactive></interactive></interactive></blockquote><interactive><interactive><interactive><br /><br />And finally:<br /><br /><pre><span style="color:Cyan;">></span> main <span style="color:Red;">=</span> getLine <span style="color:Cyan;">>>=</span> print <span style="color:Cyan;">.</span> calc'<br /><span style="color:Cyan;">></span> <span style="color:Green;"><u>where</u></span> calc' s <span style="color:Red;">=</span> runEither <span style="color:Cyan;">$</span> calc s <span style="color:Cyan;">`handle`</span> <span style="color:Cyan;">(</span><span style="color:Red;">\</span>ParseError <span style="color:Red;">-></span> return <span style="color:Magenta;">0</span><span style="color:Cyan;">)</span> <span style="color:Cyan;">`handle`</span> <span style="color:Red;">\</span>DivByZero <span style="color:Red;">-></span> return <span style="color:Cyan;">(</span><span style="color:Blue;"><i>-</i></span><span style="color:Magenta;">1</span><span style="color:Cyan;">)</span><br /></pre><br /><br />If you like the idea, please take a look at pure-exception library, it has much better API than this, and it's more powerful. There are plenty of examples at <a href="http://patch-tag.com/r/Paczesiowa/pure-exception/snapshot/current/content/pretty/doc/examples">patch-tag</a><br /><br />Suggestions are very welcome. Both regarding library and my blog. I know my english is broken (but, what would you expect from someone, who learned the language by watching Family Guy and reading dirty stories on the internet).<br /></interactive></interactive></interactive>Paczesiowahttp://www.blogger.com/profile/14436047943969802962noreply@blogger.com5