<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta http-equiv="Content-Style-Type" content="text/css" />
<meta name="generator" content="pandoc" />
<title></title>
<style type="text/css">code{white-space: pre;}</style>
<style type="text/css">
table.sourceCode, tr.sourceCode, td.lineNumbers, td.sourceCode {
margin: 0; padding: 0; vertical-align: baseline; border: none; }
table.sourceCode { width: 100%; line-height: 100%; }
td.lineNumbers { text-align: right; padding-right: 4px; padding-left: 4px; color: #aaaaaa; border-right: 1px solid #aaaaaa; }
td.sourceCode { padding-left: 5px; }
code > span.kw { color: #007020; font-weight: bold; }
code > span.dt { color: #902000; }
code > span.dv { color: #40a070; }
code > span.bn { color: #40a070; }
code > span.fl { color: #40a070; }
code > span.ch { color: #4070a0; }
code > span.st { color: #4070a0; }
code > span.co { color: #60a0b0; font-style: italic; }
code > span.ot { color: #007020; }
code > span.al { color: #ff0000; font-weight: bold; }
code > span.fu { color: #06287e; }
code > span.er { color: #ff0000; font-weight: bold; }
</style>
</head>
<body>
<p>As part of recent type-refactoring efforts in Haskell, a discussion about adding <a href="https://mail.haskell.org/pipermail/libraries/2015-March/025381.html"><code>Semigroup</code> as a parent class of <code>Monoid</code></a> has been bouncing around the mailing list. From a theoretical point of view, this is a great idea: it is more flexible than the current approach that would allow for greater expressibility.</p>
<p>From a <em>practical</em> point of view, however, I am inclined to oppose it. Not because it is <em>in itself</em> a bad change—it's a very reasonable change that has advantages for new code—but because I have, in the past, had to update large systems written in Haskell after GHC updates, and therefore I know that <em>this kind of change has a cost</em>. The Applicative-Monad changes seem to have made way for the Foldable-Traversable Prelude, but those have in turn inspired a number of suggestions for modifications to the Haskell standard library, each one of which, taken on its own, is reasonable, but taken as a mass, mean <em>much more work</em> for maintainers. This is <em>especially</em> true if we continue on this path of making minor refactorings at each release: each year a project will need changes, or it will quickly bit-rot beyond utility.</p>
<h1 id="default-superclass-instances">Default Superclass Instances</h1>
<p>There is, however, an alternative I would like to discuss. Some of these changes—especially the <code>Semigroup</code>/<code>Monoid</code> split—seem to involve taking the functionality of a class and splitting it into multiple smaller classes. For example, we can think of the <code>Semigroup</code>/<code>Monoid</code> change as converting</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">class</span> <span class="dt">Monoid</span> m <span class="kw">where</span>
<span class="ot"> mempty ::</span> m
<span class="ot"> mappend ::</span> m <span class="ot">-></span> m <span class="ot">-></span> m</code></pre>
<p>into<sup><a href="#fn1" class="footnoteRef" id="fnref1">1</a></sup></p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">class</span> <span class="dt">Semigroup</span> m <span class="kw">where</span>
<span class="ot"> mappend ::</span> m <span class="ot">-></span> m <span class="ot">-></span> m
<span class="kw">class</span> <span class="dt">Semigroup</span> m <span class="ot">=></span> <span class="dt">Monoid</span> m <span class="kw">where</span>
<span class="ot"> mempty ::</span> m</code></pre>
<p><a href="https://ghc.haskell.org/trac/ghc/wiki/DefaultSuperclassInstances">Something that has been proposed before</a> (in a <a href="https://mail.haskell.org/pipermail/haskell-prime/2006-August/001587.html">few</a> <a href="https://wiki.haskell.org/Superclass_defaults">different</a> <a href="https://wiki.haskell.org/Class_system_extension_proposal">forms</a>) and which I suggest be more actively considered if changes like these are to become common is to allow <em>superclass instances to be declared within a subclass declaration</em>. This would allow you to write a single <code>instance</code> declaration for a class, and in that body <em>also include implementations for methods belong to a superclass of that class</em> by some means<sup><a href="#fn2" class="footnoteRef" id="fnref2">2</a></sup>:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">newtype</span> <span class="dt">MyId</span> a <span class="fu">=</span> <span class="dt">MyId</span> a
<span class="kw">instance</span> <span class="dt">Monad</span> <span class="dt">MyId</span> <span class="kw">where</span>
<span class="co">-- Functor method</span>
fmap f (<span class="dt">MyId</span> x) <span class="fu">=</span> <span class="dt">MyId</span> (f x)
<span class="co">-- Applicative methods</span>
pure <span class="fu">=</span> <span class="dt">MyId</span>
<span class="dt">MyId</span> f <span class="fu"><*></span> <span class="dt">MyId</span> x <span class="fu">=</span> <span class="dt">MyId</span> (f x)
<span class="co">-- Monad methods</span>
return <span class="fu">=</span> <span class="dt">MyId</span>
<span class="dt">MyId</span> x <span class="fu">>>=</span> f <span class="fu">=</span> f x</code></pre>
<p>For the <code>Monoid</code>/<code>Semigroup</code> proposal, this would mean that any <code>Monoid</code> instances that exist would continue to work unchanged, but new instances could (optionally) split apart their declarations. Under this proposal, either of these would be acceptable:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">class</span> <span class="dt">Semigroup</span> m <span class="kw">where</span><span class="ot"> mappend ::</span> m <span class="ot">-></span> m <span class="ot">-></span> m
<span class="kw">class</span> <span class="dt">Semigroup</span> m <span class="ot">=></span> <span class="dt">Monoid</span> m <span class="kw">where</span><span class="ot"> mempty ::</span> m
<span class="co">-- combined `instance` declarations:</span>
<span class="kw">instance</span> <span class="dt">Monoid</span> [a] <span class="kw">where</span>
mempty <span class="fu">=</span> []
mappend <span class="fu">=</span> (<span class="fu">++</span>)</code></pre>
<p>or, equivalently,</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">class</span> <span class="dt">Semigroup</span> m <span class="kw">where</span><span class="ot"> mappend ::</span> m <span class="ot">-></span> m <span class="ot">-></span> m
<span class="kw">class</span> <span class="dt">Semigroup</span> m <span class="ot">=></span> <span class="dt">Monoid</span> m <span class="kw">where</span><span class="ot"> mempty ::</span> m
<span class="co">-- split apart `instance` declarations</span>
<span class="kw">instance</span> <span class="dt">Semigroup</span> [a] <span class="kw">where</span>
mappend <span class="fu">=</span> (<span class="fu">++</span>)
<span class="kw">instance</span> <span class="dt">Monoid</span> [a] <span class="kw">where</span>
mempty <span class="fu">=</span> []</code></pre>
<p>And because the <code>Monoid</code> declaration for <code>[]</code> <a href="http://hackage.haskell.org/package/base-4.8.0.0/docs/src/GHC-Base.html#line-227">is already written like the former</a>, we can make the <code>Semigroup</code>/<code>Monoid</code> split without having to rewrite the instance declarations!</p>
<p>Because this lowers the cost of updating for new versions, various <em>other</em> useful changes might be considered that would otherwise involve far too much breakage. For example, we could consider splitting <code>Num</code> apart into small constituent parts<sup><a href="#fn3" class="footnoteRef" id="fnref3">3</a></sup>:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">class</span> <span class="dt">Add</span> a <span class="kw">where</span><span class="ot"> (+) ::</span> a <span class="ot">-></span> a <span class="ot">-></span> a
<span class="kw">class</span> <span class="dt">Sub</span> a <span class="kw">where</span><span class="ot"> (-) ::</span> a <span class="ot">-></span> a <span class="ot">-></span> a
<span class="kw">class</span> <span class="dt">Zero</span> a <span class="kw">where</span><span class="ot"> zero ::</span> a
<span class="kw">class</span> <span class="dt">Mul</span> a <span class="kw">where</span><span class="ot"> (*) ::</span> a <span class="ot">-></span> a <span class="ot">-></span> a
<span class="kw">class</span> <span class="dt">One</span> a <span class="kw">where</span><span class="ot"> one ::</span> a
<span class="kw">class</span> <span class="dt">FromInteger</span> a <span class="kw">where</span>
<span class="ot"> fromInteger ::</span> <span class="dt">Integer</span> <span class="ot">-></span> a
<span class="kw">instance</span> <span class="dt">Zero</span> a <span class="kw">where</span> zero <span class="fu">=</span> fromInteger <span class="dv">0</span>
<span class="kw">instance</span> <span class="dt">One</span> a <span class="kw">where</span> one <span class="fu">=</span> fromInteger <span class="dv">1</span>
<span class="kw">class</span> <span class="dt">Signed</span> a <span class="kw">where</span>
<span class="ot"> negate ::</span> a <span class="ot">-></span> a
<span class="ot"> abs ::</span> a <span class="ot">-></span> a
<span class="ot"> signum ::</span> a <span class="ot">-></span> a
<span class="kw">class</span> ( <span class="dt">Eq</span> a
, <span class="dt">Show</span> a
, <span class="dt">Add</span> a
, <span class="dt">Sub</span> a
, <span class="dt">Mul</span> a
, <span class="dt">FromInteger</span> a
, <span class="dt">Signed</span> a) <span class="ot">=></span> <span class="dt">Num</span> a <span class="kw">where</span></code></pre>
<p>which would allow certain numeric types to only implement a subset of the relevant operations:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">data</span> <span class="dt">Nat</span> <span class="fu">=</span> <span class="dt">Zero</span> <span class="fu">|</span> <span class="dt">Succ</span> <span class="dt">Nat</span>
<span class="kw">instance</span> <span class="dt">Add</span> <span class="dt">Nat</span> <span class="kw">where</span>
<span class="dt">Z</span> <span class="fu">+</span> y <span class="fu">=</span> s
<span class="dt">S</span> x <span class="fu">+</span> y <span class="fu">=</span> <span class="dt">S</span> (x <span class="fu">+</span> y)
<span class="co">{- et cetera --- but no implementations for e.g. Signed,</span>
<span class="co"> - which is not meaningful for `Nat`!</span>
<span class="co"> -}</span></code></pre>
<p>and also allow current <code>Num</code> functions to have a looser set of constraints than they do at present:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell">sum<span class="ot"> ::</span> (<span class="dt">Zero</span> a, <span class="dt">Add</span> a) <span class="ot">=></span> [a] <span class="ot">-></span> a
sum (x<span class="fu">:</span>xs) <span class="fu">=</span> x <span class="fu">+</span> sum xs
sum [] <span class="fu">=</span> zero
<span class="ot">prod ::</span> (<span class="dt">One</span> a, <span class="dt">Mul</span> a) <span class="ot">=></span> [a] <span class="ot">-></span> a
prod (x<span class="fu">:</span>xs) <span class="fu">=</span> x <span class="fu">*</span> prod xs
prod [] <span class="fu">=</span> one</code></pre>
<p>We could also consider splitting <code>Arrow</code><sup><a href="#fn4" class="footnoteRef" id="fnref4">4</a></sup> into distinct components:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">class</span> <span class="dt">Category</span> a <span class="ot">=></span> <span class="dt">Pairwise</span> a <span class="kw">where</span>
<span class="ot"> first ::</span> a b c <span class="ot">-></span> a (b, d) (c, d)
<span class="ot"> second ::</span> a b c <span class="ot">-></span> a (d, b) (d, c)
<span class="ot"> (***) ::</span> a b c <span class="ot">-></span> a b' c' <span class="ot">-></span> a (b, b') (c, c')
<span class="ot"> (&&&) ::</span> a b c <span class="ot">-></span> a b c' <span class="ot">-></span> a b (c, c')
<span class="kw">class</span> <span class="dt">Pairwise</span> a <span class="ot">=></span> <span class="dt">Arrow</span> a <span class="kw">where</span>
<span class="ot"> arr ::</span> (b <span class="ot">-></span> c) <span class="ot">-></span> a b c</code></pre>
<p>or even (dare I dream) splitting <code>Bits</code> into <a href="https://downloads.haskell.org/~ghc/7.8.2/docs/html/libraries/base-4.7.0.0/Data-Bits.html#t:Bits">something that is not a 22-method monstrosity</a>!</p>
<h1 id="potential-drawbacks">Potential Drawbacks</h1>
<p>On the other hand, this proposal does have some down-sides:</p>
<h2 id="grepping-for-instance-declarations">Grepping for Instance Declarations</h2>
<p>Right now, I can often find an instance declaration for a type <code>T</code> by grepping for <code>instance C T</code> (modulo some line noise) whereas with this change, it's possible that there <em>is</em> no declaration for <code>instance C T</code>, because all of <code>C</code>'s methods are declared by a subclass <code>C'</code> instead. The compiler ought to be able to deal with this without problem, which means that tools like Haddock documentation should somewhat alleviate this problem, but a user might be confused.</p>
<h2 id="introduces-new-possible-errors">Introduces New Possible Errors</h2>
<p>The declarations below are of course nonsensical, and would be rejected by the compiler—but the fact that this change would <em>introduce new failure conditions at all</em> is a drawback of the proposal.</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">instance</span> <span class="dt">Semigroup</span> <span class="dt">Int</span> <span class="kw">where</span>
mappend <span class="fu">=</span> (<span class="fu">+</span>)
<span class="kw">instance</span> <span class="dt">Monoid</span> <span class="dt">Int</span> <span class="kw">where</span>
<span class="co">-- this conflicts with an existing declaration</span>
mappend <span class="fu">=</span> (<span class="fu">*</span>)
mempty <span class="fu">=</span> <span class="dv">1</span></code></pre>
<h2 id="a-pragma-less-extension">A Pragma-Less Extension</h2>
<p>In order to be <em>really</em> useful, we'd want to use this without a <code>LANGUAGE</code> pragma. After all, we're arguing for it on the basis of preserving backwards-compatibility, but that argument is much less compelling if we still have to change the source files to make use of it! On the other hand, that means we'd have included a GHC <em>extension</em> that takes effect despite not being enabled, which is <em>also</em> a worrying precedent!</p>
<p>It still might be a useful extension even if it had to be enabled by a <code>LANGUAGE</code> pragma, as it is easier to add said pragma to a source file than to manually break apart dozens of instance declarations, but it makes this feature less compelling in general.</p>
<h1 id="in-conclusion">In Conclusion</h1>
<p>As I said before, my primary objection to changes of the above nature is that they are <em>breaking</em>. I don't want to have to modify a handful of miscellaneous instance declarations on a yearly basis as people discover new levels of abstraction or become dissatisfied with current choices, especially as those changes will grow more extensive as I build more projects in Haskell! But with an extension like this, we could grow the typeclass ecosystem gradually and fix what we see as past warts <em>while maintaining backwards-compatibility</em>, which would be a very powerful tool to have.</p>
<div class="footnotes">
<hr />
<ol>
<li id="fn1"><p>This is perhaps more simplistic than we want: we can also use the existing <code>Semigroup</code> class from <a href="http://hackage.haskell.org/package/Semigroup-0.0.7/docs/Data-Semigroup.html#t:Semigroup">the <code>semigroup</code> package</a> and then, in the <code>Monoid</code> class declaration, explain how to derive the methods of the superclass. This would look like:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">class</span> <span class="dt">Semigroup</span> m <span class="ot">=></span> <span class="dt">Monoid</span> m <span class="kw">where</span>
<span class="ot"> mempty ::</span> m
<span class="ot"> mappend ::</span> m <span class="ot">-></span> m <span class="ot">-></span> m
<span class="kw">instance</span> <span class="dt">Semigroup</span> m <span class="kw">where</span>
(<span class="fu">.++.</span>) <span class="fu">=</span> mappend</code></pre>
<p>The example above is slightly simpler, which is why I relegated this version to a footnote.<a href="#fnref1">↩</a></p></li>
<li id="fn2"><p>This isn't a concrete proposal, so maybe the actual syntax or semantics of these things should be changed! I want to focus on the <em>feature</em> and not the <em>instantiation</em>.<a href="#fnref2">↩</a></p></li>
<li id="fn3"><p>For this example, I added <code>Zero</code> and <code>One</code> classes so that a given type might implement an additive and multiplicative unit while not necessarily having a sensible <code>FromInteger</code> implementation. For example, it might not make sense to implement <code>fromInteger</code> for a complex number, but complex numbers clearly have an additive unit:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">data</span> <span class="dt">Complex</span> <span class="fu">=</span> <span class="dt">Complex</span> <span class="dt">Float</span> <span class="dt">Float</span>
<span class="kw">deriving</span> (<span class="dt">Eq</span>, <span class="dt">Show</span>)
<span class="kw">instance</span> <span class="dt">Zero</span> <span class="dt">Complex</span> <span class="kw">where</span>
zero <span class="fu">=</span> <span class="dt">Complex</span> (<span class="dv">0</span><span class="fu">.</span><span class="dv">0</span>, <span class="dv">0</span><span class="fu">.</span><span class="dv">0</span>)</code></pre>
<p>This means that the <code>Sum</code> and <code>Product</code> monoids could be rewritten like:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">newtype</span> <span class="dt">Product</span> a <span class="fu">=</span> <span class="dt">Product</span> {<span class="ot"> getProduct ::</span> a }
<span class="kw">deriving</span> (<span class="dt">Eq</span>, <span class="dt">Show</span>)
<span class="kw">instance</span> (<span class="dt">One</span> a, <span class="dt">Mult</span> a) <span class="ot">=></span> <span class="dt">Monoid</span> (<span class="dt">Product</span> a) <span class="kw">where</span>
mempty <span class="fu">=</span> <span class="dt">Product</span> one
x <span class="ot">`mappend`</span> y <span class="fu">=</span> <span class="dt">Product</span> (getProduct x <span class="fu">*</span> getProduct y)</code></pre>
<p>Notice that I added <code>Zero</code> and <code>One</code> in such a way that an existing <code>Num</code> instance declaration will not have to change anything to implement those classes!<a href="#fnref3">↩</a></p></li>
<li id="fn4"><p>I have on numerous occasions had reason to use the <code>Arrow</code> abstraction, but haven't had a sensible implementation of <code>arr</code>. To use a contrived example, I could define a GADT that can describe the structure of boolean circuits in a way that resembles an Arrow, but has no way of expressing <code>arr</code>:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">data</span> <span class="dt">Circ</span> a b <span class="kw">where</span>
<span class="dt">BoolFunc</span><span class="ot"> ::</span> (<span class="dt">Bool</span> <span class="ot">-></span> <span class="dt">Bool</span>) <span class="ot">-></span> <span class="dt">Circ</span> <span class="dt">Bool</span> <span class="dt">Bool</span>
<span class="dt">Ident</span><span class="ot"> ::</span> <span class="dt">Circ</span> a a
<span class="dt">Compose</span><span class="ot"> ::</span> <span class="dt">Circ</span> a b <span class="ot">-></span> <span class="dt">Circ</span> b c <span class="ot">-></span> <span class="dt">Circ</span> a c
<span class="dt">First</span><span class="ot"> ::</span> <span class="dt">Circ</span> a b <span class="ot">-></span> <span class="dt">Circ</span> (a, d) (b, d)
<span class="dt">Second</span><span class="ot"> ::</span> <span class="dt">Circ</span> a b <span class="ot">-></span> <span class="dt">Circ</span> (d, a) (d, b)
<span class="dt">Parallel</span><span class="ot"> ::</span> <span class="dt">Circ</span> a b <span class="ot">-></span> <span class="dt">Circ</span> a' b' <span class="ot">-></span> <span class="dt">Circ</span> (a, a') (b, b')
<span class="dt">Fanout</span><span class="ot"> ::</span> <span class="dt">Circ</span> a b <span class="ot">-></span> <span class="dt">Circ</span> a b' <span class="ot">-></span> <span class="dt">Circ</span> a (b, b')
<span class="kw">instance</span> <span class="dt">Category</span> <span class="dt">Circ</span> <span class="kw">where</span>
id <span class="fu">=</span> <span class="dt">Ident</span>
(<span class="fu">.</span>) <span class="fu">=</span> flip <span class="dt">Compose</span>
<span class="kw">instance</span> <span class="dt">Arrow</span> <span class="dt">Circ</span> <span class="kw">where</span>
first <span class="fu">=</span> <span class="dt">First</span>
second <span class="fu">=</span> <span class="dt">Second</span>
(<span class="fu">***</span>) <span class="fu">=</span> <span class="dt">Parallel</span>
(<span class="fu">&&&</span>) <span class="fu">=</span> <span class="dt">Fanout</span>
arr <span class="fu">=</span> error <span class="st">"Nothing sensible to put here!"</span>
<span class="co">-- for example, using this definition, we can write xor:</span>
<span class="ot">xor ::</span> <span class="dt">BoolCircuit</span> (<span class="dt">Bool</span>, <span class="dt">Bool</span>) <span class="dt">Bool</span>
xor <span class="fu">=</span> ((first <span class="dt">Not</span> <span class="fu">>>></span> <span class="dt">And</span>) <span class="fu">&&&</span> (second <span class="dt">Not</span> <span class="fu">>>></span> <span class="dt">And</span>)) <span class="fu">>>></span> <span class="dt">Or</span>
<span class="co">-- ...and using xor, write a half-adder:</span>
<span class="ot">halfAdder ::</span> <span class="dt">BoolCircuit</span> (<span class="dt">Bool</span>, <span class="dt">Bool</span>) (<span class="dt">Bool</span>, <span class="dt">Bool</span>)
halfAdder <span class="fu">=</span> xor <span class="fu">&&&</span> <span class="dt">And</span></code></pre>
<p>This is not an unreasonable definition—it would be nice to abstract over such a definition using existing tools—but the structure of the <code>Arrow</code> typeclass makes it difficult!<a href="#fnref4">↩</a></p></li>
</ol>
</div>
</body>
</html>