ZedneWebDave Menendez's personal web site. (Full content feed.)http://www.eyrie.org/~zednenem/feed.atom2019-06-10T15:44:57-04:00Dave Menendezhttp://www.eyrie.org/~zednenem/about/dave.htmlDo not open until release datehttp://www.eyrie.org/~zednenem/2019/06/preorders2019-06-10T15:44:57-04:002019-06-10T15:44:57-04:00
Automatically downloading pre-ordered games makes technical sense, but it’s
frustrating to have something and not be able to use it.
<p>It’s usually a bad idea to pre-order video games, since you are buying something without any real way of knowing whether it’s any good, but <em>Super Mario Maker 2</em> seems like a safe enough bet that I went ahead and did it. I had vaguely recalled that the Switch (and other consoles, I assume) will pre-download pre-ordered games so that you have them ready the minute they're released. This makes a lot of sense, since otherwise you would get a crush of people trying to download the game all at the same time.<sup><a href="http://www.eyrie.org/~zednenem/2019/06/preorders#fn1" class="footnoteRef" id="fnref1">1</a></sup></p>
<p>What I did not expect was for the Switch to put <em>Super Mario Maker 2</em> right there in the console menu. It hasn’t been released yet, so you can’t open it. It just sits there, saying “Yeah, I’m already on your machine, but you can’t play me until Nintendo says so.”</p>
<p>Again, I can see the logic here. The main menu on the Switch is also how you manage software, so you wouldn’t be able to delete it or move it to external storage if it didn’t have an icon. That’s fine. It just feels like having an unwrapped Christmas present sitting under the tree.</p>
<p>Actually, that might be a good idea for Nintendo: if a game is downloaded on the Switch, but not yet released, draw a ribbon or something over the icon. That gives you a way to manage the software, provides a visual cue that it isn’t available yet, and adds a nice festive air.</p>
<div class="footnotes">
<hr />
<ol>
<li id="fn1"><p>There is the issue of day-one patches, where you get the game and immediately have to download an update before you can actually play it, but it’s certainly possible to minimize or even eliminate that.<a href="http://www.eyrie.org/~zednenem/2019/06/preorders#fnref1">↩</a></p></li>
</ol>
</div>
My least favorite phrase in <cite>The Adventure Zone</cite>http://www.eyrie.org/~zednenem/2017/08/taz2017-08-03T23:45:08-04:002017-08-03T23:45:08-04:00
I really enjoy the McElroy podcast <cite>The Adventure Zone</cite>, but
I don’t always like the way Griffin tells the story.<p>One of the podcasts that always works its way to the top of my listening queue is <a href="http://theadventure.zone/"><cite>The Adventure Zone<cite></a>, an “actual-play podcast” in which the <a href="http://mcelroyshows.com/">McElroy brothers</a> and their father play a <cite>Dungeons and Dragons</cite> campaign which started out as a vehicle for jokes and silliness, and gradually became… not exactly <em>serious</em>, because it’s still full of jokes, but compelling.</p>
<p>I’m not really doing a good job of selling it, but I do heartily recommend it if funny, fantasy-themed stories are something you like. When these guys get going, they are very good.<sup><a href="http://www.eyrie.org/~zednenem/2017/08/taz#fn1" class="footnoteRef" id="fnref1">1</a></sup> There's only one episode left in the current story, so you won’t have to worry about waiting for the next episode.</p>
<p>Anyway, while I overall am enjoying <cite>TAZ</cite>, there are a few small things that bug me that I wanted to talk about, and Twitter didn’t seem like a good medium. They’re not about the story itself, but some of the techniques Griffin McElroy, the Dungeon Master, uses to tell the story.</p>
<p>As we’ve gotten towards the end of the larger storyline, Griffin has started inserting bits where he describes things that are happening somewhere else or which had happened in the past. I haven’t listened to other actual-play podcasts, so I don’t know if that sort of thing is common. To me, it creates a distance between the listener and the characters, as we are being given information none of them could reasonably have. That is, instead of having first-person or tight third-person narration, we suddenly have an omniscient narrator telling us a larger story in which the main cast are just one thread. We’re no longer experiencing the story along with the characters; we’re hearing a story involving the characters.</p>
<p>For example, a character recently reappeared in the story after a long absence, and Griffin essentially narrated a flashback montage instead of having the character describe what they’d been up to. That’s a fine choice in a non-interactive medium, especially a visual medium like film, but I feel like it goes against the grain of an interactive medium like role-playing games, because it skips the part where the characters learn what happened, which means they don’t get to react to it.</p>
<p>Again, the problem isn’t the story. It’s the tension between the way the story is told and the nature of the medium being used to tell it.</p>
<p>Which leads me to my second grumble: Griffin’s use of the phrase “we see” when introducing these side stories and flashbacks, and sometimes to describe what’s going on around the main characters. In some cases, he even talks about “the camera” and describes pans. Instead of telling a story, Griffin is describing a movie that tells the story. It’s like an inverse of the advice to “show, don’t tell”, only instead of showing, Griffin is telling how it would be shown. This isn’t so much going against the grain of the medium as importing the narrative language from a different medium entirely. It would be like a novel that started indicating what music would be on the soundtrack for dramatic scenes.</p>
<p>Neither of these ruin the show. I’m still looking forward to the conclusion in a few weeks, and it will be fun to be part of the audience for their next story from the beginning. Actual-play podcasts are a young medium, and I’m sure we all have a lot to learn about how best to present them.</p>
<div class="footnotes">
<hr />
<ol>
<li id="fn1"><p>One of my favorite moments comes around minute 54 in episode 30, when they get into an elevator and launch into two extended jokes about snakes. I still remember listening to it when I was driving home one day and smiling so much my face hurt.<a href="http://www.eyrie.org/~zednenem/2017/08/taz#fnref1">↩</a></p></li>
</ol>
</div>
<code>Arrow</code> is more than <code>Strong</code> and <code>Category</code>http://www.eyrie.org/~zednenem/2017/07/twist2017-07-18T21:07:30-04:002017-07-18T21:07:30-04:00
Several people have claimed that Haskell’s <code>Arrow</code> class is
exactly the intersection of <code>Category</code> and <code>Strong</code>,
but this argument ignores the <code>Arrow</code> laws. I demonstrate a type
which is has lawful instances of <code>Strong</code> and
<code>Category</code> which cannot be made into an <code>Arrow</code>
in a consistent way.<p>Several people have claimed (<a href="https://stackoverflow.com/a/41679602" title="Benjamin Hodgson: Answer on Stack Overflow">1</a>,<a href="https://elvishjerricco.github.io/2017/03/10/profunctors-arrows-and-static-analysis.html" title="Will Fancher: Profunctors, Arrows, & Static Analysis">2</a>,<a href="https://github.com/purescript-deprecated/purescript-arrows/issues/9" title="Edward Kmett: The Arrow class is redundant">3</a>) that Haskell’s <code>Arrow</code> class is exactly the intersection of <code>Category</code> and <code>Strong</code> (from <a href="https://hackage.haskell.org/package/profunctors" title="The profunctors package on Hackage"><code>profunctors</code></a>). This is often justified by a reference to <a href="https://arxiv.org/pdf/1406.4823.pdf">“Notions of Computation as Monoids”</a> by Rivas and Jaskelioff, which shows the correspondence between Arrows and monoids in a category of strong profunctors, but that is actually a different point. To be an <code>Arrow</code>, it is not enough for a type constructor to be an instance of <code>Strong</code> (i.e., a strong profunctor) and be an instance of <code>Category</code> (i.e., having some monoidal structure): the monoid and the strength must also be compatible.</p>
<p>Some quick definitions, for background.</p>
<p>First, the <code>Profunctor</code> and <code>Strong</code> classes and their respective laws:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">class</span> <span class="dt">Profunctor</span> p <span class="kw">where</span>
<span class="ot"> dimap ::</span> (a' <span class="ot">-></span> a) <span class="ot">-></span> (b <span class="ot">-></span> b') <span class="ot">-></span> p a b <span class="ot">-></span> p a' b'
<span class="co">-- Laws:</span>
<span class="co">-- P1: dimap id id p = p</span>
<span class="co">-- P2: dimap f g (dimap h k p) = dimap (h . f) (g . k) p</span>
<span class="kw">class</span> <span class="dt">Profunctor</span> p <span class="ot">=></span> <span class="dt">Strong</span> p <span class="kw">where</span>
<span class="ot"> first' ::</span> p a b <span class="ot">-></span> p (a,c) (b,c)
<span class="co">-- Laws:</span>
<span class="co">-- SP1: first' (first' p) = dimap assocr assocl (first' p)</span>
<span class="co">-- SP2: dimap id fst (first' p) = dimap fst id p</span>
<span class="co">-- SP3: dimap (id *** f) id (first' p) = </span>
<span class="co">-- dimap id (id *** f) (first' p)</span>
<span class="co">-- SP4: dimap (f *** id) (g *** id) (first' a) = </span>
<span class="co">-- first' (dimap f g p)</span>
assocl (x,(y,z)) <span class="fu">=</span> ((x,y),z)
assocr ((x,y),z) <span class="fu">=</span> (x,(y,z))
f <span class="fu">***</span> g <span class="fu">=</span> \(x,y) <span class="ot">-></span> (f x, g y)
<span class="co">-- equivalently, the one from Arrow</span></code></pre>
<p>P1 and P2 are simply the usual functor laws, applied to profunctors. The laws for <code>Strong</code> are not explicitly stated in <code>profunctors</code>, but come from the idea that <code>first</code> is a “strength”. SP3 and SP4 are guaranteed by the parametricity of <code>first'</code>.</p>
<p>Next, the Haskell's <code>Category</code> and <code>Arrow</code> classes and their respective laws:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">class</span> <span class="dt">Category</span> p <span class="kw">where</span>
<span class="ot"> id ::</span> p a a
<span class="ot"> (.) ::</span> p b c <span class="ot">-></span> p a b <span class="ot">-></span> p a c
<span class="co">-- Laws:</span>
<span class="co">-- C1: p . (q . r) = (p . q) . r</span>
<span class="co">-- C2: id . p = p</span>
<span class="co">-- C3: p . id = p</span>
<span class="kw">class</span> <span class="dt">Category</span> p <span class="ot">=></span> <span class="dt">Arrow</span> p <span class="kw">where</span>
<span class="ot"> arr ::</span> (a <span class="ot">-></span> b) <span class="ot">-></span> p a b
<span class="ot"> first ::</span> p a b <span class="ot">-></span> p (a,c) (b,c)
<span class="co">-- Laws:</span>
<span class="co">-- A1: arr id = id</span>
<span class="co">-- A2: arr (g . f) = arr g . arr f</span>
<span class="co">-- A3: first (arr f) = arr (f *** id)</span>
<span class="co">-- A4: first (p . q) = first p . first q</span>
<span class="co">-- A5: arr (id *** f) . first p = first p . arr (id *** f)</span>
<span class="co">-- A6: arr fst . first p = p</span>
<span class="co">-- A7: arr assocr . first (first p) = first p . arr assocr</span></code></pre>
<p>The claim is that any instance of <code>Strong</code> and <code>Category</code> is also an instance of <code>Arrow</code>. That is,</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">newtype</span> <span class="dt">SPCA</span> p a b <span class="fu">=</span> <span class="dt">SPCA</span> {<span class="ot"> unSPCA ::</span> p a b }
<span class="kw">deriving</span> (<span class="dt">Profunctor</span>, <span class="dt">Strong</span>, <span class="dt">Category</span>)
<span class="kw">instance</span> (<span class="dt">Strong</span> p, <span class="dt">Category</span> p) <span class="ot">=></span> <span class="dt">Arrow</span> (<span class="dt">SPCA</span> p) <span class="kw">where</span>
arr f <span class="fu">=</span> <span class="dt">SPCA</span> (dimap f <span class="fu">id</span> <span class="fu">id</span>)
first <span class="fu">=</span> first'</code></pre>
<p>This assumes that the <code>Arrow</code> laws can be proven using only the laws for <code>Profunctor</code>, <code>Strong</code>, and <code>Category</code>, but none of these laws describe the interaction of <code>dimap</code> and <code>first'</code> with <code>(.)</code> and <code>id</code>. Indeed, these laws could not describe these interactions, because <code>Arrow</code> is the first class to include all four of these operations.</p>
<p>Thus, it is possible to define a type with lawful instances of <code>Category</code>, <code>Profunctor</code>, and <code>Strong</code> for which <code>SPCA</code> will give an unlawful <code>Arrow</code>. For example:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">newtype</span> <span class="dt">Twist</span> a b <span class="fu">=</span> <span class="dt">Twist</span> {<span class="ot"> getTwist ::</span> (a,a) <span class="ot">-></span> (b,b) }
<span class="kw">instance</span> <span class="dt">Category</span> <span class="dt">Twist</span> <span class="kw">where</span>
<span class="fu">id</span> <span class="fu">=</span> <span class="dt">Twist</span> <span class="fu">id</span>
<span class="dt">Twist</span> f <span class="fu">.</span> <span class="dt">Twist</span> g <span class="fu">=</span> <span class="dt">Twist</span> (f <span class="fu">.</span> g)
<span class="kw">instance</span> <span class="dt">Profunctor</span> <span class="dt">Twist</span> <span class="kw">where</span>
dimap pre post (<span class="dt">Twist</span> f) <span class="fu">=</span>
<span class="dt">Twist</span> ((post <span class="fu">***</span> post) <span class="fu">.</span> f <span class="fu">.</span> (pre <span class="fu">***</span> pre))
<span class="kw">instance</span> <span class="dt">Strong</span> <span class="dt">Twist</span> <span class="kw">where</span>
first' (<span class="dt">Twist</span> f) <span class="fu">=</span> <span class="dt">Twist</span> (\((a1,c1),(a2,c2)) <span class="ot">-></span>
<span class="kw">let</span> (b1,b2) <span class="fu">=</span> f (a1,a2) <span class="kw">in</span> ((b1,c2),(b2,c1)))</code></pre>
<p>That’s all pretty standard, aside from the twist in the last line. The proofs for the <code>Category</code> and <code>Profunctor</code> laws are obvious. Proofs that <code>Twist</code> satisfies the <code>Strong</code> laws are similarly simple, but perhaps less obvious, so I've included them in the <a href="http://www.eyrie.org/~zednenem/2017/07/twist#appendix">appendix</a>.</p>
<p><strong>Although <code>Twist</code> is a lawful instance of <code>Strong</code> and <code>Category</code>, it is not an <code>Arrow</code>.</strong> In particular, an instance following the <code>SPCA</code> pattern violates several <code>Arrow</code> laws:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">instance</span> <span class="dt">Arrow</span> <span class="dt">Twist</span> <span class="kw">where</span>
arr f <span class="fu">=</span> dimap f <span class="fu">id</span> <span class="fu">id</span>
first <span class="fu">=</span> first'</code></pre>
<p>We can easily observe a violation of A3:</p>
<pre><code>> getTwist (arr (id *** id)) ((1,2),(3,4))
((1,2),(3,4))
> getTwist (first (arr id)) ((1,2),(3,4))
((1,4),(3,2))</code></pre>
<p>A4 is similarly violated.</p>
<h2 id="what-went-wrong">What went wrong?</h2>
<p>Now, this is not a disproof that a monoid in the category of strong profunctors is an arrow. That result is sound. The problem is that having instances of <code>Category</code> and <code>Strong</code> is insufficient does not guarantee being a strong profunctor monoid.</p>
<p>Part of this confusion most likely stems from the loose way Haskell programmers tend to use ideas from category theory. This looseness is often convenient, but it can hide distinctions between related categories with different properties.</p>
<p>For example, <code>Twist</code> can be represented as an object in <strong>Pro</strong>, a monoidal category of profunctors described by Rivas and Jaskelioff. That object forms a monoid. It can also be represented as an object in <strong>SPro</strong>, a monoidal category of strong profunctors, but <em>that</em> object is <em>not</em> a monoid. Haskell gains flexibility by blurring the distinction between objects in <strong>Pro</strong> and objects in <strong>SPro</strong>, but even though the types for their respective monoid operations are the same, the correctness conditions are different.</p>
<h2 id="defining-monoids-of-profunctors">Defining monoids of profunctors</h2>
<p>I mentioned <strong>Pro</strong> and <strong>SPro</strong> and monoids in those categories, so I thought it might be useful to describe them a bit more. This is mostly a recap of the paper, so feel free to skim.</p>
<p>First, <strong>Pro</strong> is a category whose objects are profunctors and whose morphisms are natural transformations between profunctors. To conveniently represent the latter, we define:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">type</span> p <span class="fu">:-></span> q <span class="fu">=</span> forall a b<span class="fu">.</span> p a b <span class="ot">-></span> q a b</code></pre>
<p>Conveniently, any function <code>f :: p :-> q</code> is guaranteed to be a natural transformation by parametricity.</p>
<p>To talk about monoids in <strong>Pro</strong>, we first need to define a monoidal structure, and we’re going to work with profunctor composition. Re-using the terminology from <code>Data.Profunctor.Composition</code>, we have:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">data</span> <span class="dt">Procompose</span> p q a b <span class="fu">=</span>
forall x<span class="fu">.</span> <span class="dt">Procompose</span> (p x b) (q a x)
<span class="kw">instance</span> (<span class="dt">Profunctor</span> p, <span class="dt">Profunctor</span> q)
<span class="ot">=></span> <span class="dt">Profunctor</span> (<span class="dt">Procompose</span> p q) <span class="kw">where</span>
dimap pre post (<span class="dt">Procompose</span> p q) <span class="fu">=</span>
<span class="dt">Procompose</span> (dimap <span class="fu">id</span> post p) (dimap pre <span class="fu">id</span> q)</code></pre>
<p>This is a bifunctor over <strong>Pro</strong>, and has three natural transformations which make it monoidal.</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="ot">pmap ::</span> (p <span class="fu">:-></span> p') <span class="ot">-></span> (q <span class="fu">:-></span> q')
<span class="ot">-></span> (<span class="dt">Procompose</span> p q <span class="fu">:-></span> <span class="dt">Procompose</span> p' q')
pmap f g (<span class="dt">Procompose</span> p q) <span class="fu">=</span> <span class="dt">Procompose</span> (f p) (g q)
<span class="ot">passoc ::</span> <span class="dt">Procompose</span> (<span class="dt">Procompose</span> p q) r <span class="fu">:-></span>
<span class="dt">Procompose</span> p (<span class="dt">Procompose</span> q r)
passoc (<span class="dt">Procompose</span> (<span class="dt">Procompose</span> p q) r <span class="fu">=</span>
<span class="dt">Procompose</span> p (<span class="dt">Procompose</span> q r)
<span class="ot">idr ::</span> <span class="dt">Profunctor</span> p <span class="ot">=></span> <span class="dt">Procompose</span> p (<span class="ot">-></span>) <span class="fu">:-></span> p
idr (<span class="dt">Procompose</span> p f) <span class="fu">=</span> dimap f <span class="fu">id</span> p
<span class="ot">idl ::</span> <span class="dt">Profunctor</span> p <span class="ot">=></span> <span class="dt">Procompose</span> (<span class="ot">-></span>) p <span class="fu">:-></span> p
idl (<span class="dt">Procompose</span> f p) <span class="fu">=</span> dimap <span class="fu">id</span> f p</code></pre>
<p>(The last three all have inverses, but we won’t need them here.)</p>
<p>With these definitions, we can talk about monoids in <strong>Pro</strong> and describe their laws.</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">class</span> <span class="dt">Profunctor</span> p <span class="ot">=></span> <span class="dt">ProfunctorMonoid</span> p <span class="kw">where</span>
<span class="ot"> mult ::</span> <span class="dt">Procompose</span> p p <span class="fu">:-></span> p
<span class="ot"> unit ::</span> (<span class="ot">-></span>) <span class="fu">:-></span> p
<span class="co">-- Laws:</span>
<span class="co">-- PM1: mult . pmap id mult = mult . pmap mult id . passoc</span>
<span class="co">-- PM2: mult . pmap unit id = idl</span>
<span class="co">-- PM3: mult . pmap id unit = idr</span></code></pre>
<p>Given an instance of <code>ProfunctorMonoid</code>, we can define an instance of <code>Category</code> in an obvious way.</p>
<p>Next, <strong>SPro</strong> is a category whose objects are strong profunctors<sup><a href="http://www.eyrie.org/~zednenem/2017/07/twist#fn1" class="footnoteRef" id="fnref1">1</a></sup> and whose morphisms are strong natural transformations, meaning they are compatible with the strengths.</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">type</span> <span class="dt">SPNT</span> p q <span class="fu">=</span> forall a b<span class="fu">.</span> p a b <span class="ot">-></span> q a b
<span class="co">-- Law: f . first' = first' . f</span></code></pre>
<p>Unfortunately, parametricity is not enough to guarantee this. As an example,</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="ot">twist ::</span> (a <span class="ot">-></span> b) <span class="ot">-></span> <span class="dt">Twist</span> a b
twist f <span class="fu">=</span> <span class="dt">Twist</span> (f <span class="fu">***</span> f)</code></pre>
<p>This has the right type to be a strong natural transformation, but it does not respect the strengths.</p>
<pre><code>> getTwist (twist (first' id)) ((1,2),(3,4))
((1,2),(3,4))
> getTwist (first' (twist id)) ((1,2),(3,4))
((1,4),(3,2))</code></pre>
<p>Fortunately, <code>pmap</code>, <code>passoc</code>, <code>idl</code>, and <code>idr</code> do respect the strengths, so we can reuse them when defining a class for strong profunctor monoids:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">class</span> (<span class="dt">Strong</span> p, <span class="dt">ProfunctorMonoid</span> p)
<span class="ot">=></span> <span class="dt">StrongProfunctorMonoid</span> p <span class="kw">where</span>
<span class="ot"> smult ::</span> <span class="dt">SPNT</span> (<span class="dt">Procompose</span> p p) p
<span class="ot"> sunit ::</span> <span class="dt">SPNT</span> (<span class="ot">-></span>) p
<span class="co">-- Laws:</span>
<span class="co">-- SPM1: smult . pmap id smult = mult . pmap smult id . passoc</span>
<span class="co">-- SPM2: smult . pmap sunit id = idl</span>
<span class="co">-- SPM3: smult . pmap id sunit = idr</span>
<span class="kw">instance</span> (<span class="dt">Strong</span> p, <span class="dt">Strong</span> q) <span class="ot">=></span> <span class="dt">Strong</span> (<span class="dt">Procompose</span> p q) <span class="kw">where</span>
first' (<span class="dt">Procompose</span> p q) <span class="fu">=</span> <span class="dt">Procompose</span> (first' p) (first' q)</code></pre>
<p>Note that the only difference between <code>StrongProfunctorMonoid</code> and <code>ProfunctorMonoid</code> is the requirement that <code>smult</code> and <code>sunit</code> respect the strengths. The other laws are effectively the same.</p>
<p>Given an instance of <code>StrongProfunctorMonoid</code>, it is easy to define lawful instances of <code>Category</code> and <code>Arrow</code>, and vice versa.</p>
<h2 id="what-are-the-instances-of-profunctormonoid">What are the instances of <code>ProfunctorMonoid</code>?</h2>
<p>Earlier I mentioned that any instance of <code>ProfunctorMonoid</code> can define an instance of <code>Category</code>, but are instances of <code>Profunctor</code> and <code>Category</code> enough to define a lawful instance of <code>ProfunctorMonoid</code>? I’m not certain.</p>
<p>Certainly, we can define functions with the appropriate types, as the <code>profunctor</code> package does:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="ot">mult' ::</span> <span class="dt">Category</span> p <span class="ot">=></span> <span class="dt">Procompose</span> p p <span class="fu">:-></span> p
mult' (<span class="dt">Procompose</span> p q) <span class="fu">=</span> p <span class="fu">.</span> q
<span class="ot">unit' ::</span> (<span class="dt">Category</span> p, <span class="dt">Profunctor</span> p) <span class="ot">=></span> (<span class="ot">-></span>) <span class="fu">:-></span> p
unit' f <span class="fu">=</span> dimap f <span class="fu">id</span> <span class="fu">id</span></code></pre>
<p>Of these, <code>mult'</code> seems pretty obviously correct. PM1 reduces easily to C1. In contrast, <code>unit'</code> involves an interaction between <code>dimap</code> and <code>id</code>, which is not addressed by any of the available laws. If we knew, for example,</p>
<pre><code>X: dimap id f p . q = p . dimap f id q</code></pre>
<p>that would be sufficient to prove PM2 and PM3 (and also to show that <code>dimap f id id = dimap id f id</code>). Unfortunately, I don’t see any way to derive X algebraically, given the laws we have. Conversely, I don’t see any way to define lawful instances of <code>Category</code> and <code>Profunctor</code> which violate X, so there may be a way to derive it by appealing to aspects of Haskell’s type system. (I would not expect this property to hold in a general categorical setting.)</p>
<p>In particular, P1 and the inability for Haskell functions to distinguish <code>id</code> from an arbitrary function seemingly prevent <code>dimap</code> from marking its results in a way that <code>(.)</code> could use to distinguish the two sides in X. (Note that X is easily proven in the case where <code>f = id</code>.) I imagine something more rigorous could be made of this, but I will have to leave it for better practitioners.</p>
<h2 id="appendix">
Appendix: Proofs
</h2>
<p>Proof that <code>Twist</code> is a lawful instance of <code>Strong</code>:</p>
<pre><code>SP1:
first' (first' p)
=
first' (Twist (\((a1,c1),(a2,c2)) ->
let (b1,b2) = getTwist p (a1,a2) in ((b1,c2),(b2,c1))))
=
Twist (\(((a1,c1),d1),((a2,c2),d2)) ->
let (bc1,bc2) =
let (b1,b2) = getTwist p (a1,a2) in ((b1,c2),(b2,c1))
in ((bc1,d2),(bc2,d1)))
=
Twist (\(((a1,c1),d1),((a2,c2),d2)) ->
let (b1,b2) = getTwist p (a1,a2) in (((b1,c2),d2),(b2,c1),d1))
=
Twist (\(((a1,c1),d1),((a2,c2),d2)) ->
let (b1,b2) = getTwist p (a1,a2)
in (assocl (a1,(c2,d2)), assocl (a2,(c1,d1))))
=
Twist (\(((a1,c1),d1),((a2,c2),d2)) ->
let (bcd1,bcd2) =
let (b1,b2) = getTwist p (a1,a2) in ((a1,(c2,d2)),(a2,(c1,d1)))
in (assocl bcd1, assocl bcd2))
=
Twist (\(((a1,c1),d1),((a2,c2),d2)) ->
let (bcd1,bcd2) = getTwist (first' p) ((a1,(c1,d1)),(a2,(c2,d2)))
in (assocl bcd1, assocl bcd2))
=
Twist (\(acd1,acd2) ->
let (bcd1,bcd2) = getTwist (first' p) (assocr acd1, assocr acd2)
in (assocl bcd1, assocl bcd2)
=
Twist ((assocl *** assocl) . getTwist (first' p) . (assocr *** assocr))
=
dimap assocr assocl (first' p)
SP2:
dimap id fst (first' p)
=
Twist ((fst *** fst) . getTwist (first' p) . (id *** id))
=
Twist ((fst *** fst) . getTwist (first' p))
=
Twist (\((a1,c1),(a2,c2)) -> (fst *** fst) (getTwist (first' p) ((a1,c1),(a2,c2))))
=
Twist (\((a1,c1),(a2,c2)) -> let (b1,b2) = getTwist p (a1,a2) in (fst *** fst) ((b1,c2),(b2,c1)))
=
Twist (\((a1,c1),(a2,c2)) -> let (b1,b2) = getTwist p (a1,a2) in (b1,b2))
=
Twist (\((a1,c1),(a2,c2)) -> getTwist p (a1,a2))
=
Twist (getTwist p . (fst *** fst))
=
Twist ((id *** id) . getTwist p . (fst *** fst))
=
dimap fst id p</code></pre>
<p>SP3 and SP4 are guaranteed by parametricity.</p>
<div class="footnotes">
<hr />
<ol>
<li id="fn1"><p>These objects should be pairs containing a profunctor and a strength. In Haskell, instances of <code>Strong</code> uniquely determine the strength, but this is not true in general. (For example, there is an obvious alternative strength for <code>Twist</code> which <em>is</em> compatible with its <code>Category</code> instance.)<a href="http://www.eyrie.org/~zednenem/2017/07/twist#fnref1">↩</a></p></li>
</ol>
</div>
2016: Not entirely badhttp://www.eyrie.org/~zednenem/2016/12/20162016-12-31T18:08:14-05:002016-12-31T18:08:14-05:00I don’t have much to say about the awful stuff that’s happened this year, so here are some good things that happened to me.<p>This has been quite a year. I won’t try listing all the celebrity deaths, as every time I think of them I get reminded of someone else who had already been crowded out of my mind. More seriously, we have the rise of right-wing nationalism in the US and Europe, leading to the Brexit vote and the election of Donald Trump.</p>
<p>Seriously, Donald Trump is going to be president of the United States in twenty days. I’ve known about this for more than a month, and <em>I still can’t believe it.</em> “President Trump” has been a dystopian punchline for much of my life, and now it’s actually happening. It’s so absurd and awful that I can’t even think of an analogy for it.<sup><a href="http://www.eyrie.org/~zednenem/2016/12/2016#fn1" class="footnoteRef" id="fnref1">1</a></sup></p>
<p>Anyway, I don’t have much to add about the terrible stuff, so I’d like to mention a few good things from my personal 2016.</p>
<p>First is the birth of my first child. She’s a bit over four months old now, and is starting to feel more like an individual. She can smile and laugh, and she’s just learned how to put things in her mouth on purpose. There are hard times—especially in the evening, when she’s too tired to sleep—and we have a few months of teething to look forward to, but overall I’d say we’re all happy.</p>
<p>As a bonus, being a parent means quickly getting over disgust about body fluids. We’ve only had one projectile pooping episode so far, and even then it seemed more funny than gross.</p>
<p>In my <a href="https://www.cs.rutgers.edu/~davemm" title="My academic web page">academic career</a>—which I suddenly can’t recall whether I’ve mentioned here—I've published two papers this year, <a href="https://www.cs.rutgers.edu/~sn349/papers/icse2016-alive-loops.pdf" title="PDF">“Termination checking for LLVM peephole optimizations”</a>—which received a Distinguished Paper Award—and <a href="https://www.cs.rutgers.edu/~sn349/papers/alive-fp-sas16.pdf" title="PDF">“Alive-FP: Automated verification of floating point based peephole optimizations in LLVM”</a>, both of which extend my earlier (joint) work on <a href="https://github.com/nunoplopes/alive/" title="Github page for Alive">Alive</a>, a language for specifying peephole optimizations in the LLVM compiler. Speaking of which, the original <a href="https://www.cs.rutgers.edu/~sn349/papers/alive-pldi15.pdf" title="PDF">Alive paper</a> from last year was selected as a <a href="http://www.sigplan.org/Highlights/Papers/"%20Listing%20of%20ACM%20SIGPLAN%20Research%20Highlights"">SIGPLAN Research Highlight</a> this October.</p>
<p>I could probably say more, but there’s only six hours left in 2016 and I <em>really</em> want to get at least one blog post up this calendar year. In the unlikely event you are reading this today, Happy New Year! To everyone else, thanks for reading. I’m glad this web site still exists in some form.</p>
<div class="footnotes">
<hr />
<ol>
<li id="fn1"><p>Maybe an actual zombie apocalypse or something.<a href="http://www.eyrie.org/~zednenem/2016/12/2016#fnref1">↩</a></p></li>
</ol>
</div>
Amber alerts and the boy who cried “wolf”http://www.eyrie.org/~zednenem/2015/02/amber2015-02-25T22:00:39-05:002015-02-25T22:00:39-05:00
In principle, alerting people to missing children using cell phones
seems like a good idea, but people won’t react well to a jarring alarm
in the middle of the night that they can’t reasonably respond to.
<p>Apparently there was an <a href="http://www.nj.com/news/index.ssf/2015/02/why_a_startling_amber_alert_awakened_people_across_nj_early_this_morning.html" title="NJ.com: Why a startling Amber Alert awakened people across N.J. early this morning">Amber alert around 1:30 AM last night</a> in New Jersey. I don’t know anything about the specific situation, except that they have since found the child in Massachusetts, but I mostly want to talk about the specific notification system. This Amber alert utilized the FCC’s <a href="http://www.fcc.gov/guides/wireless-emergency-alerts-wea" title="FCC explanation of the WEA system">Wireless Emergency Alerts</a> system, meaning that a lot of people’s cell phones turned on their disaster sirens in the middle of the night. That lead to some grumbling the next day, which in turn lead to some <a href="http://www.nj.com/opinion/index.ssf/2015/02/amber_alerts_should_prompt_action_not_anger_editor.html" title="NJ.com: Amber Alerts should prompt action, not anger: Editorial">chiding</a> from the <em>South Jersey Times</em> editorial board.</p>
<blockquote>
<p>Everyone uses their cellphones to chat with friends, text, send party photos or order pizzas.</p>
<p>They can also be used to save a life—and locate a missing child like little Elinor.</p>
<p>[…]</p>
<p>The next time an Amber Alert sounds, don’t curse it. Don't ignore it. It all could be a matter of life or death.</p>
</blockquote>
<p>If you read the comments (not generally advisable), you’ll see plenty of people mocking those who were upset at being awakened by an alert about a situation they couldn’t do anything about. Why worry about your precious “beauty sleep” when there’s a missing kid out there?</p>
<p>This is not a good argument. Yes, the consequences of missing an alert when you are in a position to do something about it far outweigh the inconvenience of being jarred out of sleep by a blaring alarm<sup><a href="http://www.eyrie.org/~zednenem/2015/02/amber#fn1" class="footnoteRef" id="fnref1">1</a></sup> in the middle of the night, but we also need to consider frequencies. How often are these situations likely to happen? I suspect the latter is far more common than the former.</p>
<p>Contrary to <a href="http://www.amberalert.gov/faqs.htm#faq6" title="DOJ: Amber Alert FAQ">claims</a> by the department which manages them, studies show that <a href="http://cjr.sagepub.com/content/33/2/159.abstract" title="Criminal Justice Review: Child Abduction, AMBER Alert, and Crime Control Theater (abstract)">Amber alerts are not particularly effective</a>. Some have <a href="http://www.slate.com/blogs/crime/2013/08/08/amber_alert_california_let_s_get_rid_of_the_amber_alert_system.html" title="Justin Peters, Slate: Let’s get rid of the AMBER alert system. It doesn’t work.">called for their elimination</a> altogether. I’m not sure we need to go that far, but I think the bar for midnight alerts has to be pretty high. Some people will be okay with it, but others will just disable Amber alerts entirely. I did so myself, after a similar incident last year. I’ve left on the natural disaster/severe weather warnings, but as soon as they stop being used only for severe circumstances they’ll go off as well.</p>
<p>I mentioned the boy who cried wolf in the title, even though it’s not an exact match for the situation. You can imagine a variation where the boy yells whenever a wolf gets within ten miles of the sheep, which will probably work out similarly: after a few responses, the townsfolk with realize that there’s nothing useful they can do in response to a distant wolf and stop responding. Then one day the wolves will actually get to the sheep and the flock will be lost, because no one came to assist the boy.</p>
<p>We usually blame the boy for the loss of the sheep, since his indiscriminate warnings lead to the townsfolk not responding when they were needed. Some blame the townsfolk as well, since they could have prevented the loss of the flock. But their mistake was not ignoring the warning: they made a reasonable judgement that it wasn’t worth responding to an alert they probably couldn’t do anything about. Their real mistake was failing to fix their lookout system once they found some problems with it.</p>
<div class="footnotes">
<hr />
<ol>
<li id="fn1"><p>“Jarring” doesn’t really do it justice. The WEA requires a “unique attention signal”, and Apple came up with a pretty alarming one.<a href="http://www.eyrie.org/~zednenem/2015/02/amber#fnref1">↩</a></p></li>
</ol>
</div>
How Apple secures iMessagehttp://www.eyrie.org/~zednenem/2014/03/imessage2014-03-01T12:08:10-05:002014-03-01T12:08:10-05:00
Apple has explained how iMessage’s design protects your messages from third-parties—even themselves.<p>Cool article describing <a href="http://techcrunch.com/2014/02/27/apple-explains-exactly-how-secure-imessage-really-is/" title="Greg Kumparak: Apple Explains Exactly How Secure iMessage Really Is (2014-02-28)">Apple’s security measures for iMessage</a>, based on the <a href="http://images.apple.com/iphone/business/docs/iOS_Security_Feb14.pdf" title="Apple: iOS Security (PDF)">white paper</a> Apple released last month. It’s actually a lot more secure than I had expected.</p>
<p>The quick summary involves public-key cryptography, which uses a pair of keys to encrypt and decrypt messages. Messages encrypted using the public key can only be decrypted with the corresponding private key, and vice-versa. Essentially, when Bob joins iMessage, his device generates a public/private key pair and sends the public key to Apple. The private key never leaves his device. If Alice wants to send a message to Bob, her phone obtains Bob’s public key from Apple, encrypts the message, and then passes it to Apple who forwards it to Bob. Since Apple doesn’t have Bob’s private key, they have no way of reading the message.</p>
<p>There’s actually a <em>second</em> pair of public/private keys used as well, which Alice uses to digitally sign her message, so that Bob’s device can tell it came from her and not someone else. If Bob has multiple devices, then each one has its own set of keys, and Alice encrypts the message such that each of Bob’s private keys can decrypt it.<sup><a href="http://www.eyrie.org/~zednenem/2014/03/imessage#fn1" class="footnoteRef" id="fnref1">1</a></sup></p>
<p>The key takeaway here is that Apple can’t read Alice’s messages to Bob without considerable effort on their part. If the system works as designed, Apple never has a decryption key, so they have no special ability to decrypt messages.</p>
<p>The “as designed” is important: Alice has to trust that her software works as described. On iOS, there is no way to independently verify how iMessage is implemented. Furthermore, since Apple handles the key distribution, they might be able to implement a Man-in-the-Middle attack: instead of sending Alice Bob’s actual public key, they could send a public key that they control, decrypt the message, and then re-encrypt using Bob’s public key.<sup><a href="http://www.eyrie.org/~zednenem/2014/03/imessage#fn2" class="footnoteRef" id="fnref2">2</a></sup></p>
<p>Given Apple’s recent <a href="http://daringfireball.net/2014/02/apple_prism" title="John Gruber: On the Timing of iOS’s SSL Vulnerability and Apple’s ‘Addition’ to the NSA’s PRISM Program (2014-02-22)">SSL flaw</a> (<a href="http://daringfireball.net/2014/02/apple_prism" title="John Gruber: On the Timing of iOS’s SSL Vulnerability and Apple’s ‘Addition’ to the NSA’s PRISM Program (2014-02-22)">1</a>, <a href="https://www.schneier.com/blog/archives/2014/02/was_the_ios_ssl.html" title="Bruce Schneier: Was the iOS SSL Flaw Deliberate? (2014-02-27)">2</a>) and the <a href="https://www.schneier.com/blog/archives/2014/02/dropoutjeep_nsa.html" title="Bruce Schneier: DROPOUTJEEP: NSA Exploit of the Day (2014-02-12)">NSA’s claimed iOS exploits</a>, it’s not unreasonable to be wary of Apple’s security claims, but I still feel comfortable with the system for iMessage. It’s already more secure than e-mail or text messaging, and Apple has no real incentive to compromise their users’ privacy.</p>
<p>(via <a href="http://daringfireball.net/linked/2014/02/28/imessage-security" title="John Gruber: Apple Offers More Details on iMessage Security (2014-02-28)">Daring Fireball</a>)</p>
<div class="footnotes">
<hr />
<ol>
<li id="fn1"><p>Apparently, this involves encrypting the entire message multiple times if it’s short, or using the public key to encrypt a symmetric key—presumably similar to the way PGP works.<a href="http://www.eyrie.org/~zednenem/2014/03/imessage#fnref1">↩</a></p></li>
<li id="fn2"><p>The white paper is not clear on whether Alice signs the encrypted message or the plaintext. If she authenticates the encrypted message, then I don’t think this attack could work.<a href="http://www.eyrie.org/~zednenem/2014/03/imessage#fnref2">↩</a></p></li>
</ol>
</div>
Hemingway and software-assisted writinghttp://www.eyrie.org/~zednenem/2014/02/hemingway2014-02-27T12:27:48-05:002014-02-27T12:27:48-05:00
Two recent apps claim to help improve your writing, but their advice is based on misapplying questionable rules.
<p>Interesting <a href="http://bygonebureau.com/2014/02/17/death-and-syntaxes/" title="The Bygone Bureau: Death and Syntaxes">article by Kevin Nguyen</a> about two recent apps, Hemmingway and Writer Pro, which are alleged to help improve your writing. There are a bunch of problems with this strategy. As Nguyen points out:</p>
<blockquote>
<p>Basically, Hemingway is a writing tool with a syntax highlighter, which identifies word types and sets them in different colors. This is a long-standing feature in text editors built for coding; it makes programming languages more readable and errors easier to identify. That is to say, Hemingway’s feature set is less indicative of how writers actually write and more about how a developer-centric mindset would view writing: treat prose as code.</p>
</blockquote>
<p>This is the first problem: highlighting, say, all the adverbs in a piece of text doesn’t really make writing any easier.</p>
<p>The second problem, which <a href="http://languagelog.ldc.upenn.edu/nll/?p=10416" title="Language Log: “Hemingway” on Hemingway">Mark Lieberman points out</a>, is that Hemingway (and Writer Pro, to a lesser extent) are basing their judgements on bad rules, like “avoid adverbs” and “don’t use the passive voice”. Yes, many professional writers will give advice like that, but examining their text will show they don’t <em>follow</em> that advice.<sup><a href="http://www.eyrie.org/~zednenem/2014/02/hemingway#fn1" class="footnoteRef" id="fnref1">1</a></sup></p>
<p>More seriously, Hemmingway can’t actually tell whether you’re following the rules. As one commenter at Language Log points out, Hemmingway incorrectly flags sentences like “John was red” as passive. Its identification of adverbs seems to be based primarily on whether a word ends in “ly”. Sentences like “Teh teh teh teh teh.” are judged easy to read, presumably because they contain a small number of short words.</p>
<p>In other words, Hemmingway is advising you by applying questionable rules to faulty data.<sup><a href="http://www.eyrie.org/~zednenem/2014/02/hemingway#fn2" class="footnoteRef" id="fnref2">2</a></sup></p>
<p>That being said: there <em>are</em> times when highlighting would be useful for improving writing. We already have spelling checkers that underline misspelled words. I would like a feature that highlights common homophones like “their”/“there”/“they’re” when I’m doing the final editing pass. That way, I can scan the text and make sure each one is correct. Unlike trying to identify adverbs or the passive voice, this would be pretty easy to automate, too.</p>
<p>(Hemmingway rates this article at grade 12, incidentally.)</p>
<p>(via <a href="http://verynicewebsite.net/2014/02/death-and-syntaxes/" title="It’s a Very Nice Web Site: “Death and Syntaxes”">John Moltz</a>)</p>
<div class="footnotes">
<hr />
<ol>
<li id="fn1"><p>I suspect things like “don’t use adverbs” is a reaction to amateur writers using too many adverbs. In other words, there’s an implicit “too much”.<a href="http://www.eyrie.org/~zednenem/2014/02/hemingway#fnref1">↩</a></p></li>
<li id="fn2"><p>One also has to question the credibility of software that gives advice like “Aim for 0 or fewer.”<a href="http://www.eyrie.org/~zednenem/2014/02/hemingway#fnref2">↩</a></p></li>
</ol>
</div>
More on Free Applicative Functorshttp://www.eyrie.org/~zednenem/2013/06/freeapp-22013-06-12T00:57:42-04:002013-06-12T00:57:42-04:00
Since free applicative functors are free, does that mean they are monads
over indexed types? Also, can we squeeze out any more performance?<h2 id="monads-over-indexed-types">Monads over indexed types</h2>
<p>In my last two technical posts in this series, I discussed <a href="http://www.eyrie.org/~zednenem/2013/05/27/freeapp" title="ZedneWeb: Free Applicative Functors in Haskell (2013-05-27)">free applicative functors</a> and <a href="http://www.eyrie.org/~zednenem/2013/06/prompt" title="ZedneWeb: Prompt Monads are Free (2013-06-07)"><code>Prompt</code> monads</a>. In the latter, I showed that <code>Prompt</code> monads are “free”, and that because they’re free, <code>Prompt</code> is a <a href="http://www.eyrie.org/~zednenem/2012/07/29/paramonads" title="ZedneWeb: Parameterized monads vs monads over indexed types (2012-07-29)">monad in the category of indexed types</a>. Naturally, the question arises: do free applicative functors <em>also</em> lead to monads?</p>
<p>Let’s define a category <strong>A</strong> of applicative functors and applicative morphisms. That is, functions <code>t :: f :-> g</code> such that,</p>
<pre><code>f (pure a) = pure a
f (x <*> y) = f x <*> f y</code></pre>
<p>Again, we can define a forgetful functor <em>U'</em> : <strong>A</strong> → <strong>I</strong>. The implementations <code>Free</code>, <code>C1</code>, and <code>C2</code>, correspond to left adjoints of <em>U'</em>, which means they’re all instances of <code>IMonad</code>.</p>
<p>This page is literate Haskell, so feel free to copy and paste into a <code>*.lhs</code> file and load it up in GHCi. You’ll also need to save the <a href="http://www.eyrie.org/~zednenem/2013/05/27/freeapp" title="ZedneWeb: Free Applicative Functors in Haskell (2013-05-27)">FreeApp</a> post, or download its <a href="http://www.eyrie.org/~zednenem/2013/files/FreeApp.lhs">source</a>. The <a href="http://www.eyrie.org/~zednenem/2013/files/FreeApp2.lhs">source for this article</a> is also available.</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="ot">{-# LANGUAGE RankNTypes, GADTs, TypeOperators #-}</span>
<span class="fu">></span>
<span class="fu">></span> <span class="kw">module</span> <span class="dt">FreeApp2</span> <span class="kw">where</span>
<span class="fu">></span>
<span class="fu">></span> <span class="kw">import</span> <span class="dt">Control.Applicative</span>
<span class="fu">></span> <span class="kw">import</span> <span class="dt">FreeApp</span></code></pre>
<p>For the sake of being somewhat self-contained, here are the definitions of <code>IMonad</code> and friends.</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">type</span> p <span class="fu">:-></span> q <span class="fu">=</span> forall i<span class="fu">.</span> p i <span class="ot">-></span> q i
<span class="fu">></span>
<span class="fu">></span> <span class="kw">class</span> <span class="dt">IFunctor</span> f <span class="kw">where</span>
<span class="fu">></span><span class="ot"> imap ::</span> (p <span class="fu">:-></span> q) <span class="ot">-></span> (f p <span class="fu">:-></span> f q)
<span class="fu">></span>
<span class="fu">></span> <span class="kw">class</span> <span class="dt">IFunctor</span> f <span class="ot">=></span> <span class="dt">IMonad</span> f <span class="kw">where</span>
<span class="fu">></span><span class="ot"> iskip ::</span> p <span class="fu">:-></span> f p
<span class="fu">></span><span class="ot"> iextend ::</span> (p <span class="fu">:-></span> f q) <span class="ot">-></span> (f p <span class="fu">:-></span> f q)
<span class="fu">></span>
<span class="fu">></span><span class="ot"> (?>=) ::</span> <span class="dt">IMonad</span> f <span class="ot">=></span> f p i <span class="ot">-></span> (p <span class="fu">:-></span> f q) <span class="ot">-></span> f q i
<span class="fu">></span> m <span class="fu">?>=</span> f <span class="fu">=</span> iextend f m</code></pre>
<p>Recall the definition of <code>Free</code>:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">data</span> <span class="dt">Free</span> f a <span class="kw">where</span>
<span class="dt">Pure</span><span class="ot"> ::</span> a <span class="ot">-></span> <span class="dt">Free</span> f a
<span class="dt">App</span><span class="ot"> ::</span> f a <span class="ot">-></span> <span class="dt">Free</span> f (a <span class="ot">-></span> b) <span class="ot">-></span> <span class="dt">Free</span> f b</code></pre>
<p>The <code>IFunctor</code> instance is straightforward:</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">instance</span> <span class="dt">IFunctor</span> <span class="dt">Free</span> <span class="kw">where</span>
<span class="fu">></span> imap f (<span class="dt">Pure</span> x) <span class="fu">=</span> <span class="dt">Pure</span> x
<span class="fu">></span> imap f (<span class="dt">App</span> x xs) <span class="fu">=</span> <span class="dt">App</span> (f x) (imap f xs)</code></pre>
<p>In the <code>IMonad</code> instance, <code>iskip</code> is just <code>liftFree</code>. We could define <code>iextend</code> in terms of <code>lowerFree</code> and <code>imap</code>, but let’s define a more general operation instead.</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">instance</span> <span class="dt">IMonad</span> <span class="dt">Free</span> <span class="kw">where</span>
<span class="fu">></span> iskip x <span class="fu">=</span> <span class="dt">App</span> x (<span class="dt">Pure</span> <span class="fu">id</span>)
<span class="fu">></span> iextend <span class="fu">=</span> runFree
<span class="fu">></span>
<span class="fu">></span><span class="ot"> runFree ::</span> <span class="kw">Applicative</span> g <span class="ot">=></span> (f <span class="fu">:-></span> g) <span class="ot">-></span> <span class="dt">Free</span> f a <span class="ot">-></span> g a
<span class="fu">></span> runFree f (<span class="dt">Pure</span> a) <span class="fu">=</span> pure a
<span class="fu">></span> runFree f (<span class="dt">App</span> x xs) <span class="fu">=</span> f x <span class="fu"><**></span> runFree f xs</code></pre>
<p>Note that <code>runFree</code> maps an index-preserving function to an applicative morphism. Its inverse is <code>(. iskip)</code>.</p>
<h3>
C1
</h3>
<p>My <code>C1</code> and <code>C2</code> implementations both rely on <code>CSeq</code>, which represents a sequence of effects.</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">data</span> <span class="dt">CSeq</span> f a <span class="kw">where</span>
<span class="dt">CNil</span><span class="ot"> ::</span> <span class="dt">CSeq</span> f ()
<span class="dt">CCons</span><span class="ot"> ::</span> f a <span class="ot">-></span> <span class="dt">CSeq</span> f u <span class="ot">-></span> <span class="dt">CSeq</span> f (a,u)</code></pre>
<p>As with <code>Free</code>, this is clearly an instance of <code>IFunctor</code>.</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">instance</span> <span class="dt">IFunctor</span> <span class="dt">CSeq</span> <span class="kw">where</span>
<span class="fu">></span> imap f <span class="dt">CNil</span> <span class="fu">=</span> <span class="dt">CNil</span>
<span class="fu">></span> imap f (<span class="dt">CCons</span> x xs) <span class="fu">=</span> <span class="dt">CCons</span> (f x) (imap f xs)</code></pre>
<p>We’ll also generalize <code>reduce</code> slightly<sup><a href="http://www.eyrie.org/~zednenem/2013/06/freeapp-2#fn1" class="footnoteRef" id="fnref1">1</a></sup> by defining:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell">runCSeq f <span class="fu">=</span> reduce <span class="fu">.</span> imap f</code></pre>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span><span class="ot"> runCSeq ::</span> <span class="kw">Applicative</span> g <span class="ot">=></span> (f <span class="fu">:-></span> g) <span class="ot">-></span> <span class="dt">CSeq</span> f u <span class="ot">-></span> g u
<span class="fu">></span> runCSeq f <span class="dt">CNil</span> <span class="fu">=</span> pure ()
<span class="fu">></span> runCSeq f (<span class="dt">CCons</span> x xs) <span class="fu">=</span> (,) <span class="fu"><$></span> f x <span class="fu"><*></span> runCSeq f xs</code></pre>
<p>Using this, we can easily define the <code>IFunctor</code> and <code>IMonad</code> instances of <code>C1</code>:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">data</span> <span class="dt">C1</span> f a <span class="fu">=</span> forall u<span class="fu">.</span> <span class="dt">C1</span> (u <span class="ot">-></span> a) (<span class="dt">CSeq</span> f u)</code></pre>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span><span class="ot"> runC1 ::</span> <span class="kw">Applicative</span> g <span class="ot">=></span> (f <span class="fu">:-></span> g) <span class="ot">-></span> <span class="dt">C1</span> f a <span class="ot">-></span> g a
<span class="fu">></span> runC1 t (<span class="dt">C1</span> f x) <span class="fu">=</span> f <span class="fu"><$></span> runCSeq t x
<span class="fu">></span>
<span class="fu">></span> <span class="kw">instance</span> <span class="dt">IFunctor</span> <span class="dt">C1</span> <span class="kw">where</span>
<span class="fu">></span> imap g (<span class="dt">C1</span> f x) <span class="fu">=</span> <span class="dt">C1</span> f (imap g x)
<span class="fu">></span>
<span class="fu">></span> <span class="kw">instance</span> <span class="dt">IMonad</span> <span class="dt">C1</span> <span class="kw">where</span>
<span class="fu">></span> iskip a <span class="fu">=</span> <span class="dt">C1</span> <span class="fu">fst</span> (<span class="dt">CCons</span> a <span class="dt">CNil</span>)
<span class="fu">></span> iextend <span class="fu">=</span> runC1</code></pre>
<h3>
C2
</h3>
<p>Again, we can use <code>runCSeq</code> to easily define <code>runC2</code>, which we will use for <code>iextend</code>.</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">newtype</span> <span class="dt">C2</span> f a <span class="fu">=</span> <span class="dt">C2</span>
{<span class="ot"> unC2 ::</span> forall u y z<span class="fu">.</span>
(forall x<span class="fu">.</span> (x <span class="ot">-></span> y) <span class="ot">-></span> <span class="dt">CSeq</span> f x <span class="ot">-></span> z) <span class="ot">-></span>
(u <span class="ot">-></span> a <span class="ot">-></span> y) <span class="ot">-></span>
<span class="dt">CSeq</span> f u <span class="ot">-></span> z }</code></pre>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span><span class="ot"> runC2 ::</span> <span class="kw">Applicative</span> g <span class="ot">=></span> (f <span class="fu">:-></span> g) <span class="ot">-></span> <span class="dt">C2</span> f a <span class="ot">-></span> g a
<span class="fu">></span> runC2 t x
<span class="fu">></span> <span class="fu">=</span> unC2 x (\f s <span class="ot">-></span> f <span class="fu"><$></span> runCSeq t s) (<span class="fu">const</span> <span class="fu">id</span>) <span class="dt">CNil</span>
<span class="fu">></span>
<span class="fu">></span> <span class="kw">instance</span> <span class="dt">IMonad</span> <span class="dt">C2</span> <span class="kw">where</span>
<span class="fu">></span> iskip a <span class="fu">=</span> <span class="dt">C2</span> (\k f s <span class="ot">-></span> k (\(a,s) <span class="ot">-></span> f s a) (<span class="dt">CCons</span> a s))
<span class="fu">></span> iextend <span class="fu">=</span> runC2</code></pre>
<p>The necessary instance for <code>IFunctor</code> is a little more difficult. The problem is that <code>C2</code> takes a <code>CSeq f</code> as an argument <em>and</em> passes one to its continuation. So, <code>x</code> will be expecting a <code>CSeq f</code>, but <code>imap f x</code> will receive a <code>CSeq g</code>, and we don’t have any way to translate.</p>
<p>Fortunately, we can get around this by passing an empty sequence to <code>x</code> and then appending the input sequence to the sequence <code>x</code> passes to its continuation. We can do this because instances of <code>C2</code> never examines the input sequence.</p>
<p>Thus:</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">instance</span> <span class="dt">IFunctor</span> <span class="dt">C2</span> <span class="kw">where</span>
<span class="fu">></span> imap g x <span class="fu">=</span> <span class="dt">C2</span> (\k f s <span class="ot">-></span>
<span class="fu">></span> unC2 x
<span class="fu">></span> (\f' s' <span class="ot">-></span>
<span class="fu">></span> rebaseC1 (imap g s') k
<span class="fu">></span> (\v u <span class="ot">-></span> f v (f' u)) s)
<span class="fu">></span> (<span class="fu">const</span> <span class="fu">id</span>)
<span class="fu">></span> <span class="dt">CNil</span>)</code></pre>
<p>It’s possible to save a traversal here by defining a variant of <code>rebaseC1</code> that merges in an <code>imap</code>, but I’ll refrain.</p>
<h2 id="faster-free-applicative-functors">Faster Free Applicative Functors</h2>
<p>Sometime after I posted my original <a href="http://www.eyrie.org/~zednenem/2013/05/27/freeapp" title="ZedneWeb: Free Applicative Functors in Haskell (2013-05-27)">fast free applicatives</a>, I came up with yet another implementation idea. <code>C2</code> improved on <code>C1</code> by replacing the tail of the sequence with a variable, similar to replacing <code>[a]</code> with <code>[a] -> [a]</code>. But another way of representing lists involves replacing <code>[a]</code> with its Church representation:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell">forall b<span class="fu">.</span> (a <span class="ot">-></span> b <span class="ot">-></span> b) <span class="ot">-></span> b <span class="ot">-></span> b</code></pre>
<p>That is, the arguments to <code>foldr</code>.</p>
<p>We try the same thing for <code>CSeq</code>. First, its fold:</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span><span class="ot"> foldCSeq ::</span> (forall a u<span class="fu">.</span> f a <span class="ot">-></span> p u <span class="ot">-></span> p (a,u)) <span class="ot">-></span>
<span class="fu">></span> p () <span class="ot">-></span>
<span class="fu">></span> <span class="dt">CSeq</span> f u <span class="ot">-></span> p u
<span class="fu">></span> foldCSeq cons nil (<span class="dt">CCons</span> x xs) <span class="fu">=</span> cons x (foldCSeq cons nil xs)
<span class="fu">></span> foldCSeq cons nil <span class="dt">CNil</span> <span class="fu">=</span> nil</code></pre>
<p>Unlike <code>foldr</code>, <code>foldCSeq</code> has to work with a GADT. This makes the types a little more complicated. Our return type, <code>p</code> can be anything, as long as we can define an appropriate <code>cons</code> function. For example, <code>p</code> could be <code>Const Integer</code> and our <code>cons</code> can add one.</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span><span class="ot"> size ::</span> <span class="dt">CSeq</span> f a <span class="ot">-></span> <span class="dt">Integer</span>
<span class="fu">></span> size <span class="fu">=</span> getConst <span class="fu">.</span>
<span class="fu">></span> foldCSeq (\_ <span class="ot">-></span> <span class="dt">Const</span> <span class="fu">.</span> (<span class="fu">+</span><span class="dv">1</span>) <span class="fu">.</span> getConst) (<span class="dt">Const</span> <span class="dv">0</span>)</code></pre>
<p>We’ll be seeing a lot of things with the same type as that <code>cons</code> argument, so let’s define an alias:</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">type</span> <span class="dt">Build</span> f p <span class="fu">=</span> forall a u<span class="fu">.</span> f a <span class="ot">-></span> p u <span class="ot">-></span> p (a,u)</code></pre>
<p>My first attempt to use this was a variation of <code>C1</code>. The most obvious implementation would simply replace <code>CSeq f u</code> with its encoding:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">data</span> <span class="dt">B0</span> f a <span class="fu">=</span> forall u<span class="fu">.</span>
<span class="dt">B0</span> (a <span class="ot">-></span> u) (forall p<span class="fu">.</span> <span class="dt">Build</span> f p <span class="ot">-></span> p () <span class="ot">-></span> p u)</code></pre>
<p>But that would still need something like <code>reduceC1</code>, since the sequence is implicitly terminated by the <code>p ()</code> argument. So instead, I chose to leave the sequence tail abstract, as in <code>C2</code>.</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">newtype</span> <span class="dt">B1</span> f a <span class="fu">=</span> <span class="dt">B1</span> {<span class="ot"> unB1 ::</span> forall p u z<span class="fu">.</span>
<span class="fu">></span> (forall v<span class="fu">.</span> (v <span class="ot">-></span> a) <span class="ot">-></span> p v <span class="ot">-></span> z) <span class="ot">-></span>
<span class="fu">></span> <span class="dt">Build</span> f p <span class="ot">-></span> p u <span class="ot">-></span> z }
<span class="fu">></span>
<span class="fu">></span><span class="ot"> runB1 ::</span> <span class="kw">Applicative</span> g <span class="ot">=></span> (f <span class="fu">:-></span> g) <span class="ot">-></span> <span class="dt">B1</span> f a <span class="ot">-></span> g a
<span class="fu">></span> runB1 f x <span class="fu">=</span> unB1 x <span class="fu">fmap</span> (liftA2 (,) <span class="fu">.</span> f) (pure ())
<span class="fu">></span>
<span class="fu">></span><span class="ot"> convB1C1 ::</span> <span class="dt">B1</span> f a <span class="ot">-></span> <span class="dt">C1</span> f a
<span class="fu">></span> convB1C1 x <span class="fu">=</span> unB1 x <span class="dt">C1</span> <span class="dt">CCons</span> <span class="dt">CNil</span></code></pre>
<p>As the definition of <code>convB1C1</code> suggests, <code>B1</code> is essentially <code>C1</code> with all its constructors made abstract. In fact, under normal use, <code>B1</code> will never actually construct a <code>CSeq</code>.</p>
<p>Most of the instances are fairly simple.</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">instance</span> <span class="kw">Functor</span> (<span class="dt">B1</span> f) <span class="kw">where</span>
<span class="fu">></span> <span class="fu">fmap</span> f x <span class="fu">=</span> <span class="dt">B1</span> (\k <span class="ot">-></span> unB1 x (\g <span class="ot">-></span> k (f <span class="fu">.</span> g)))
<span class="fu">></span>
<span class="fu">></span> <span class="kw">instance</span> <span class="dt">IFunctor</span> <span class="dt">B1</span> <span class="kw">where</span>
<span class="fu">></span> imap t x <span class="fu">=</span> <span class="dt">B1</span> (\k cons <span class="ot">-></span> unB1 x k (cons <span class="fu">.</span> t))
<span class="fu">></span>
<span class="fu">></span> <span class="kw">instance</span> <span class="dt">IMonad</span> <span class="dt">B1</span> <span class="kw">where</span>
<span class="fu">></span> iskip x <span class="fu">=</span> <span class="dt">B1</span> (\k c n <span class="ot">-></span> k <span class="fu">fst</span> (c x n))
<span class="fu">></span> iextend <span class="fu">=</span> runB1</code></pre>
<p>As with <code>C2</code>, the challenge is in the definition of <code>x <*> y</code>, where we must somehow pass the result of <code>y</code> to <code>x</code>. With <code>C2</code>, we had an extra type parameter that we could use to smuggle the result in, and the same is true here: we can hide the extra value by changing <code>p</code>.</p>
<p><code>P a p</code> augments an abstract sequence <code>p</code> with an extra parameter that extracts a value of type <code>a</code>.</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">data</span> <span class="dt">P</span> a p u <span class="fu">=</span> <span class="dt">P</span> (u <span class="ot">-></span> a) (p u)
<span class="fu">></span>
<span class="fu">></span><span class="ot"> consP ::</span> <span class="dt">Build</span> f p <span class="ot">-></span> <span class="dt">Build</span> f (<span class="dt">P</span> a p)
<span class="fu">></span> consP c x (<span class="dt">P</span> f xs) <span class="fu">=</span> <span class="dt">P</span> (f <span class="fu">.</span> <span class="fu">snd</span>) (c x xs)</code></pre>
<p>Using it, we can define the <code>Applicative</code> instance like so:</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">instance</span> <span class="kw">Applicative</span> (<span class="dt">B1</span> f) <span class="kw">where</span>
<span class="fu">></span> pure a <span class="fu">=</span> <span class="dt">B1</span> (\k c n <span class="ot">-></span> k (<span class="fu">const</span> a) n)
<span class="fu">></span>
<span class="fu">></span> x <span class="fu"><*></span> y <span class="fu">=</span> <span class="dt">B1</span> (\k c n <span class="ot">-></span>
<span class="fu">></span> unB1 y
<span class="fu">></span> (\f pu <span class="ot">-></span>
<span class="fu">></span> unB1 x
<span class="fu">></span> (\g (<span class="dt">P</span> h pv) <span class="ot">-></span> k (\v <span class="ot">-></span> g v (h v)) pv)
<span class="fu">></span> (consP c)
<span class="fu">></span> (<span class="dt">P</span> f pu))
<span class="fu">></span> c
<span class="fu">></span> n)</code></pre>
<p>Like <code>C2</code>, <code>B1</code> avoids recursion entirely in its definitions. Unfortunately, it duplicates work. As you can see, in the section <code>\v -> g v (h v)</code>, the tuple generated by the effect sequence must be passed to <code>x</code> and <code>y</code>, each of which will filter out the portion that does not apply to them. Since <code><*></code> is the primary operation for applicatives, this bodes poorly for performance.</p>
<h3 id="b2">
B2
</h3>
<p>Instead of abstracting <code>CCons</code> in <code>C1</code>, we could also abstract it in <code>C2</code>. This gives us another possible implementation:</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">newtype</span> <span class="dt">B2</span> f a <span class="fu">=</span> <span class="dt">B2</span> {<span class="ot"> unB2 ::</span> forall p u y z<span class="fu">.</span>
<span class="fu">></span> <span class="dt">Build</span> f p <span class="ot">-></span>
<span class="fu">></span> (forall x<span class="fu">.</span> (x <span class="ot">-></span> y) <span class="ot">-></span> p x <span class="ot">-></span> z) <span class="ot">-></span>
<span class="fu">></span> (u <span class="ot">-></span> a <span class="ot">-></span> y) <span class="ot">-></span> p u <span class="ot">-></span> z }
<span class="fu">></span>
<span class="fu">></span><span class="ot"> runB2 ::</span> <span class="kw">Applicative</span> g <span class="ot">=></span>
<span class="fu">></span> (forall a<span class="fu">.</span> f a <span class="ot">-></span> g a) <span class="ot">-></span> <span class="dt">B2</span> f a <span class="ot">-></span> g a
<span class="fu">></span> runB2 f x
<span class="fu">></span> <span class="fu">=</span> unB2 x (liftA2 (,) <span class="fu">.</span> f) <span class="fu">fmap</span> (<span class="fu">const</span> <span class="fu">id</span>) (pure ())
<span class="fu">></span>
<span class="fu">></span> <span class="kw">instance</span> <span class="kw">Functor</span> (<span class="dt">B2</span> f) <span class="kw">where</span>
<span class="fu">></span> <span class="fu">fmap</span> g x <span class="fu">=</span> <span class="dt">B2</span> (\c k f <span class="ot">-></span> unB2 x c k (\s <span class="ot">-></span> f s <span class="fu">.</span> g))
<span class="fu">></span>
<span class="fu">></span> <span class="kw">instance</span> <span class="kw">Applicative</span> (<span class="dt">B2</span> f) <span class="kw">where</span>
<span class="fu">></span> pure a <span class="fu">=</span> <span class="dt">B2</span> (\_ k f <span class="ot">-></span> k (<span class="fu">flip</span> f a))
<span class="fu">></span>
<span class="fu">></span> x <span class="fu"><*></span> y <span class="fu">=</span> <span class="dt">B2</span> (\c k f <span class="ot">-></span>
<span class="fu">></span> unB2 y c (unB2 x c k) (\s a g <span class="ot">-></span> f s (g a)))
<span class="fu">></span>
<span class="fu">></span> <span class="kw">instance</span> <span class="dt">IFunctor</span> <span class="dt">B2</span> <span class="kw">where</span>
<span class="fu">></span> imap t x <span class="fu">=</span> <span class="dt">B2</span> (\cons <span class="ot">-></span> unB2 x (cons <span class="fu">.</span> t))
<span class="fu">></span>
<span class="fu">></span> <span class="kw">instance</span> <span class="dt">IMonad</span> <span class="dt">B2</span> <span class="kw">where</span>
<span class="fu">></span> iskip x <span class="fu">=</span> <span class="dt">B2</span> (\c k f pu <span class="ot">-></span> k (\(a,s) <span class="ot">-></span> f s a) (c x pu))
<span class="fu">></span> iextend <span class="fu">=</span> runB2</code></pre>
<p>Aside from the extra <code>c</code> parameters, the only differences between <code>C2</code> and <code>B2</code> are in <code>imap</code> and <code>runB2</code>, both of which take advantage of the fact that <code>c</code> can be any appropriately-typed function, not just <code>CCons</code>.</p>
<h3 id="performance">
Performance
</h3>
<p>So how does the B-series compare with the C-series? As before, I used Criterion to time the various implementations traversing balanced trees of various sizes.</p>
<div class="figure">
<img src="http://www.eyrie.org/~zednenem/2013/files/tree-b-1.png" width="450" height="300" alt="Chart">
<p class="caption">
Time to traverse a tree of <em>n</em> elements
</p>
</div>
<p>The results show <code>B1</code> beating <code>C1</code>, with <code>C2</code> and <code>B2</code> better than both.</p>
<p>Comparisons of <code>C2</code> and <code>B2</code> are less clear. The initial tests I ran last month gave an edge to <code>B2</code> of about 2 μs for <em>n</em>=100, but the tests I ran today show <code>C2</code> faster by 0.2 μs. There are too many variables to know what caused the difference, so for now I’ll declare their performance “about the same”.<sup><a href="http://www.eyrie.org/~zednenem/2013/06/freeapp-2#fn2" class="footnoteRef" id="fnref2">2</a></sup></p>
<p>Since the main area where <code>B2</code> improves on <code>C2</code> is the implementation of <code>imap</code> and <code>run<var>X</var></code>, I tried the same experiment again with the addition of a single <code>imap id</code> after the <code>sequenceA</code>. Here, the results do favor <code>B2</code>:</p>
<div class="figure">
<img src="http://www.eyrie.org/~zednenem/2013/files/tree-b-2.png" width="450" height="300" alt="Chart">
<p class="caption">
Time to traverse a tree of <em>n</em> elements and call <code>imap</code>
</p>
</div>
<p>At <em>n</em>=100, <code>B2</code> stays at about 22 μs, but <code>C2</code> jumps to 30 μs. This suggests that <code>B2</code> is definitely preferable for code using <code>imap</code>, and since it isn’t much worse (if at all) in other code, it suggests that <code>B2</code> should be preferred in general.</p>
<div class="footnotes">
<hr />
<ol>
<li id="fn1"><p>Arguably, <code>reduce</code> is more primitive, since defining <code>runCSeq</code> in terms of it requires <code>imap</code>, but, on the other hand, <code>reduce = runCSeq id</code>.<a href="http://www.eyrie.org/~zednenem/2013/06/freeapp-2#fnref1">↩</a></p></li>
<li id="fn2"><p>Performance-sensitive applications should probably be using a dedicated implementation in the first place.<a href="http://www.eyrie.org/~zednenem/2013/06/freeapp-2#fnref2">↩</a></p></li>
</ol>
</div>
Prompt Monads are Freehttp://www.eyrie.org/~zednenem/2013/06/prompt2013-06-07T22:18:42-04:002013-06-07T22:18:42-04:00
A brief look at <code>Prompt</code> monads, showing that they are free
monads, that <code>Prompt</code> is a monad over indexed types, and how it
can be used to build composable components.<p>In a <a href="http://www.eyrie.org/~zednenem/2013/05/27/freeapp">recent post</a>, I casually described Prompt monads as free monads. This is one of those facts that is probably well-known, but which I’ve never seen explicitly stated anywhere, so I figured I’d do so here.</p>
<p>I’m going to assume some basic knowledge of category theory here: specifically, the definitions of category and functor. All the rest I’ll explain as we go along. If that’s not your cup of tea, or if the fact that <code>Prompt</code> is free is already obvious, feel free to <a href="http://www.eyrie.org/~zednenem/2013/06/prompt#implications">skip ahead</a>.</p>
<p>This document is a literate Haskell file. You should be able to copy it directly out of your browser, save it as a file called “FreePrompt.lhs”, and load it into GHCi. Alternately, you can download the my original <a href="http://www.eyrie.org/~zednenem/2013/files/FreePrompt.lhs">lhs+markdown file</a>.</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="ot">{-# LANGUAGE RankNTypes, GADTs, TypeOperators #-}</span>
<span class="fu">></span>
<span class="fu">></span> <span class="kw">module</span> <span class="dt">FreePrompt</span> <span class="kw">where</span>
<span class="fu">></span>
<span class="fu">></span> <span class="kw">import</span> <span class="dt">Control.Monad</span>
<span class="fu">></span> <span class="kw">import</span> <span class="dt">Control.Monad.Cont</span>
<span class="fu">></span> <span class="kw">import</span> <span class="dt">Control.Monad.Reader</span></code></pre>
<p>Let’s start by defining two categories. The first, <strong>I</strong>, is the category of indexed types and type-preserving functions. We'll write <code>f :-> g</code> for an index-preserving function from <code>f</code> to <code>g</code>.</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">type</span> f <span class="fu">:-></span> g <span class="fu">=</span> forall i<span class="fu">.</span> f i <span class="ot">-></span> g i</code></pre>
<p>The second, <strong>M</strong>, is the category of Haskell monads—or, more accurately, the category of instances of the <code>Monad</code> class. Its arrows are <em>monad morphisms</em>, which are index-preserving functions that respect the <code>Monad</code> operations. That is, if <code>f :: m :-> n</code> is a monad morphism from <code>m</code> to <code>n</code>, then we have</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell">f (<span class="fu">return</span> a) <span class="fu">=</span> <span class="fu">return</span> a
f m <span class="fu">>>=</span> f <span class="fu">.</span> g <span class="fu">=</span> f (m <span class="fu">>>=</span> g)</code></pre>
<p>for any <code>a</code>, <code>m</code>, and <code>g</code> of the appropriate types.</p>
<p>Since every instance of <code>Monad</code> is an indexed type (in the sense that it takes a single parameter), and since every monad morphism is an index-preserving function, we can say that <strong>M</strong> is a <em>subcategory</em> of <strong>I</strong>. This implies the existence of a functor <em>U</em> : <strong>M</strong> → <strong>I</strong> which simply maps things to themselves. This is known as a <em>forgetful</em> functor, because it discards the extra structure in <strong>M</strong>.</p>
<p>Now let’s talk about <code>Prompt</code>. Here’s one basic definition:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">data</span> <span class="dt">Prompt</span> p a
<span class="fu">=</span> <span class="dt">Done</span> a
<span class="fu">|</span> forall i<span class="fu">.</span> <span class="dt">Prompt</span> (p i) (i <span class="ot">-></span> <span class="dt">Prompt</span> p a)
<span class="ot">prompt ::</span> p a <span class="ot">-></span> <span class="dt">Prompt</span> p a
prompt p <span class="fu">=</span> <span class="dt">Prompt</span> p <span class="dt">Done</span></code></pre>
<p>Essentially, a computation of type <code>Prompt p a</code> is either a pure value, or a prompt and a continuation.</p>
<p>While simple, this particular implementation has performance problems, so we’ll use its Church encoding:</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">newtype</span> <span class="dt">Prompt</span> p a
<span class="fu">></span> <span class="fu">=</span> <span class="dt">P</span> (forall b<span class="fu">.</span> (forall i<span class="fu">.</span> p i <span class="ot">-></span> (i <span class="ot">-></span> b) <span class="ot">-></span> b) <span class="ot">-></span> (a <span class="ot">-></span> b) <span class="ot">-></span> b)
<span class="fu">></span>
<span class="fu">></span> unP (<span class="dt">P</span> f) <span class="fu">=</span> f
<span class="fu">></span>
<span class="fu">></span><span class="ot"> prompt ::</span> p a <span class="ot">-></span> <span class="dt">Prompt</span> p a
<span class="fu">></span> prompt p <span class="fu">=</span> <span class="dt">P</span> (\c <span class="ot">-></span> c p)</code></pre>
<p>We’ll also provide a simple way to run computations:</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span><span class="ot"> run ::</span> <span class="kw">Monad</span> m <span class="ot">=></span> (p <span class="fu">:-></span> m) <span class="ot">-></span> <span class="dt">Prompt</span> p a <span class="ot">-></span> m a
<span class="fu">></span> run f m <span class="fu">=</span> unP m (\p k <span class="ot">-></span> f p <span class="fu">>>=</span> k) <span class="fu">return</span></code></pre>
<p>The <code>Monad</code> instance is what interests us here.</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">instance</span> <span class="kw">Monad</span> (<span class="dt">Prompt</span> p) <span class="kw">where</span>
<span class="fu">></span> <span class="fu">return</span> x <span class="fu">=</span> <span class="dt">P</span> (\c k <span class="ot">-></span> k x)
<span class="fu">></span> m <span class="fu">>>=</span> f <span class="fu">=</span> <span class="dt">P</span> (\c k <span class="ot">-></span> unP m c (\a <span class="ot">-></span> unP (f a) c k))</code></pre>
<p>Notice that <code>Prompt p</code> is a monad for any indexed type <code>p</code>. In other words, it maps the objects of <strong>I</strong> to <strong>M</strong>. We can similarly define</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span><span class="ot"> pmap ::</span> (p <span class="fu">:-></span> q) <span class="ot">-></span> (<span class="dt">Prompt</span> p <span class="fu">:-></span> <span class="dt">Prompt</span> q)
<span class="fu">></span> pmap f m <span class="fu">=</span> <span class="dt">P</span> (\c k <span class="ot">-></span> unP m (c <span class="fu">.</span> f) k)</code></pre>
<p>which maps index-preserving functions to monad morphisms.<sup><a href="http://www.eyrie.org/~zednenem/2013/06/prompt#fn1" class="footnoteRef" id="fnref1">1</a></sup> This means we can define a functor <em>P</em> : <strong>I</strong> → <strong>M</strong>.</p>
<p>Now we’re going to argue that <em>P</em> is the left adjoint of <em>U</em>. There are a few ways of doing this, including showing an isomorphism between index-preserving functions <em>f</em> : <em>T</em> → <em>U</em> <em>M</em> and monad morphisms <em>g</em> : <em>P</em> <em>T</em> → <em>M</em>, but I’m going to focus on defining the unit and counit.</p>
<p>The unit, η : 1 ⇒ <em>PU</em>, gives a family of index-preserving functions. The counit, ε : <em>UP</em> ⇒ 1, gives a family of monad morphisms. In Haskell, these correspond to the types,</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="ot">unit ::</span> p <span class="fu">:-></span> <span class="dt">Prompt</span> p
<span class="ot">counit ::</span> (<span class="kw">Monad</span> m) <span class="ot">=></span> <span class="dt">Prompt</span> m <span class="fu">:-></span> m</code></pre>
<p>with the additional requirement that <code>counit</code> is a monad morphism. <code>unit</code> is pretty clearly the same thing as <code>prompt</code>, and we’ll define <code>counit</code> as <code>run id</code>.</p>
<p>Next, we should show that <code>run id</code> is a monad morphism. In fact, <code>run f</code> is a monad morphism for any <code>f</code>. The proof that <code>run f (return a) = return a</code> is simple, and for the proof that <code>run f (m >>= g) = run f m >>= run f . g</code>, we only need to consider the case where <code>m = prompt p</code>:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"> run f (prompt p <span class="fu">>>=</span> g)
<span class="fu">=</span> unP (prompt p <span class="fu">>>=</span> g) (\p k <span class="ot">-></span> f p <span class="fu">>>=</span> k) <span class="fu">return</span>
<span class="fu">=</span> unP (prompt p) (\p k <span class="ot">-></span> f p <span class="fu">>>=</span> k)
(\a <span class="ot">-></span> unP (g a) (\p k <span class="ot">-></span> f p <span class="fu">>>=</span> k) <span class="fu">return</span>)
<span class="fu">=</span> f p <span class="fu">>>=</span> run f <span class="fu">.</span> g
run f (prompt p) <span class="fu">>>=</span> run f <span class="fu">.</span> g
<span class="fu">=</span> unP (prompt p) (\p k <span class="ot">-></span> f p <span class="fu">>>=</span> k) <span class="fu">return</span> <span class="fu">>>=</span> run f <span class="fu">.</span> g
<span class="fu">=</span> f p <span class="fu">>>=</span> <span class="fu">return</span> <span class="fu">>>=</span> run f <span class="fu">.</span> g
<span class="fu">=</span> f p <span class="fu">>>=</span> run f <span class="fu">.</span> g</code></pre>
<h2 id="implications">Implications</h2>
<p>There are two interesting implications to the fact that <em>P</em> is a left adjoint of <em>U</em>. First, since <em>U</em> is a forgetful functor, <em>P</em> is free. In other words, <code>Prompt p</code> is simplest monad that can be derived from a type constructor <code>p</code>.</p>
<p>Second, <em>PU</em> is a monad in <strong>I</strong>.<sup><a href="http://www.eyrie.org/~zednenem/2013/06/prompt#fn2" class="footnoteRef" id="fnref2">2</a></sup> We already have the unit, η, and we can define μ using ε.</p>
<p>μ = <em>UεP</em> : <em>UPUP</em> ⇒ <em>UP</em></p>
<p>Now, we’ve seen <a href="http://www.eyrie.org/~zednenem/2012/07/29/paramonads">monads in <strong>I</strong></a> before; Conor McBride described them in “Kleisli Arrows of Outrageous Fortune”.</p>
<p>For the sake of making this complete, here are the definitions of <code>IFunctor</code> and <code>IMonad</code> again:</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">class</span> <span class="dt">IFunctor</span> f <span class="kw">where</span>
<span class="fu">></span><span class="ot"> imap ::</span> (p <span class="fu">:-></span> q) <span class="ot">-></span> (f p <span class="fu">:-></span> f q)
<span class="fu">></span>
<span class="fu">></span> <span class="kw">class</span> <span class="dt">IFunctor</span> f <span class="ot">=></span> <span class="dt">IMonad</span> f <span class="kw">where</span>
<span class="fu">></span><span class="ot"> iskip ::</span> p <span class="fu">:-></span> f p
<span class="fu">></span><span class="ot"> iextend ::</span> (p <span class="fu">:-></span> f q) <span class="ot">-></span> (f p <span class="fu">:-></span> f q)
<span class="fu">></span>
<span class="fu">></span><span class="ot"> (?>=) ::</span> <span class="dt">IMonad</span> f <span class="ot">=></span> f p i <span class="ot">-></span> (p <span class="fu">:-></span> f q) <span class="ot">-></span> f q i
<span class="fu">></span> m <span class="fu">?>=</span> f <span class="fu">=</span> iextend f m</code></pre>
<p>It should be pretty obvious that <code>imap</code> is just <code>pmap</code> and <code>iskip</code> is <code>prompt</code>. <code>iextend</code> could be defined as <code>\f -> run id . pmap f</code>, but we’ll simplify it.</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">instance</span> <span class="dt">IFunctor</span> <span class="dt">Prompt</span> <span class="kw">where</span>
<span class="fu">></span> imap <span class="fu">=</span> pmap
<span class="fu">></span>
<span class="fu">></span> <span class="kw">instance</span> <span class="dt">IMonad</span> <span class="dt">Prompt</span> <span class="kw">where</span>
<span class="fu">></span> iskip <span class="fu">=</span> prompt
<span class="fu">></span> iextend f m <span class="fu">=</span> <span class="dt">P</span> (\c <span class="ot">-></span> unP m (\p <span class="ot">-></span> unP (f p) c))</code></pre>
<p>Note that, since <code>run id</code> and <code>pmap f</code> are monad morphisms, <code>iextend f</code> is a monad morphism for any function <code>f</code>.</p>
<h2 id="components">Components</h2>
<p>So, is this good for anything? Well, it turns out that functions of the type <code>p :-> Prompt q</code> are a pretty good approximation of the components Johan Granström describes in his paper <a href="http://ojs.academypublisher.com/index.php/jsw/article/view/jsw070511361148">“A new paradigm for component-based development”</a> (<a href="http://ojs.academypublisher.com/index.php/jsw/article/download/jsw070511361148/4771">PDF</a>).</p>
<p>The basic idea is that a computation <code>m :: Prompt p a</code> may interact with an external “world” through the interface <code>p</code>. A component <code>f :: p :-> Prompt q</code> provides an implementation of <code>p</code> in terms of another interface, <code>q</code>.</p>
<p>Coming up with examples that are self-contained and interesting is difficult, so I’ll give part of a UTF-8 converter I wrote using this style. It was part of an exercise in making iteratee-like components. Essentially, an iteratee uses the <code>Stream e</code> interface to request elements of type <code>e</code>.</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">data</span> <span class="dt">Chunk</span> e <span class="fu">=</span> <span class="dt">Chunk</span> e <span class="fu">|</span> <span class="dt">EOS</span>
<span class="fu">></span>
<span class="fu">></span> <span class="kw">data</span> <span class="dt">Stream</span> e i <span class="kw">where</span>
<span class="fu">></span> <span class="dt">SRead</span><span class="ot"> ::</span> <span class="dt">Stream</span> e (<span class="dt">Chunk</span> e)</code></pre>
<p>When I was writing my UTF-8 converter, I occasionally wanted to be able to read the next byte in the stream <em>only</em> if it met certain criteria. Otherwise, I wanted it to stay in the stream for later. This could have been done by adding local state to the converter, but since most stream providers will offer some lookahead, I figured my converter could use a variation I called “guarded streams”.</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">data</span> <span class="dt">GStream</span> e i <span class="kw">where</span>
<span class="fu">></span> <span class="dt">GReadAny</span><span class="ot"> ::</span> <span class="dt">GStream</span> e (<span class="dt">Chunk</span> e)
<span class="fu">></span> <span class="dt">GReadOnly</span><span class="ot"> ::</span> (e <span class="ot">-></span> <span class="dt">Bool</span>) <span class="ot">-></span> <span class="dt">GStream</span> e (<span class="dt">Maybe</span> e)</code></pre>
<p>The idea is that <code>GReadOnly f</code> provides a test, <code>f</code>. If the next element of the stream does not satisfy <code>f</code> or is the end-of-stream, the world should return <code>Nothing</code> and leave the next element or EOS for subsequent reads.<sup><a href="http://www.eyrie.org/~zednenem/2013/06/prompt#fn3" class="footnoteRef" id="fnref3">3</a></sup></p>
<p>As a very simple example of a component using <code>GStream</code>, here’s one that collects runs of a character.</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span><span class="ot"> charRuns ::</span> <span class="dt">Stream</span> (<span class="dt">Char</span>, <span class="dt">Int</span>) <span class="fu">:-></span> <span class="dt">Prompt</span> (<span class="dt">GStream</span> <span class="dt">Char</span>)
<span class="fu">></span> charRuns <span class="dt">SRead</span> <span class="fu">=</span> <span class="kw">do</span>
<span class="fu">></span> ch <span class="ot"><-</span> prompt <span class="dt">GReadAny</span>
<span class="fu">></span> <span class="kw">case</span> ch <span class="kw">of</span>
<span class="fu">></span> <span class="dt">Chunk</span> c <span class="ot">-></span> collect c <span class="dv">1</span>
<span class="fu">></span> <span class="dt">EOS</span> <span class="ot">-></span> <span class="fu">return</span> <span class="dt">EOS</span>
<span class="fu">></span> <span class="kw">where</span>
<span class="fu">></span> collect c n <span class="fu">=</span> <span class="kw">do</span>
<span class="fu">></span> mc <span class="ot"><-</span> prompt (<span class="dt">GReadOnly</span> (<span class="fu">==</span> c))
<span class="fu">></span> <span class="kw">case</span> mc <span class="kw">of</span>
<span class="fu">></span> <span class="kw">Nothing</span> <span class="ot">-></span> <span class="fu">return</span> (<span class="dt">Chunk</span> (c,n))
<span class="fu">></span> <span class="kw">Just</span> _ <span class="ot">-></span> collect c (n<span class="dv">+1</span>)</code></pre>
<p>This reads one character, then requests only additional characters equal to the first one. If the input is an “a” followed by a “b”, the <code>GReadOnly</code> will return <code>Nothing</code> and save the “b” for the future.</p>
<p>To show this in action, we’ll provide a generic consumer:</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span><span class="ot"> collect ::</span> <span class="dt">Prompt</span> (<span class="dt">Stream</span> e) [e]
<span class="fu">></span> collect <span class="fu">=</span> <span class="kw">do</span>
<span class="fu">></span> ch <span class="ot"><-</span> prompt <span class="dt">SRead</span>
<span class="fu">></span> <span class="kw">case</span> ch <span class="kw">of</span>
<span class="fu">></span> <span class="dt">Chunk</span> e <span class="ot">-></span> liftM (e<span class="fu">:</span>) collect
<span class="fu">></span> <span class="dt">EOS</span> <span class="ot">-></span> <span class="fu">return</span> []</code></pre>
<p>And using some interpreters <a href="http://www.eyrie.org/~zednenem/2013/06/prompt#interpreters">defined below</a>, we can see how it works:</p>
<pre>
<samp>*FreePrompt></samp> <kbd>stateful1 gstream "aaabcc" (collect >>= charRuns)</kbd>
<samp>[('a',3),('b',1),('c',2)]</samp>
</pre>
<p>The control flow here is more complicated than the familiar Haskell monads. In <code>collect ?>= charRuns</code>, control passes from <code>collect</code> to <code>charRuns</code> whenever <code>collect</code> invokes <code>prompt</code>, but it returns to <code>collect</code> once <code>charRuns</code> produces an answer. This can be understood by looking at the monad laws and remembering that <code>?>= f</code> is a monad morphism.</p>
<p>We have:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"> (prompt p <span class="fu">>>=</span> f) <span class="fu">?>=</span> g
<span class="fu">=</span> (prompt p <span class="fu">?>=</span> g) <span class="fu">>>=</span> \x <span class="ot">-></span> f x <span class="fu">?>=</span> g
<span class="fu">=</span> g p <span class="fu">>>=</span> \x <span class="ot">-></span> f x <span class="fu">?>=</span> g</code></pre>
<p>Essentially, <code>iextend</code> gives us a way to compose subroutines.</p>
<p>Now, for a more complex component. <code>charRuns</code> requires a guarded stream, but what if our stream provider only supports unguarded streams? Well, we can implement <code>GStream</code> using an unguarded stream and some state. Since components don’t have state that persists across invocations, we’ll add the state to our interface.</p>
<p>Here’s the interface for mutable state:</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">data</span> <span class="dt">St</span> s i <span class="kw">where</span>
<span class="fu">></span> <span class="dt">Get</span><span class="ot"> ::</span> <span class="dt">St</span> s s
<span class="fu">></span> <span class="dt">Put</span><span class="ot"> ::</span> s <span class="ot">-></span> <span class="dt">St</span> s ()</code></pre>
<p>We can combine <code>Stream e</code> and <code>St s</code> by using the lifted sum from before.</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">data</span> (p <span class="fu">:</span>\<span class="fu">/</span> q) i <span class="fu">=</span> <span class="dt">L</span> (p i) <span class="fu">|</span> <span class="dt">R</span> (q i)</code></pre>
<p>And here’s the component:</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span><span class="ot"> guardStream ::</span>
<span class="fu">></span> <span class="dt">GStream</span> e <span class="fu">:-></span> <span class="dt">Prompt</span> (<span class="dt">St</span> (<span class="dt">Maybe</span> (<span class="dt">Chunk</span> e)) <span class="fu">:</span>\<span class="fu">/</span> <span class="dt">Stream</span> e)
<span class="fu">></span> guardStream <span class="dt">GReadAny</span> <span class="fu">=</span> <span class="kw">do</span>
<span class="fu">></span> mch <span class="ot"><-</span> prompt (<span class="dt">L</span> <span class="dt">Get</span>)
<span class="fu">></span> <span class="kw">case</span> mch <span class="kw">of</span>
<span class="fu">></span> <span class="kw">Nothing</span> <span class="ot">-></span> prompt (<span class="dt">R</span> <span class="dt">SRead</span>)
<span class="fu">></span> <span class="kw">Just</span> ch <span class="ot">-></span> <span class="kw">do</span>
<span class="fu">></span> prompt (<span class="dt">L</span> (<span class="dt">Put</span> <span class="kw">Nothing</span>))
<span class="fu">></span> <span class="fu">return</span> ch
<span class="fu">></span> guardStream (<span class="dt">GReadOnly</span> f) <span class="fu">=</span> <span class="kw">do</span>
<span class="fu">></span> mch <span class="ot"><-</span> prompt (<span class="dt">L</span> <span class="dt">Get</span>)
<span class="fu">></span> <span class="kw">case</span> mch <span class="kw">of</span>
<span class="fu">></span> <span class="kw">Nothing</span> <span class="ot">-></span> <span class="kw">do</span>
<span class="fu">></span> ch <span class="ot"><-</span> prompt (<span class="dt">R</span> <span class="dt">SRead</span>)
<span class="fu">></span> <span class="kw">case</span> ch <span class="kw">of</span>
<span class="fu">></span> <span class="dt">Chunk</span> e <span class="fu">|</span> f e <span class="ot">-></span> <span class="fu">return</span> (<span class="kw">Just</span> e)
<span class="fu">></span> _ <span class="ot">-></span> <span class="kw">do</span>
<span class="fu">></span> prompt (<span class="dt">L</span> (<span class="dt">Put</span> (<span class="kw">Just</span> ch)))
<span class="fu">></span> <span class="fu">return</span> <span class="kw">Nothing</span>
<span class="fu">></span> <span class="kw">Just</span> ch <span class="ot">-></span> <span class="kw">do</span>
<span class="fu">></span> <span class="kw">case</span> ch <span class="kw">of</span>
<span class="fu">></span> <span class="dt">Chunk</span> e <span class="fu">|</span> f e <span class="ot">-></span> <span class="kw">do</span>
<span class="fu">></span> prompt (<span class="dt">L</span> (<span class="dt">Put</span> <span class="kw">Nothing</span>))
<span class="fu">></span> <span class="fu">return</span> (<span class="kw">Just</span> e)
<span class="fu">></span> _ <span class="ot">-></span> <span class="fu">return</span> <span class="kw">Nothing</span></code></pre>
<p>We’ll combine two interpreters for the two interfaces</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> streamState s
<span class="fu">></span> <span class="fu">=</span> stateful stream s <span class="fu">.</span> lstateful state <span class="kw">Nothing</span></code></pre>
<pre>
<samp>*FreePrompt></samp> <kbd>let op = collect ?>= charRuns ?>= guardStream</kbd>
<samp>*FreePrompt></samp> <kbd>streamState "abba" op</kbd>
<samp>[('a',1),('b',2),('a',1)]</samp>
</pre>
<p>Note that the two interfaces, <code>St s</code> and <code>Stream e</code> are independent. If we had some other component <code>c :: Stream e :-> Prompt Q</code>, we could easily connect it to <code>guardStream</code> by using <code>\/</code> or some similar function.</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> (f \<span class="fu">/</span> g) (<span class="dt">L</span> p) <span class="fu">=</span> f p
<span class="fu">></span> (f \<span class="fu">/</span> g) (<span class="dt">R</span> q) <span class="fu">=</span> g q
<span class="fu">></span>
<span class="fu">></span><span class="ot"> iright ::</span> <span class="dt">IMonad</span> m <span class="ot">=></span> (p <span class="fu">:-></span> m q) <span class="ot">-></span> ((r <span class="fu">:</span>\<span class="fu">/</span> p) <span class="fu">:-></span> m (r <span class="fu">:</span>\<span class="fu">/</span> q))
<span class="fu">></span> iright f <span class="fu">=</span> (iskip <span class="fu">.</span> <span class="dt">L</span>) \<span class="fu">/</span> (imap <span class="dt">R</span> <span class="fu">.</span> f)</code></pre>
<h2 id="generators">Generators</h2>
<p><code>Prompt</code> is closely related to the <code>ICont</code> monad I discussed <a href="http://www.eyrie.org/~zednenem/2012/07/29/paramonads">previously</a>:</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">newtype</span> <span class="dt">ICont</span> q p i <span class="fu">=</span> <span class="dt">ICont</span> {<span class="ot"> unICont ::</span> (p <span class="fu">:-></span> q) <span class="ot">-></span> q i }
<span class="fu">></span>
<span class="fu">></span> <span class="kw">instance</span> <span class="dt">IFunctor</span> (<span class="dt">ICont</span> q) <span class="kw">where</span>
<span class="fu">></span> imap f m <span class="fu">=</span> <span class="dt">ICont</span> (\k <span class="ot">-></span> unICont m (k <span class="fu">.</span> f))
<span class="fu">></span>
<span class="fu">></span> <span class="kw">instance</span> <span class="dt">IMonad</span> (<span class="dt">ICont</span> q) <span class="kw">where</span>
<span class="fu">></span> iskip x <span class="fu">=</span> <span class="dt">ICont</span> (\k <span class="ot">-></span> k x)
<span class="fu">></span> iextend f m <span class="fu">=</span> <span class="dt">ICont</span> (\k <span class="ot">-></span> unICont m (\p <span class="ot">-></span> unICont (f p) k))</code></pre>
<p>When <code>q</code> is a continuation monad, they are (almost) interconvertible.</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span><span class="ot"> to ::</span> <span class="dt">Prompt</span> p a <span class="ot">-></span> <span class="dt">ICont</span> (<span class="dt">Cont</span> b) p a
<span class="fu">></span> to m <span class="fu">=</span> <span class="dt">ICont</span> (\c <span class="ot">-></span> cont (unP m (runCont <span class="fu">.</span> c)))
<span class="fu">></span>
<span class="fu">></span><span class="ot"> from ::</span> (forall b<span class="fu">.</span> <span class="dt">ICont</span> (<span class="dt">Cont</span> b) p a) <span class="ot">-></span> <span class="dt">Prompt</span> p a
<span class="fu">></span> from m <span class="fu">=</span> <span class="dt">P</span> (\c <span class="ot">-></span> runCont (unICont m (cont <span class="fu">.</span> c)))</code></pre>
<p>Note that <code>from</code> requires the <code>Cont b</code> to be polymorphic in <code>b</code>. This indicates that <code>Prompt</code> is weaker than <code>ICont (Cont b)</code>, in the sense that it only has access to undelimited continuations.</p>
<p>This near-interconvertibility suggests that <code>ICont</code> can have an instance of <code>Monad</code> as well, and it turns out it can when the return type is any monad.</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">instance</span> <span class="kw">Monad</span> q <span class="ot">=></span> <span class="kw">Monad</span> (<span class="dt">ICont</span> q p) <span class="kw">where</span>
<span class="fu">></span> <span class="fu">return</span> x <span class="fu">=</span> <span class="dt">ICont</span> (\_ <span class="ot">-></span> <span class="fu">return</span> x)
<span class="fu">></span> m <span class="fu">>>=</span> f <span class="fu">=</span> <span class="dt">ICont</span> (\k <span class="ot">-></span> unICont m k <span class="fu">>>=</span> \x <span class="ot">-></span> unICont (f x) k)</code></pre>
<p>And, in fact, <code>ICont</code> and <code>Prompt</code> are also interconvertible when <code>ICont</code> is polymorphic over any <code>Monad</code>:</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span><span class="ot"> to' ::</span> <span class="kw">Monad</span> m <span class="ot">=></span> <span class="dt">Prompt</span> p a <span class="ot">-></span> <span class="dt">ICont</span> m p a
<span class="fu">></span> to' m <span class="fu">=</span> <span class="dt">ICont</span> (\k <span class="ot">-></span> run k m)
<span class="fu">></span>
<span class="fu">></span><span class="ot"> from' ::</span> (forall m<span class="fu">.</span> <span class="kw">Monad</span> m <span class="ot">=></span> <span class="dt">ICont</span> m p a) <span class="ot">-></span> <span class="dt">Prompt</span> p a
<span class="fu">></span> from' m <span class="fu">=</span> unICont m prompt</code></pre>
<p>This suggests an alternative implementation of <code>Prompt</code>:</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">newtype</span> <span class="dt">Prompt'</span> p a <span class="fu">=</span> <span class="dt">P'</span> (forall m<span class="fu">.</span> <span class="kw">Monad</span> m <span class="ot">=></span> (p <span class="fu">:-></span> m) <span class="ot">-></span> m a)</code></pre>
<p><code>ICont</code> is very similar to the generator type discussed in <a href="http://www.cs.indiana.edu/~sabry/papers/yield-pp.pdf">“Lazy v. Yield: Incremental, Linear Pretty-printing”</a> by Oleg Kiselyov, Simon Peyton-Jones, and Amr Sabry:</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">type</span> <span class="dt">GenT</span> e m <span class="fu">=</span> <span class="dt">ReaderT</span> (e <span class="ot">-></span> m ()) m</code></pre>
<p>We can define a simple interface for generators,</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">data</span> <span class="dt">Sink</span> e i <span class="kw">where</span> <span class="dt">Send</span><span class="ot"> ::</span> e <span class="ot">-></span> <span class="dt">Sink</span> e ()</code></pre>
<p>and now <code>ICont m (Sink e)</code> is isomorphic to <code>GenT e m</code>.</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span><span class="ot"> toGen ::</span> <span class="dt">ICont</span> m (<span class="dt">Sink</span> e) <span class="fu">:-></span> <span class="dt">GenT</span> e m
<span class="fu">></span> toGen m <span class="fu">=</span> <span class="dt">ReaderT</span> (\f <span class="ot">-></span> unICont m (\(<span class="dt">Send</span> e) <span class="ot">-></span> f e))
<span class="fu">></span>
<span class="fu">></span><span class="ot"> fromGen ::</span> <span class="dt">GenT</span> e m <span class="fu">:-></span> <span class="dt">ICont</span> m (<span class="dt">Sink</span> e)
<span class="fu">></span> fromGen m <span class="fu">=</span> <span class="dt">ICont</span> (\k <span class="ot">-></span> runReaderT m (k <span class="fu">.</span> <span class="dt">Send</span>))</code></pre>
<p>In their paper, Kiselyov and the others contrast their simple generators with iteratees, noting that the latter effectively require “first-class, multi-shot delimited continuations.” Of course, <code>GenT</code> can’t <em>prevent</em> the use of delimited continuations, unless it fixes the monad <code>m</code>—at which point it is restricted to the effects that <code>m</code> can express.</p>
<p>Similarly, <code>Prompt</code> and <code>Prompt'</code> are polymorphic in their effects, while <code>ICont m</code> is limited to whatever effects <code>m</code> can express. What’s interesting is that it doesn’t really matter which one you choose. If you go back to <code>charRuns</code> and <code>guardStream</code> and replace all the occurrences of <code>prompt</code> with <code>iskip</code>, the result is polymorphic over any <code>IMonad</code>. That’s because the only operations <code>Prompt</code> provides are those in <code>Monad</code> and <code>IMonad</code>—but that’s basically all you need.</p>
<h2 id="interpreters">Interpreters</h2>
<p>A small framework for interpreting stateful effects in <code>Prompt</code>.</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span><span class="ot"> stateful ::</span> (forall i<span class="fu">.</span> p i <span class="ot">-></span> s <span class="ot">-></span> (i,s))
<span class="fu">></span> <span class="ot">-></span> s <span class="ot">-></span> <span class="dt">Prompt</span> p a <span class="ot">-></span> a
<span class="fu">></span> stateful op s m <span class="fu">=</span> unP m (\p k <span class="ot">-></span> <span class="fu">uncurry</span> k <span class="fu">.</span> op p) <span class="fu">const</span> s
<span class="fu">></span>
<span class="fu">></span><span class="ot"> lstateful ::</span> (forall i<span class="fu">.</span> p i <span class="ot">-></span> s <span class="ot">-></span> (i,s))
<span class="fu">></span> <span class="ot">-></span> s <span class="ot">-></span> <span class="dt">Prompt</span> (p <span class="fu">:</span>\<span class="fu">/</span> q) a <span class="ot">-></span> <span class="dt">Prompt</span> q a
<span class="fu">></span> lstateful op s m <span class="fu">=</span> unP m
<span class="fu">></span> ((\p k <span class="ot">-></span> <span class="fu">uncurry</span> k <span class="fu">.</span> op p) \<span class="fu">/</span> pass)
<span class="fu">></span> (\a s <span class="ot">-></span> <span class="fu">return</span> a)
<span class="fu">></span> s
<span class="fu">></span> <span class="kw">where</span>
<span class="fu">></span> pass q k s <span class="fu">=</span> prompt q <span class="fu">>>=</span> <span class="fu">flip</span> k s
<span class="fu">></span>
<span class="fu">></span><span class="ot"> state ::</span> <span class="dt">St</span> s i <span class="ot">-></span> s <span class="ot">-></span> (i,s)
<span class="fu">></span> state <span class="dt">Get</span> s <span class="fu">=</span> (s, s)
<span class="fu">></span> state (<span class="dt">Put</span> s) _ <span class="fu">=</span> ((),s)
<span class="fu">></span>
<span class="fu">></span><span class="ot"> stream ::</span> <span class="dt">Stream</span> e i <span class="ot">-></span> [e] <span class="ot">-></span> (i,[e])
<span class="fu">></span> stream <span class="dt">SRead</span> [] <span class="fu">=</span> (<span class="dt">EOS</span>, [])
<span class="fu">></span> stream <span class="dt">SRead</span> (e<span class="fu">:</span>es) <span class="fu">=</span> (<span class="dt">Chunk</span> e, es)
<span class="fu">></span>
<span class="fu">></span><span class="ot"> gstream ::</span> <span class="dt">GStream</span> e i <span class="ot">-></span> [e] <span class="ot">-></span> (i,[e])
<span class="fu">></span> gstream <span class="dt">GReadAny</span> [] <span class="fu">=</span> (<span class="dt">EOS</span>, [])
<span class="fu">></span> gstream <span class="dt">GReadAny</span> (e<span class="fu">:</span>es) <span class="fu">=</span> (<span class="dt">Chunk</span> e, es)
<span class="fu">></span> gstream (<span class="dt">GReadOnly</span> f) (e<span class="fu">:</span>es) <span class="fu">|</span> f e <span class="fu">=</span> (<span class="kw">Just</span> e, es)
<span class="fu">></span> gstream (<span class="dt">GReadOnly</span> f) es <span class="fu">=</span> (<span class="kw">Nothing</span>, es)</code></pre>
<div class="footnotes">
<hr />
<ol>
<li id="fn1"><p>Proof that <code>pmap t</code> is a monad morphism:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"> pmap t (m <span class="fu">>>=</span> f)
<span class="fu">=</span> <span class="dt">P</span> (\c k <span class="ot">-></span> unP (m <span class="fu">>>=</span> f) (c <span class="fu">.</span> t) k)
<span class="fu">=</span> <span class="dt">P</span> (\c k <span class="ot">-></span> unP m (c <span class="fu">.</span> t) (\a <span class="ot">-></span> unP (f a) (c <span class="fu">.</span> t) k))
pmap t m <span class="fu">>>=</span> pmap t <span class="fu">.</span> f
<span class="fu">=</span> <span class="dt">P</span> (\c k <span class="ot">-></span> unP (pmap t m) c (\a <span class="ot">-></span> unP (pmap t (f a)) c k))
<span class="fu">=</span> <span class="dt">P</span> (\c k <span class="ot">-></span> unP (pmap t m) c (\a <span class="ot">-></span> unP (f a) (c <span class="fu">.</span> t) k))
<span class="fu">=</span> <span class="dt">P</span> (\c k <span class="ot">-></span> unP m (c <span class="fu">.</span> t) (\a <span class="ot">-></span> unP (f a) (c <span class="fu">.</span> t) k))</code></pre>
<a href="http://www.eyrie.org/~zednenem/2013/06/prompt#fnref1">↩</a></li>
<li id="fn2"><p>Also, <em>UP</em> is a comonad in <strong>M</strong>.<a href="http://www.eyrie.org/~zednenem/2013/06/prompt#fnref2">↩</a></p></li>
<li id="fn3"><p>In the real implementation, <code>Chunk</code> also has the capacity to report errors, so it isn’t isomorphic to <code>Maybe</code>.<a href="http://www.eyrie.org/~zednenem/2013/06/prompt#fnref3">↩</a></p></li>
</ol>
</div>
<cite class='self'>ZedneWeb</cite> 2013http://www.eyrie.org/~zednenem/2013/06/redesign2013-06-06T14:19:19-04:002013-06-06T14:19:19-04:00
After ten years, it’s time for a new content manager here at
<cite class='self'>ZedneWeb</cite>. And after 12½ years, it’s time for
a new look. You’ll probably never experience the former, and you can
already see the latter, but here’s a blog post about it anyway.<p>I guess those <a href="http://www.eyrie.org/~zednenem/2013/05/27/cms" title="ZedneWeb: Stop helping me! (2013-05-27)">CMS problems</a> I was having a few days ago lit a fire under me, because I've spent most of the last week furiously re-writing <cite class="self">ZedneWeb</cite>’s content manager and redesigning the look of the site.<sup><a href="http://www.eyrie.org/~zednenem/2013/06/redesign#fn1" class="footnoteRef" id="fnref1">1</a></sup> The latter is still a work in progress, since I don’t have easy access to Windows machines for testing, but I’m pretty pleased with the former.</p>
<h2 id="new-cms">New CMS</h2>
<p>Back in the dark ages of 1996, when I started <cite class="self">ZedneWeb</cite>, every page was hand-coded. Eventually, I wrote a Perl script to manage the blog portion. I‘m not sure when, but the <a href="http://www.eyrie.org/~zednenem/2000/08/23/#reorg" title="ZedneWeb: “I’ve gone the ‘weblog’ route” (2000-08-03)">first reference</a> to it is in August, 2000. In any case, it lasted until June, 2003, when I <a href="http://www.eyrie.org/~zednenem/2003/06/17/cms" title="ZedneWeb: ZedneWeb’s new content manager (2003-06-17)">replaced it</a> with a Python script, which I kept using largely unchanged for almost ten years.</p>
<p>It is really bizarre to look at the old code. It seems so amateurish; I can only hope the professional work I was doing at the time was better.</p>
<p>Once the new code was able to recreate the old site, I started adding features. One that I’ve wanted for a long time is <strong>post topics</strong>. Each post can optionally be associated with one or more topics (you can see them above in the line beginning “Filed under:” and in the navigation section on the bottom), and for each topic there is an index listing all of its posts.</p>
<p>Another cool feature is the <strong><a href="http://www.eyrie.org/~zednenem/feed.atom">full-content syndication feed</a></strong>. I’d only ever provided plain-text descriptions because I’d been using RSS, which is ambiguous about whether its content and description fields contain plain text or encoded HTML. The new feeds use the <a href="http://www.atomenabled.org/">Atom</a> format, which clears that up. So go ahead and change the URL in your feed reader, hypothetical <cite class="self">ZedneWeb</cite> reader who uses one. You won’t be sorry.<sup><a href="http://www.eyrie.org/~zednenem/2013/06/redesign#fn2" class="footnoteRef" id="fnref2">2</a></sup></p>
<p>The last feature I’ve wanted for a long time is <strong>external posts</strong>, which appear in the index but aren’t part of the blog itself. This allows my fiction to appear in the yearly and monthly indices while still being hosted in the <a href="http://www.eyrie.org/~zednenem/library/" title="ZedneWeb: Fiction by Dave Menendez">Library</a>. Closely related are <strong>link posts</strong>, which <em>are</em> part of the blog, but which are intended to link to external pages. I haven’t created any of those yet, and I’m kind of out of the habit of linking to things, but the capacity will be there when I need it.</p>
<p>There’s also some stuff that may hopefully be more useful in the future, like <strong>cover images</strong>. Essentially, I added some code that puts an optional image above the title. <cite class="self">ZedneWeb</cite> doesn’t have a strong history of posting images, but I did go back and reformat this <a href="http://www.eyrie.org/~zednenem/2006/06/26/pip" title="ZedneWeb: Photo: A small bird bathing in my sink (2006-06-26)">photo of Pip taking a shower</a>.</p>
<p>Oh, and just for fun I put <strong>rotating taglines</strong> on the post and index pages. These are selected pseudo-randomly from a list of ten or so, although individual posts can specify their own.</p>
<p><strong>Addendum:</strong> I forgot to mention the new URI structure. The old CMS used a three-level hierarchy for posts, including the year, month, and day in the post URI. The idea was that you could look at a <cite class="self">ZedneWeb</cite> URI and tell the day it was posted and get a hint as to its subject, as in <code>2013/05/27/cms</code>.</p>
<p>As reasonable as that is, <cite class="self">ZedneWeb</cite> doesn’t really see the kind of activity that justifies that much hierarchy. Very few days have more than one post. So the new CMS uses two levels, year and month, for new posts, while preserving the three levels for the older posts. It’s slightly more complicated that way, but it means all of my older posts are still at the same address.</p>
<h2 id="new-design">New design</h2>
<p>Again, I don’t have good records, but I believe the <a href="http://www.eyrie.org/~zednenem/about/archeology/v3/" title="How ZedneWeb looked before 2013-06-06">previous look</a> for <cite class="self">ZedneWeb</cite> was <a href="http://www.eyrie.org/~zednenem/2000/11/03/#update" title="ZedneWeb: “a Zeldman-esque look” (2000-11-03)">adopted</a> in November, 2000. As you can imagine, the state of the art has advanced considerably since then. Sadly, I haven’t kept up with web coding, but things seem to work well enough now that I can use modern CSS tools without worrying <em>too</em> much about cross-browser compatibility.<sup><a href="http://www.eyrie.org/~zednenem/2013/06/redesign#fn3" class="footnoteRef" id="fnref3">3</a></sup></p>
<p>The primary design change is that page body is now about 75 characters across (i.e., <code>75ex</code>) and centered using <code>margin: auto</code>. This will hopefully make the site more readable, by preventing the page text from getting too wide—even on gigantic monitors. The advantage of declaring the width relative to the font size is that the page will get wider if you use a bigger font. (The disadvantage is that I don't really know how to size images. Ideally, I’d like oversized images to still be centered, but I don’t know if that’s possible with CSS alone.)</p>
<p>I’ve also changed the font (Hoefler Text if you have it, Georgia or your default serif otherwise) and un-framed the pages. The result is clean, and (I think) looks pretty nice.</p>
<p>Link colors are back to the defaults. I may adjust that.</p>
<h2 id="the-rest-of-zedneweb">The rest of <cite class="self">ZedneWeb</cite></h2>
<p>Right now, only the blog portion of the site has the new design. Sadly, the rest of the site is pretty old and dusty these days. The <a href="http://www.eyrie.org/~zednenem/library/" title="ZedneWeb: Fiction by Dave Menendez">Library</a> and <a href="http://www.eyrie.org/~zednenem/misc/sites.html" title="ZedneWeb: Sites of interest">links to other sites</a> were last updated in 2003, and my <a href="http://www.eyrie.org/~zednenem/about/dave.html" title="ZedneWeb: About Dave Menendez">bio</a> was apparently last updated in late <em>2001.</em></p>
<p>I’m not sure when I’ll get around to updating these. I guess my bio should be my top priority, since anyone searching for me on the web probably doesn’t want 11½ year old information. I’d also like to get the Library looking nice, although maybe that can wait until I’m actually writing fiction again.<sup><a href="http://www.eyrie.org/~zednenem/2013/06/redesign#fn4" class="footnoteRef" id="fnref4">4</a></sup></p>
<p>Then there’s stuff like the <a href="http://www.eyrie.org/~zednenem/sfstory/">Sfstory</a> information page that never really gelled in the first place. That may be sticking around in its current form for quite a while.</p>
<p>I guess the blog is the most important part of <cite class="self">ZedneWeb</cite> these days (to the extent that any part of <cite class="self">ZedneWeb</cite> can be considered important). It’s certainly the largest, so I guess it’s good that I was able to polish it up.</p>
<div class="footnotes">
<hr />
<ol>
<li id="fn1"><p>For the new millennium, I guess. Since, technically, I <a href="http://www.eyrie.org/~zednenem/2000/11/03/#update" title="ZedneWeb: “a Zeldman-esque look” (2000-11-03)">adopted the old look</a> in the previous one.<a href="http://www.eyrie.org/~zednenem/2013/06/redesign#fnref1">↩</a></p></li>
<li id="fn2"><p>Not a guarantee.<a href="http://www.eyrie.org/~zednenem/2013/06/redesign#fnref2">↩</a></p></li>
<li id="fn3"><p>If you’re using Internet Explorer, feel free to send me screenshots. I’m not too worried about supporting IE 6.0 or earlier, but I’d like to know if these pages are at least readable.<a href="http://www.eyrie.org/~zednenem/2013/06/redesign#fnref3">↩</a></p></li>
<li id="fn4"><p>It could happen! Who says it couldn’t?<a href="http://www.eyrie.org/~zednenem/2013/06/redesign#fnref4">↩</a></p></li>
</ol>
</div>
Stop helping me!http://www.eyrie.org/~zednenem/2013/05/27/cms2013-05-27T22:57:04-04:002013-05-27T22:57:04-04:00When I tried to enter that last post, it crashed my content manager. Turns out, my ancient code was using the wrong kind of string substitution, one which “helpfully” interprets the replacement string. Works fine until you try to post an entry containing the text <code>\g</code>.
<p>Part of the reason that <a href="http://www.eyrie.org/~zednenem/2013/05/27/freeapp" title="ZedneWeb 2013-05-27: Free Applicative Functors in Haskell">last post</a> went up so late at night was that when I finally finished writing it and tried to run it through the <a href="http://www.eyrie.org/~zednenem/2003/06/17/cms" title="ZedneWeb 2003-06-17: ZedneWeb’s new content manager">ancient Python script</a> that “manages” <cite class="self">ZedneWeb</cite>, I suddenly got an uncaught exception.</p>
<p>Keep in mind, I've been using this script since 2003. Before last night, I believe it’s last-modified date was sometime in 2004. Believe me, this was something that had never happened before, because if it had I would have fixed it long ago.</p>
<p>So what happened? It took me a while to track down, since I had to re-familiarize myself with the code, and with Python, but eventually I realized it had to do with the bit that copies the post content into the page template. It’s literally just a search-and-replace<sup><a href="http://www.eyrie.org/~zednenem/2013/05/27/cms#fn1" class="footnoteRef" id="fnref1">1</a></sup>, but the problem is that I implemented it using <code>sre.sub</code>:</p>
<pre><code>result = sre.sub("<#content#>", content, result)</code></pre>
<p>Looks simple, right? Takes a string, replaces any occurrences of <code><#content#></code> with the post content, and uses that as the new string. What could go wrong?</p>
<p>Well, it turns out, Python helpfully interprets the replacement string by looking for backslash escapes. Replacing, e.g., the literal text <code>\n</code> with a newline. More importantly, it looks for group identifiers of the form <code>\g<<var>name</var>></code>, in case you were using a regular expression that defined groups.</p>
<p>This is, quite simply, a bug. One that stood for nearly ten years simply because I had never posted any blog entries containing the string <code>\g</code>. Until last night, when I posted a bunch code written in Haskell, which uses the backslash to introduce anonymous functions. Post some code defining a variable <code>g</code> and <em>boom.</em> Crash city.</p>
<p>From what I can tell, the correct<sup><a href="http://www.eyrie.org/~zednenem/2013/05/27/cms#fn2" class="footnoteRef" id="fnref2">2</a></sup> way to do this would have been to use <code>replace</code>, i.e.,</p>
<pre><code>result = result.replace("<#content#>", content)</code></pre>
<p>I made the changes, ran the new post through, and everything worked out just fine.<sup><a href="http://www.eyrie.org/~zednenem/2013/05/27/cms#fn3" class="footnoteRef" id="fnref3">3</a></sup></p>
<div class="footnotes">
<hr />
<ol>
<li id="fn1"><p>A bunch of web security gurus just winced at the idea of doing string substitution to put content in a template. They needn’t worry: the code only runs locally on content I control, so the only security risk is me. Anyone who could possibly take advantage of that would already have access to my web host, making the point moot.<a href="http://www.eyrie.org/~zednenem/2013/05/27/cms#fnref1">↩</a></p></li>
<li id="fn2"><p>Well, more correct. The <em>actual</em> correct way would be to do something more robust than string replacement.<a href="http://www.eyrie.org/~zednenem/2013/05/27/cms#fnref2">↩</a></p></li>
<li id="fn3"><p>Until I realized I had posted broken links to the images. And there were probably a few other last-minute fixes as well.<a href="http://www.eyrie.org/~zednenem/2013/05/27/cms#fnref3">↩</a></p></li>
</ol>
</div>
Free Applicative Functors in Haskellhttp://www.eyrie.org/~zednenem/2013/05/27/freeapp2013-05-27T01:37:11-04:002013-05-27T01:37:11-04:00Can we find a way to make an applicative functor for any type constructor? It turns out, methods are already known—but I didn’t know that when I started, so I found my own way. One that turns out to have much better performance.<p>A few days ago, I found myself thinking about free monads, specifically <a href="http://hackage.haskell.org/packages/archive/MonadPrompt/1.0.0.3/doc/html/Control-Monad-Prompt.html#t:Prompt" title="MonadPrompt-1.0.0.3: Control.Monad.Prompt.Prompt"><code>Prompt</code> monads</a>, and wondering if there were equivalents for applicative functors. I didn’t realize it at the time, but apparently there was a recent bit of discussion about this in the Haskell community, starting with a <a href="http://web.jaguarpaw.co.uk/~tom/blog/2012/09/09/towards-free-applicatives.html" title="Towards Free Applicatives">blog post by Tom Ellis</a>, and leading to a <a href="http://ro-che.info/articles/2013-03-31-flavours-of-free-applicative-functors.html" title="Flavours of free applicative functors">roundup of implementations</a> by Roman Cheplyaka.</p>
<p>The consensus implementation, at least the one provided by the <a href="http://hackage.haskell.org/packages/archive/free/3.4.1/doc/html/Control-Applicative-Free.html" title="free-3.4.1: Control.Applicative.Free"><code>free</code> package</a>, looks roughly like this:</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="ot">{-# LANGUAGE GADTs, RankNTypes #-}</span>
<span class="fu">></span>
<span class="fu">></span> <span class="kw">module</span> <span class="dt">FreeApp</span> <span class="kw">where</span>
<span class="fu">></span>
<span class="fu">></span> <span class="kw">import</span> <span class="dt">Control.Applicative</span>
<span class="fu">></span>
<span class="fu">></span> <span class="kw">data</span> <span class="dt">Free</span> f a <span class="kw">where</span>
<span class="fu">></span> <span class="dt">Pure</span><span class="ot"> ::</span> a <span class="ot">-></span> <span class="dt">Free</span> f a
<span class="fu">></span> <span class="dt">App</span><span class="ot"> ::</span> f a <span class="ot">-></span> <span class="dt">Free</span> f (a <span class="ot">-></span> b) <span class="ot">-></span> <span class="dt">Free</span> f b
<span class="fu">></span>
<span class="fu">></span><span class="ot"> liftFree ::</span> f a <span class="ot">-></span> <span class="dt">Free</span> f a
<span class="fu">></span> liftFree x <span class="fu">=</span> <span class="dt">App</span> x (<span class="dt">Pure</span> <span class="fu">id</span>)
<span class="fu">></span>
<span class="fu">></span><span class="ot"> lowerFree ::</span> <span class="kw">Applicative</span> f <span class="ot">=></span> <span class="dt">Free</span> f a <span class="ot">-></span> f a
<span class="fu">></span> lowerFree (<span class="dt">Pure</span> x) <span class="fu">=</span> pure x
<span class="fu">></span> lowerFree (<span class="dt">App</span> x xs) <span class="fu">=</span> x <span class="fu"><**></span> lowerFree xs
<span class="fu">></span>
<span class="fu">></span> <span class="kw">instance</span> <span class="kw">Functor</span> (<span class="dt">Free</span> f) <span class="kw">where</span>
<span class="fu">></span> <span class="fu">fmap</span> f (<span class="dt">Pure</span> a) <span class="fu">=</span> <span class="dt">Pure</span> (f a)
<span class="fu">></span> <span class="fu">fmap</span> f (<span class="dt">App</span> x xs) <span class="fu">=</span> <span class="dt">App</span> x (<span class="fu">fmap</span> (f <span class="fu">.</span>) xs)
<span class="fu">></span>
<span class="fu">></span> <span class="kw">instance</span> <span class="kw">Applicative</span> (<span class="dt">Free</span> f) <span class="kw">where</span>
<span class="fu">></span> pure <span class="fu">=</span> <span class="dt">Pure</span>
<span class="fu">></span>
<span class="fu">></span> <span class="dt">Pure</span> f <span class="fu"><*></span> y <span class="fu">=</span> <span class="fu">fmap</span> f y
<span class="fu">></span> <span class="dt">App</span> x xs <span class="fu"><*></span> y <span class="fu">=</span> <span class="dt">App</span> x (<span class="fu">fmap</span> <span class="fu">flip</span> xs <span class="fu"><*></span> y)</code></pre>
<p>Essentially, <code>Free f a</code> consists of a sequence of “effects” (values of type <code>f a</code>, for some <code>a</code>) and a function which combines the results of those effects to produce the final answer.</p>
<p>You can also see that this is going to have bad asymptotic performance. <code>fmap f x</code>, for example, will take time <em>O</em>(<em>n</em>) time, where <em>n</em> is the number of effects in <code>x</code>. Worse, <code>x <*> y</code> will take <em>O</em>(<em>n</em><sup>2</sup> + <em>m</em>) time, since it calls <code>fmap</code> <em>n</em> times on <code>x</code> and once on <code>y</code>.</p>
<h2 id="my-first-implementation">My first implementation</h2>
<p>Of course, I didn’t bother to look for other implementations until after I’d found my own. I think I considered one like <code>Free</code> above, but rejected it because I didn’t like that <code>fmap</code> was so expensive. Instead, I kept the function separate from the effect sequence. To make it easy to call <code>fmap</code> without needing to walk the tree, I made the function accept all the results from the effects in a single argument, represented as a nested tuple.</p>
<p>Here’s the type for the effect sequence:</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">data</span> <span class="dt">CSeq</span> f a <span class="kw">where</span>
<span class="fu">></span> <span class="dt">CNil</span><span class="ot"> ::</span> <span class="dt">CSeq</span> f ()
<span class="fu">></span> <span class="dt">CCons</span><span class="ot"> ::</span> f a <span class="ot">-></span> <span class="dt">CSeq</span> f u <span class="ot">-></span> <span class="dt">CSeq</span> f (a,u)
<span class="fu">></span>
<span class="fu">></span>
<span class="fu">></span><span class="ot"> reduce ::</span> <span class="kw">Applicative</span> f <span class="ot">=></span> <span class="dt">CSeq</span> f u <span class="ot">-></span> f u
<span class="fu">></span> reduce <span class="dt">CNil</span> <span class="fu">=</span> pure ()
<span class="fu">></span> reduce (<span class="dt">CCons</span> x xs) <span class="fu">=</span> (,) <span class="fu"><$></span> x <span class="fu"><*></span> reduce xs</code></pre>
<p>So if we have operations <code>x :: f a</code>, <code>y :: f b</code>, and <code>z :: f c</code>, we can put them in sequence and get <code>CCons x (CCons y (CCons z CNil)) :: Seq f (a,(b,(c,())))</code>.</p>
<p>And here’s the implementation itself:</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">data</span> <span class="dt">C1</span> f a <span class="fu">=</span> forall u<span class="fu">.</span> <span class="dt">C1</span> (u <span class="ot">-></span> a) (<span class="dt">CSeq</span> f u)
<span class="fu">></span>
<span class="fu">></span><span class="ot"> liftC1 ::</span> f a <span class="ot">-></span> <span class="dt">C1</span> f a
<span class="fu">></span> liftC1 a <span class="fu">=</span> <span class="dt">C1</span> <span class="fu">fst</span> (<span class="dt">CCons</span> a <span class="dt">CNil</span>)
<span class="fu">></span>
<span class="fu">></span><span class="ot"> lowerC1 ::</span> <span class="kw">Applicative</span> f <span class="ot">=></span> <span class="dt">C1</span> f a <span class="ot">-></span> f a
<span class="fu">></span> lowerC1 (<span class="dt">C1</span> f x) <span class="fu">=</span> f <span class="fu"><$></span> reduce x
<span class="fu">></span>
<span class="fu">></span> <span class="kw">instance</span> <span class="kw">Functor</span> (<span class="dt">C1</span> f) <span class="kw">where</span>
<span class="fu">></span> <span class="fu">fmap</span> f (<span class="dt">C1</span> u x) <span class="fu">=</span> <span class="dt">C1</span> (f <span class="fu">.</span> u) x
<span class="fu">></span>
<span class="fu">></span> <span class="kw">instance</span> <span class="kw">Applicative</span> (<span class="dt">C1</span> f) <span class="kw">where</span>
<span class="fu">></span> pure a <span class="fu">=</span> <span class="dt">C1</span> (<span class="fu">const</span> a) <span class="dt">CNil</span>
<span class="fu">></span>
<span class="fu">></span> <span class="dt">C1</span> f x <span class="fu"><*></span> <span class="dt">C1</span> g y <span class="fu">=</span> rebaseC1 x <span class="dt">C1</span> (\v u <span class="ot">-></span> f u (g v)) y
<span class="fu">></span>
<span class="fu">></span><span class="ot"> rebaseC1 ::</span> <span class="dt">CSeq</span> f u <span class="ot">-></span> (forall x<span class="fu">.</span> (x <span class="ot">-></span> y) <span class="ot">-></span> <span class="dt">CSeq</span> f x <span class="ot">-></span> z) <span class="ot">-></span>
<span class="fu">></span> (v <span class="ot">-></span> u <span class="ot">-></span> y) <span class="ot">-></span> <span class="dt">CSeq</span> f v <span class="ot">-></span> z
<span class="fu">></span> rebaseC1 <span class="dt">CNil</span> k f <span class="fu">=</span> k (\v <span class="ot">-></span> f v ())
<span class="fu">></span> rebaseC1 (<span class="dt">CCons</span> x xs) k f <span class="fu">=</span>
<span class="fu">></span> rebaseC1 xs (\g s <span class="ot">-></span> k (\(a,u) <span class="ot">-></span> g u a) (<span class="dt">CCons</span> x s))
<span class="fu">></span> (\v u a <span class="ot">-></span> f v (a,u))</code></pre>
<p>(The prefix C, incidentally, stands for “Curry”, because when I was naming it, I got currying and uncurrying confused. <code>C1</code> uses an uncurried function; <code>Free</code> uses a curried one.)</p>
<p>The only real tricky part is <code>rebaseC1</code>. It may not be obvious, but it essentially acts like <code>++</code>, traversing the first sequence and creating a new one by appending the second sequence. The difference is that this also has to modify the return functions and that the return type depends on the input types. I could have used type families here, but for some reason I chose to just stick with existential types; the continuation passed in the second argument is polymorphic in the sequence type, allowing me to just pass <code>C1</code> when I call it.</p>
<p>The real “trick” in <code>rebaseC1</code> involves the <code>y</code> parameter, which changes in the recursive call to allow us to pass values through the later parts of the computation and then reconstruct them. So if the third parameter, <code>f</code> has type <code>v -> (a,u) -> y</code>, in the recursive call it will have type <code>v -> u -> a -> y</code>. The modified continuation will eventually convert the function <code>g :: x -> a -> y</code> into a one with type <code>(a,x) -> y</code> and pass it to the original continuation.</p>
<p>Asymptotically, this is more efficient than <code>Free</code>. All of the operations are <em>O</em>(1), aside from <code>lowerC1</code> and <code><*></code>, which are <em>O</em>(<em>n</em>). It’s pretty clear that <em>O</em>(<em>n</em>) is the best something like <code>lowerC1</code> could be, since it has to evaluate every effect, but can we get a faster <code><*></code>?</p>
<h2 id="my-second-implementation">My second implementation</h2>
<p>Consider that <code><*></code> is essentially appending one sequence to another. In lists, appending works by replacing the final <code>[]</code> of the first list with the second list. That is,</p>
<pre><code>1:2:3:[] ++ 4:5:[] = 1:2:3:4:5:[]</code></pre>
<p>We can speed up append by taking the end of the list as a parameter, allowing us to use <code>[]</code> or another list as we choose. Then appending simply becomes function composition.</p>
<pre><code>(\n -> 1:2:3:n) . (\n -> 4:5:n) = (\n -> 1:2:3:4:5:n)</code></pre>
<p>Finding an analogous trick for <code>C1</code> is harder, obviously, but after a bunch of tweaking, this is what I came up with:</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span> <span class="kw">newtype</span> <span class="dt">C2</span> f a <span class="fu">=</span> <span class="dt">C2</span>
<span class="fu">></span> {<span class="ot"> unC2 ::</span> forall u y z<span class="fu">.</span>
<span class="fu">></span> (forall x<span class="fu">.</span> (x <span class="ot">-></span> y) <span class="ot">-></span> <span class="dt">CSeq</span> f x <span class="ot">-></span> z) <span class="ot">-></span>
<span class="fu">></span> (u <span class="ot">-></span> a <span class="ot">-></span> y) <span class="ot">-></span> <span class="dt">CSeq</span> f u <span class="ot">-></span> z }
<span class="fu">></span>
<span class="fu">></span><span class="ot"> liftC2 ::</span> f a <span class="ot">-></span> <span class="dt">C2</span> f a
<span class="fu">></span> liftC2 a <span class="fu">=</span> <span class="dt">C2</span> (\k f s <span class="ot">-></span> k (\(a,s) <span class="ot">-></span> f s a) (<span class="dt">CCons</span> a s))
<span class="fu">></span>
<span class="fu">></span><span class="ot"> lowerC2 ::</span> <span class="kw">Applicative</span> f <span class="ot">=></span> <span class="dt">C2</span> f a <span class="ot">-></span> f a
<span class="fu">></span> lowerC2 x <span class="fu">=</span> unC2 x (\f s <span class="ot">-></span> f <span class="fu"><$></span> reduce s) (\() <span class="ot">-></span> <span class="fu">id</span>) <span class="dt">CNil</span>
<span class="fu">></span>
<span class="fu">></span> <span class="kw">instance</span> <span class="kw">Functor</span> (<span class="dt">C2</span> f) <span class="kw">where</span>
<span class="fu">></span> <span class="fu">fmap</span> g x <span class="fu">=</span> <span class="dt">C2</span> (\k f <span class="ot">-></span> unC2 x k (\s <span class="ot">-></span> f s <span class="fu">.</span> g))
<span class="fu">></span>
<span class="fu">></span> <span class="kw">instance</span> <span class="kw">Applicative</span> (<span class="dt">C2</span> f) <span class="kw">where</span>
<span class="fu">></span> pure a <span class="fu">=</span> <span class="dt">C2</span> (\k f <span class="ot">-></span> k (<span class="fu">flip</span> f a))
<span class="fu">></span>
<span class="fu">></span> x <span class="fu"><*></span> y <span class="fu">=</span> <span class="dt">C2</span> (\k f <span class="ot">-></span> unC2 y (unC2 x k) (\s a g <span class="ot">-></span> f s (g a)))</code></pre>
<p>Now, all operations are <em>O</em>(1) except <code>lowerC2</code>.</p>
<p>As a quick explanation, <code>x :: C2 f a</code> is a function taking three arguments. The first is a continuation (of the same type used in <code>reduceC1</code>) saying what to do with the final effect sequence and function. The third is the tail of the effect sequence, that <code>x</code> can add to using <code>CCons</code>. The second is a function which explains how to take the results of the tail effects and the value produced by <code>x</code> and combine them into the final return value. You can look at <code>liftC2</code> and <code>pure</code> to see how they use them.</p>
<p><code><*></code> uses the same trick as <code>rebaseC1</code> of being sneaky with the <code>y</code> type parameter, allowing us to pass an extra value from <code>x</code> to <code>y</code>. That’s also why the function doesn’t have the seemingly more logical argument order <code>a -> u -> v</code>.</p>
<p>Notice in <code><*></code> that the first argument is put into the continuation of the second one. This is the secret to <code>C2</code>’s speed: it essentially traverses the expression tree from right to left, building the sequence of events from last to first. Unlike <code>Free</code> or <code>C1</code>, <code>C2</code> never has to traverse and reconstruct the effect sequence.</p>
<p>Naturally, <code>C1</code> and <code>C2</code> are easily interconvertible:</p>
<pre class="sourceCode literate haskell"><code class="sourceCode haskell"><span class="fu">></span><span class="ot"> c2toC1 ::</span> <span class="dt">C2</span> f a <span class="ot">-></span> <span class="dt">C1</span> f a
<span class="fu">></span> c2toC1 x <span class="fu">=</span> unC2 x <span class="dt">C1</span> (\() a <span class="ot">-></span> a) <span class="dt">CNil</span>
<span class="fu">></span>
<span class="fu">></span><span class="ot"> c1toC2 ::</span> <span class="dt">C1</span> f a <span class="ot">-></span> <span class="dt">C2</span> f a
<span class="fu">></span> c1toC2 (<span class="dt">C1</span> g x) <span class="fu">=</span> <span class="dt">C2</span> (\k f <span class="ot">-></span> rebaseC1 x k (\v u <span class="ot">-></span> f v (g u)))</code></pre>
<h2 id="testing-for-speed">Testing for speed</h2>
<p>I’ve talked a bit about asymptotic performance, but that isn’t the end of the story with efficiency. <code>C1</code> and <code>C2</code> do a bit work converting functions between curried and uncurried forms, so we should do some experiments to see whether they’re actually any better.</p>
<p>Here’s one. I generated a balanced binary tree containing between 10 and 100 nodes, each of which is a trivial call to <code>liftX</code>, used <code>sequenceA</code> to traverse the tree, and then used <code>lowerX</code> to run the computation. I then used <a href="http://hackage.haskell.org/package/criterion-0.8.0.0" title="The criterion package">Criterion</a> to tell me how long they took. The result was that <code>C2</code> was easily faster than <code>C1</code>, which was much faster than <code>Free</code>.</p>
<img src="http://www.eyrie.org/~zednenem/2013/files/tree.png" alt="Chart showing times to traverse a tree with n nodes" height="400" width="600">
<p>Other experiments are more stark. For example, expressions of the form</p>
<pre><code>f <$> lift () <*> lift () <*> lift () …</code></pre>
<p>are something of a worst case for <code>Free</code> and <code>C1</code>, particularly as the number of arguments rose. In my experiments, the time for <code>Free</code> went from 0.58 μs to 14 μs as the number of arguments rose from 3 to 11. <code>C2</code>, in contrast, rose only from 0.049 μs to 0.16 μs.</p>
<img src="http://www.eyrie.org/~zednenem/2013/files/nary.png" alt="Chart showing times for applying a function to n arguments" height="400" width="600">
<p>Obviously, this experiment is artificial, but its results hold up in the tree traversal experiment.</p>
<p>The funny thing is, if I had started my exploration by looking for other implementations, I might have found the existing ones and stopped, my curiosity satisfied. Because I was (re)inventing the concept for myself, I pushed harder to find the best one I could.<sup><a href="http://www.eyrie.org/~zednenem/2013/05/27/freeapp#fn1" class="footnoteRef" id="fnref1">1</a></sup> The results are a significant improvement over the current state of the art.</p>
<p>It may be that no one will ever need a free applicative functor. It certainly may be that no one will need the speed improvement of <code>C2</code> over <code>Free</code>. We’ve still learned two lessons here: don’t append when you can compose, and don’t use curried functions if you’re going to compose them.</p>
<div class="footnotes">
<hr />
<ol>
<li id="fn1"><p>I'm omitting, in fact, four implementations I came up with that use a curried function—in fact, <code>C1</code> and <code>C2</code> were renamed to contrast with them. When I finally pulled out Criterion, I saw that they could beat <code>Free</code>, but <code>C2</code> was better than all of them. Since they’re also more complicated, it didn’t seem worth it to mention them.<a href="http://www.eyrie.org/~zednenem/2013/05/27/freeapp#fnref1">↩</a></p></li>
</ol>
</div>
Parameterized monads vs monads over indexed typeshttp://www.eyrie.org/~zednenem/2012/07/29/paramonads2012-07-29T02:25:45-04:002012-07-29T02:25:45-04:00Parameterized monads are a known way of extending the monadic interface. As an alternative, Conor McBride suggested using monads over indexed types. How do these approaches compare?<p>I’ve been meaning to write about this for a while, but I kept getting stuck trying to introduce the topic. So instead, I’ll just jump into it and refer people to the original paper for more detail. (If you’ve already read McBride’s “Kleisli arrows of outrageous fortune”, you may want to skip to the <a href="http://www.eyrie.org/~zednenem/2012/07/29/paramonads#ip">new stuff</a> towards the end.)</p>
<h2>Paramonads</h2>
<p>One abstraction that’s been floating around the Haskell community for a while is the parameterized monad—or “paramonad”, as I like to call it. Dan Piponi has a <a href="http://blog.sigfpe.com/2009/02/beyond-monads.html" title="A Neighborhood of Infinity: Beyond Monads">good brief introduction</a> to them, but the general idea is that paramonads extend the familiar monad abstraction by adding a type-level index which can change over the course of a computation.</p>
<p>Here’s a class definition:</p>
<pre><code>class Paramonad m where
preturn :: a -> m i i a
pbind :: (a -> m j k b) -> m i j a -> m i k b
</code></pre>
<p>Here, <code>x :: m i j a</code> is a computation that returns a value of type <code>a</code> but also contains a transition from <code>i</code> to <code>j</code>. The nature of the transition depends on the specific paramonad. For <a href="http://okmij.org/ftp/Computation/monads.html#param-monad">state transformers</a>, it indicates the type of the internal state:</p>
<pre><code>newtype PState i j a = PState (i -> (a,j))
</code></pre>
<p>For <a href="http://okmij.org/ftp/continuations/implementations.html#genuine-shift">delimited continuations</a>, it indicates the return type:</p>
<pre><code>newtype PCont i j a = PCont ((a -> j) -> i)
</code></pre>
<p>But the state may be entirely abstract: one can define a paramonad which <a href="http://okmij.org/ftp/Haskell/regions.html#light-weight" title="Lightweight monadic regions (see section 6)">keeps track of allocated resources</a> in its type. In this way, the programmer can statically guarantee that all allocated resources are eventually de-allocated, and that no attempt is made to access a de-allocated resource.</p>
<p>For simplicity, imagine that we only want to work with one resource—say, a file—at a time. We’ll define some types to indicate whether a file is open:</p>
<pre><code>data Open
data Closed
</code></pre>
<p>Here are the types of our basic operations:</p>
<pre><code>open :: FilePath -> FH Closed Open ()
read :: FH Open Open (Maybe Char)
close :: FH Open Closed ()
</code></pre>
<p>The type of <code>read</code> indicates that it has to come between <code>open</code> and <code>close</code>. Similarly, we can use the type of our run function to ensure that all open files are eventually closed:</p>
<pre><code>run :: FH Closed Closed a -> IO a
</code></pre>
<p>Now, bad programs such as <code>run (open "Foo")</code> and <code>run read</code> are rejected during compilation.</p>
<h2>Adding dynamism</h2>
<p>The problem with the scheme given above is that it’s too static. Some resource allocations may fail—for example, the file might not exist—but the interface given above can’t handle that. We might try exceptions, but there isn’t any good way to handle them inside the paramonad—especially once we start dealing with more complex states involving multiple resources.</p>
<p>One possibility is to remake <code>open</code> to require a continuations for handling successful and unsuccessful allocation:</p>
<pre><code>open :: FilePath
-> FilePath Closed i a -- on failure
-> FilePath Open i a -- on success
-> FilePath Closed i a
</code></pre>
<p>Again, this becomes unweildy once we start to work with multiple resources.</p>
<p>Fortunately, Conor McBride has come up with an alternative, which he describes in his paper <a href="https://personal.cis.strath.ac.uk/conor.mcbride/Kleisli.pdf">“Kleisli Arrows of outrageous fortune”</a>. Instead of defining a variation on monads, McBride shifts attention to the category of indexed-types and index-preserving functions.</p>
<pre><code>type p :-> q = forall i. p i -> q i
</code></pre>
<p>A simple example of an indexed type would be lists which indicate their length in their type—so <code>List a n</code> is a list with <code>n</code> elements. These can be defined using the <code>GADTs</code> extension to Haskell. A function which reverses the elements of a list without changing the length is index-preserving.</p>
<p>Because the monad abstraction isn’t tied to any particular category, we can define a class for monads over index-preserving functions.</p>
<pre><code>class IMonad m where
iskip :: p :-> m p
iextend :: (p :-> m q) -> (m p :-> m q)
</code></pre>
<p>Compare that to the familiar <code>Monad</code> class. Aside from names and the order of arguments, the only difference is the choice of category.</p>
<p>McBride also defines a more familiar-looking synonym:</p>
<pre><code>(?>=) :: IMonad m => m p i -> (p :-> m q) -> m q i
m ?>= f = iextend f m
</code></pre>
<p>We can view the indexed types, such as <code>p</code> and <code>m q</code>, as making claims about the index. So a value of type <code>p i</code> indicates that claim <code>p</code> is possible in state <code>i</code>, and a function <code>f :: p :-> m q</code> says that <code>m q</code> is true when <code>p</code> is true. Similarly, the monads can indicate transitions in the index. In other words, <code>x :: m p i</code> says that <code>m p</code> is possible in state <code>i</code>, but claim <code>p</code> might be about some other state. That’s why the first argument to <code>iextend</code> has to be defined for all possible indicies.</p>
<p>The strongest claim is that the index is some specific value. The type <code>a := i</code> provides a value of type <code>a</code> and a claim that the current index is <code>i</code>.</p>
<pre><code>data (a := i) j where
V :: a -> (a := i) i
</code></pre>
<p>Now we can define some more restricted versions of <code>iskip</code> and <code>iextend</code>:</p>
<pre><code>ireturn :: IMonad m => a -> m (a := i) i
ireturn = iskip . V
(=>=) :: IMonad m => m (a := j) i -> (a -> m p j) -> m p i
m =>= f = m ?>= \(V a) -> f a
</code></pre>
<p>A value <code>x :: m (a := j) i</code> is a computation that produces a value of type <code>a</code> and changes the index from <code>i</code> to <code>j</code>.</p>
<p>Now, we can describe that <code>open</code> can either succeed or fail. First, a type to indicate choice:</p>
<pre><code>data (p :\/ q) i = L (p i) | R (q i)
</code></pre>
<p>Then, the operations over our monad <code>FH</code>:</p>
<pre><code>open :: FilePath -> FH (() := Closed :\/ () := Open) Closed
read :: FH (Maybe Char := Open) Open
close :: FH (() := Closed) Open
</code></pre>
<p>Now it’s clear that <code>open</code> may result in one of two possible states: either the file is open or not. Furthermore, the type system will only allow us to call <code>read</code> and <code>close</code> if <code>open</code> succeeds.</p>
<p>In short, this will typecheck:</p>
<pre><code>ex_good :: FH (Maybe Char := Closed) Closed
ex_good = open "Foo" ?>= \x ->
case x of
L (V ()) -> ireturn Nothing
R (V ()) -> read =>= \c -> close =>= \() -> ireturn c
</code></pre>
<p>This will not:</p>
<pre><code>ex_bad :: FH (Maybe Char := Closed) Closed
ex_bad = open "Foo" ?>= \_ -> read =>= \c -> close =>= \() -> ireturn c
</code></pre>
<p>At this point, it might not seem as we’ve gained much. Instead of writing,</p>
<pre><code>open file on_failure on_success
</code></pre>
<p>we write</p>
<pre><code>open file ?>= \x -> case x of
L (V _) -> on_failure
R (V _) -> on_success
</code></pre>
<p>But the fact that <code>:\/</code> is just another indexed type allows us to work more within our framework. For example, if we have a convention that <code>L</code> is used for failure, we can create a general recovery form:</p>
<pre><code>orElse :: m (() := j :\/ q) i -> m (p :\/ q) j -> m (p :\/ q) i
m1 `orElse` m2 = m1 ?>= \x ->
case x of
L (V _) -> m2
R q -> iskip q
</code></pre>
<p>Now we can write things like this:</p>
<pre><code>open file1 `orElse` open file2 ?>= \x -> case x of
L (V _) -> on_failure
R (V _) -> on_success
</code></pre>
<p>Doing this with the continuation-based <code>open</code> is possible, but it gets complicated very fast.</p>
<h2 id="ip">Back to paramonads</h2>
<p>I mentioned that <code>x :: m (a := i) j</code> is a computation that produces an <code>a</code> and changes the index from <code>i</code> to <code>j</code>. This sounds an awful lot like what a paramonadic computation does, and in fact we can map any instance of <code>IMonad</code> to an instance of <code>Paramonad</code>.</p>
<pre><code>newtype PI m i j a = PI (m (a := j) i)
unPI (PI m) = m
instance IMonad m => Paramonad (PI m) where
preturn = PI . ireturn
pbind m f = PI (unPI m =>= unPI . f)
</code></pre>
<p>This suggests that <code>IMonad</code> is at least as powerful as <code>Paramonad</code>.</p>
<p>We’ve already shown that one of the standard uses for paramonads can be expressed using <code>IMonad</code>, but what about state transforming and continuations?</p>
<p>For state, the index of the computation will determine the input state, and the index of the result will determine the output state. But since the result may have an arbitrary index, we will need an existential type.</p>
<pre><code>data Dyn p = forall i. Dyn (p i) i
newtype State p i = State (i -> Dyn p)
unState (State f) = f
instance IMonad State where
iskip p = State (\i -> Dyn p i)
iextend f m = State (\i ->
case unState m i of
Dyn p j -> unState (f p) j)
</code></pre>
<p>For continuations, the result determines the intermediate return type.</p>
<pre><code>newtype Cont p i = Cont ((forall j. p j -> j) -> i)
unCont (Cont f) = f
instance IMonad Cont where
iskip p = Cont (\k -> k p)
iextend f m = Cont (\k -> unCont m (\p -> unCont (f p) k))
</code></pre>
<p>It’s worth convincing yourself that <code>PI Cont</code> is essentially the same as <code>PCont</code> from above. In particular, for <code>Cont (a := k) i</code>, the continuation will have the type <code>forall j. (a := k) j -> k</code>; but since <code>(a := k) j</code> can only have values when <code>k</code> equals <code>j</code>, we can easily transform a function <code>f :: a -> k</code> into the function <code>(\(V a) -> f a) :: forall j. (a := k) j -> j</code>.</p>
<p>We can generalize further, incidentally, by adding another indexed type:</p>
<pre><code>newtype ICont q p i = ICont ((p :-> q) -> q i)
newtype Id a = Id a
</code></pre>
<p>Now, <code>Cont p i</code> is isomorphic to <code>ICont Id p i</code>.</p>
<p>A similar generalization is possible for <code>State</code>.</p>
<p>Now that all of our paramonad examples turn out to be expressible as monads over indexed types, it’s worth considering whether <em>every</em> paramonad can be mapped to <code>IMonad</code>. For a long time, I was convinced this was impossible, because paramonads require the index transitions be known statically, but monads over indexed types allow dynamic transitions. But it turns out that such a construction is possible after all:</p>
<pre><code>newtype IP m p i = IP (forall k z. (forall j. p j -> m j k z) -> m i k z)
unIP (IP f) = f
instance Paramonad m => IMonad (IP m) where
iskip p = IP (\k -> k p)
iextend f m = IP (unIP m (\p -> unIP (f p) k))
liftP :: Paramonad m => m i j a -> IP m (a := j) i
liftP m = IP (\k -> m `pbind` k . V)
</code></pre>
<p>Since <code>pbind</code> requires the index transition to be known statically, it can’t be in <code>iextend</code>. Instead, we use <code>iextend</code> to build up a continuation, and then call <code>pbind</code> in <code>liftP</code>, where the transition <em>is</em> known statically.</p>
<p>Even better, we can translate the higher-order operations needed to handle dynamic transitions into simple dynamic computations:</p>
<pre><code>liftBranch :: Paramonad m =>
(forall l z. (a -> m j l z) -> (b -> m k l z) -> m i l z)
-> IP m (a := j :\/ b := k) i
liftBranch branch = IP (\k -> branch (k . L . V) (k . R . V))
</code></pre>
<h2>So which is better?</h2>
<p>So now we’ve seen that <code>Paramonad</code> and <code>IMonad</code> are essentially equally powerful: whereever one can be used, the other can be transformed into it. So is one preferable? I’m not sure. On the one hand, paramonads are a new concept without much theoretical basis at this point, whereas <code>IMonad</code>s are just monads in a context we haven’t seen before. On the other hand, <code>(?>=)</code> is hard to use: you need to use GADTs at some level to do anything useful with it, and it’s not always obvious where you need to put type signatures so that GHC can figure out what you’re doing.</p>
<p>Furthermore, instances of <code>Monad</code> are not just monads but <em>strong</em> monads. This strength turns out to be essential for making monads easy to work with; almost all the utility functions in <code>Control.Monad</code> require strength. The obvious definition for a strength for monads over indexed types would probably look like this:</p>
<pre><code>data (p :*: q) i = p i :*: q i
strength :: (p :*: m q) :-> m (p :*: q)
</code></pre>
<p>but this can only work if <code>m</code> never involves an index transition. (That is, <code>p</code> starts out having the initial index and ends up having the final index.)</p>
<p>Aside from illustrating the difference between strong and non-strong monads (something I had never appreciated before), this unforunately limits the utility of <code>IMonad</code>. (For example, <code>IMonad</code> cannot be made an instance of a hypothetical <code>IArrow</code> class, because there’s no way to define <code>first</code>.)</p>
<p>McBride gets around this by defining analogues to <code>ap</code> and other functions in the case where the transitions are known statically:</p>
<pre><code>ap :: IMonad m => m ((a -> b) := j) i -> m (a := k) j -> m (b := k) i
m1 `ap` m2 = m1 =>= \f -> m2 =>= \x -> ireturn (f x)
</code></pre>
<p>But, as we saw before, this is essentially limiting ourselves to what we can do with <code>Paramonad</code>.</p>
<p>Even with that limitation, I think the ability to handle dynamic transitions makes <code>IMonad</code> more useful than <code>Paramonad</code>. But that leaves the question of whether <em>either</em> of them is useful. Are there any interesting algorithms that operate over any instance of <code>IMonad</code> or <code>Paramonad</code>? Yes, it’s possible to define analogues to <code>mapM</code> or <code>traverse</code>, but they don’t allow for index transitions.</p>
<pre><code>imapM :: IMonad m => (a -> m (b := i) i) -> [a] -> m ([b] := i) i
imapM f [] = ireturn []
imapM f (x:xs) = f x =>= \b -> imapM f xs =>= \bs -> ireturn (b:bs)
</code></pre>
<p>Without index transitions, <code>IMonad</code> and <code>Paramonad</code> are no more powerful than <code>Monad</code>. I don’t have an answer here; I think <code>IMonad</code> is interesting and deserves further study, but it’s not yet clear that its advantages outweigh its complexity for practical programming.</p>
Ronald C. Menendez, 1949–2010http://www.eyrie.org/~zednenem/2010/08/17/obit2010-08-17T17:43:50-04:002010-08-17T17:43:50-04:00Ronald C. Menendez, of Chatham, New Jersey, passed away peacefully on Wednesday evening, August 11, 2010.
<p>Ronald C. Menendez, of Chatham, New Jersey, passed away peacefully on Wednesday evening, August 11, 2010.</p>
<p>Ron is survived by his wife Catherine, son David, daughter Ellen (Bob Schell), and grand-daughters Hannah and Kate, all of Chatham, NJ; his mother Carmela, sister Joanne (Gina), brother Rick and Aunt Kay of St Louis, MO. Son of the late Manuel Menendez, beloved nephew, cousin, uncle, brother-in-law; mentor, colleague and friend to many.</p>
<p>Ron received his Bachelor’s in physics from Washington University in St Louis and his Master’s and Doctoral degrees in electrical engineering from the University of Illinois - Urbana. He was a research scientist for 33 years at Telcordia, formerly Bell Labs, most recently working in fiber-optic telecommunications. </p>
<p>He was a long-time and active member of the Unitarian Church in Summit, serving for many years as a youth advisor and teacher. He served on the Board of Trustees, several ministerial search committees and various fundraising endeavors.</p>
<p>A private internment has been held. There will be a memorial service on Sat. August 28 at 1pm at <a href="http://www.ucsummit.org/">The Unitarian Church in Summit, NJ</a>. A second memorial service will be held on Sat., September 18 at 1pm at <a href="http://www.saintmarks-stl.org/">St Mark’s Episcopal Church in St Louis, MO</a>. In lieu of flowers, donations can be made to the <a href="http://www.uusc.org/">Unitarian Universalist Service Committee</a>.</p>
So that was 2008http://www.eyrie.org/~zednenem/2008/12/31/20082008-12-31T17:49:56-05:002008-12-31T17:49:56-05:00What a year this has been. Despite the silence at <cite class='self'>ZedneWeb</cite>, America elected a new president and I got a new niece.<p>What a year this has been. Admittedly, it hasn't been a particularly prolific year on my part—although my <a href="http://twitter.com/zednenem">Twitter account</a> has seen more activity—but this post brings the year’s total to five, which is a 25% improvement over last year. Maybe I really should do that episode-by-episode commentary on <a href="http://www.eyrie.org/~zednenem/library/sa/" title="Episode list"><cite>Starcruiser Anonymous</cite></a> I’ve been <a href="http://www.eyrie.org/~zednenem/2006/07/24/sa" title="ZedneWeb 2006-07-24: Ten years of Starcruiser Anonymous">thinking about</a>. That’s twenty-six posts right there.</p>
<p>Thinking about the past year, two events stick out in my mind. The first is the election of Barack Obama as President of the United States of America. You probably don’t need me to explain why that’s important. Aside from the historic nature of the first black president, I’m hoping for an end to the lawlessness and corruption of the Bush administration. I don’t expect Obama to wave a wand and get our troops out of Iraq, but I hope we’re near the end of torture as government policy and the legal black hole of Guantánamo Bay. (I’m less hopeful that Obama will repudiate Bush’s illegal wiretapping, much less prosecute anyone for war crimes, but you never know.)</p>
<p>The other event is the birth of my niece, Hannah Marie Schell, back in May. I’m not really a baby person, but Hannah and I get along just fine. I’ll hopefully have more to say about her as she gets older and starts talking, but for now I’m content to exchange smiles.</p>
<p>Here’s hoping 2009 brings good fortune.</p>