<commit_before><!doctype html>
<html lang="en">
    <head>
        <meta charset="utf-8">
        <meta http-equiv="x-ua-compatible" content="ie=edge">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <title>Moving Towards Dialogue - Vaibhav Sagar</title>
        <link rel="stylesheet" type="text/css" href="../../css/default.css" />
        <link rel="stylesheet" type="text/css" href="../../css/syntax.css" />
        <script>
          (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
          (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
          m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
          })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');

          ga('create', 'UA-79891461-1', 'auto');
          ga('send', 'pageview');

        </script>
    </head>
    <body>
        <div id="header">
            <div id="logo">
                <a href="../../">Vaibhav Sagar</a>
            </div>
            <div id="navigation">
                <a href="../../about/">About</a>
                <a href="../../talks/">Talks</a>
                <a href="../../archive/">Archive</a>
            </div>
        </div>

        <div id="content">
            <h1>Moving Towards Dialogue</h1>

            <div class="info">
    Posted on 25 September 2018
    
</div>
<div class="info">
    
        Tags: <a href="../../blog/tags/programming/">programming</a>, <a href="../../blog/tags/haskell/">haskell</a>
    
</div>

<p><em>This blog post is essentially a transcript of <a href="https://www.youtube.com/watch?v=0oo8wIi2qBE">a 10-minute talk I gave at !!Con</a>, the slides for which are available <a href="https://vaibhavsagar.com/presentations/typed-holes/">here</a>.</em></p>
<p>Let’s talk about typed holes. What’s a typed hole? A definition I like is <em>“a placeholder for an expression with a known type and an unknown value”</em>.</p>
<p>Why are typed holes useful? Because they allow the language to help us write programs! To demonstrate, let’s look at some code in Python, a language that lacks this feature.</p>
<p>Suppose I want to write a function that takes another function and a list and applies the function to each element of that list. A first stab might look like this:</p>
<div class="sourceCode" id="cb1"><pre class="sourceCode python"><code class="sourceCode python"><a class="sourceLine" id="cb1-1" data-line-number="1"><span class="op">&gt;&gt;&gt;</span> <span class="kw">def</span> <span class="bu">map</span>(f, ls): <span class="cf">return</span> []</a></code></pre></div>
<p>This is obviously wrong: this function ignores its arguments and gives us an empty list each time. This is no good, but what’s worse is that Python will accept this definition without complaint. It doesn’t seem to know (or care).</p>
<p>Let’s try again. I hear the way to do things with lists in Python is to use a list comprehension, so I make sure to use one of those this time:</p>
<div class="sourceCode" id="cb2"><pre class="sourceCode python"><code class="sourceCode python"><a class="sourceLine" id="cb2-1" data-line-number="1"><span class="op">&gt;&gt;&gt;</span> <span class="kw">def</span> <span class="bu">map</span>(f, ls): [f(e) <span class="cf">for</span> e <span class="kw">in</span> ls]</a>
<a class="sourceLine" id="cb2-2" data-line-number="2">...</a>
<a class="sourceLine" id="cb2-3" data-line-number="3"><span class="op">&gt;&gt;&gt;</span> plusOne <span class="op">=</span> <span class="kw">lambda</span> i: i <span class="op">+</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb2-4" data-line-number="4"><span class="op">&gt;&gt;&gt;</span> <span class="bu">print</span>(<span class="bu">map</span>(plusOne, [<span class="dv">1</span>, <span class="dv">2</span>, <span class="dv">3</span>]))</a>
<a class="sourceLine" id="cb2-5" data-line-number="5"><span class="va">None</span></a></code></pre></div>
<p>But this definition is still wrong, because I forgot to put a <code>return</code> statement in! Again, Python will happily accept this.</p>
<p>I’m getting a bit frustrated at this point, so I look at how <code>map</code> is actually implemented. It uses a generator comprehension instead of a list comprehension, which makes it more general somehow, so I make sure to use that, and I remember to put a <code>return</code> statement in this time:</p>
<div class="sourceCode" id="cb3"><pre class="sourceCode python"><code class="sourceCode python"><a class="sourceLine" id="cb3-1" data-line-number="1"><span class="op">&gt;&gt;&gt;</span> <span class="kw">def</span> <span class="bu">map</span>(f, ls): <span class="cf">return</span> (f(e) <span class="cf">for</span> e <span class="kw">in</span> ls)</a>
<a class="sourceLine" id="cb3-2" data-line-number="2">...</a>
<a class="sourceLine" id="cb3-3" data-line-number="3"><span class="op">&gt;&gt;&gt;</span> <span class="bu">print</span>(<span class="bu">map</span>(plusOne, [<span class="dv">1</span>, <span class="dv">2</span>, <span class="dv">3</span>]))</a>
<a class="sourceLine" id="cb3-4" data-line-number="4"><span class="op">&lt;</span>generator <span class="bu">object</span> <span class="bu">map</span>.<span class="op">&lt;</span><span class="bu">locals</span><span class="op">&gt;</span>.<span class="op">&lt;</span>genexpr<span class="op">&gt;</span> at <span class="bn">0x7ffb92103ca8</span><span class="op">&gt;</span></a></code></pre></div>
<p>And now instead of giving me something useful, this function gives me an address in memory, which seems especially pointless.</p>
<p>I give up. This example seems contrived, but over the course of my relationship with Python, which is more than a decade long now, I’ve seen the same dynamic play out embarrassingly many times. How do I write programs that work? Surely this is a simple question with a straightforward answer.</p>
<p>Indeed, the most common response I get when I ask this question is to write tests. That sounds reasonable, so let’s do that:</p>
<div class="sourceCode" id="cb4"><pre class="sourceCode python"><code class="sourceCode python"><a class="sourceLine" id="cb4-1" data-line-number="1"><span class="op">&gt;&gt;&gt;</span> <span class="kw">def</span> <span class="bu">map</span>(f, ls):</a>
<a class="sourceLine" id="cb4-2" data-line-number="2">...     <span class="bu">print</span>(<span class="st">&quot;Where are your tests now?&quot;</span>)</a>
<a class="sourceLine" id="cb4-3" data-line-number="3">...     <span class="cf">return</span> [<span class="dv">2</span>, <span class="dv">3</span>, <span class="dv">4</span>]</a>
<a class="sourceLine" id="cb4-4" data-line-number="4">...</a>
<a class="sourceLine" id="cb4-5" data-line-number="5"><span class="op">&gt;&gt;&gt;</span> <span class="bu">map</span>(plusOne, [<span class="dv">1</span>, <span class="dv">2</span>, <span class="dv">3</span>]) <span class="op">==</span> [<span class="dv">2</span>, <span class="dv">3</span>, <span class="dv">4</span>]</a>
<a class="sourceLine" id="cb4-6" data-line-number="6">Where are your tests now?</a>
<a class="sourceLine" id="cb4-7" data-line-number="7"><span class="va">True</span></a></code></pre></div>
<p>Okay, my test passes, so everything must be good, right?</p>
<p>I contend that tests are necessary, but not sufficient. They are problematic for at least two reasons:</p>
<ol type="1">
<li>They are only as good as the specification they imply for how a program should behave. If that specification is incomplete or wrong, no amount of tests will guarantee software that works.</li>
<li>The language doesn’t understand tests, by which I mean that it’s extremely difficult to automatically go from a failing test to the part of the code where the error lives. The programmer has to do the legwork of tracking down the bug based on essentially one bit of information in many cases.</li>
</ol>
<p>Fortunately, tests aren’t the only specification of how a program should behave. Types can also serve as specifications, and they have the advantage that they are extremely well integrated into the language in a way tests usually are not.</p>
<p>What does this mean in practice? Let’s look at Haskell. Haskell is statically typed, which means it expects to know the types of all the expressions in your program at compile time. This is nothing special though, lots of other languages also claim to be statically typed. What is special about Haskell though is that it has type inference, which means that you don’t have to annotate expressions with their types most of the time because the compiler can figure it out. If you put these two features together, you get typed holes!</p>
<p>Let’s try to write that same program in Haskell with typed holes. To start, let’s create a file called <code>Main.hs</code> with the following contents:</p>
<div class="sourceCode" id="cb5"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb5-1" data-line-number="1"><span class="kw">import</span> <span class="dt">Prelude</span> <span class="kw">hiding</span> (map)</a>
<a class="sourceLine" id="cb5-2" data-line-number="2"></a>
<a class="sourceLine" id="cb5-3" data-line-number="3">map<span class="ot"> ::</span> (a <span class="ot">-&gt;</span> b) <span class="ot">-&gt;</span> [a] <span class="ot">-&gt;</span> [b]</a>
<a class="sourceLine" id="cb5-4" data-line-number="4">map f ls <span class="fu">=</span> _</a>
<a class="sourceLine" id="cb5-5" data-line-number="5"></a>
<a class="sourceLine" id="cb5-6" data-line-number="6"><span class="ot">plusOne ::</span> <span class="dt">Int</span> <span class="ot">-&gt;</span> <span class="dt">Int</span></a>
<a class="sourceLine" id="cb5-7" data-line-number="7">plusOne i <span class="fu">=</span> i <span class="fu">+</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb5-8" data-line-number="8"></a>
<a class="sourceLine" id="cb5-9" data-line-number="9"><span class="ot">main ::</span> <span class="dt">IO</span> ()</a>
<a class="sourceLine" id="cb5-10" data-line-number="10">main <span class="fu">=</span> print ((map plusOne [<span class="dv">1</span>, <span class="dv">2</span>, <span class="dv">3</span>]) <span class="fu">==</span> [<span class="dv">2</span>, <span class="dv">3</span>, <span class="dv">4</span>])</a></code></pre></div>
<p>To automate the cycle of loading this file into GHCi every time we make a change, we’re going to use <a href="https://github.com/ndmitchell/ghcid"><code>ghcid</code></a>, which does essentially that and not much else. This is the result of running <code>ghcid Main.hs</code>:</p>
<pre><code>Main.hs:4:12: error:
    • Found hole: _ :: [b]
      Where: ‘b’ is a rigid type variable bound by
               the type signature for:
                 map :: forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
               at Main.hs:3:1-29
    • In the expression: _
      In an equation for ‘map’: map f ls = _
    • Relevant bindings include
        ls :: [a] (bound at Main.hs:4:7)
        f :: a -&gt; b (bound at Main.hs:4:5)
        map :: (a -&gt; b) -&gt; [a] -&gt; [b] (bound at Main.hs:4:1)
  |
4 | map f ls = _
  |</code></pre>
<p>I’d suggest ignoring the middle and instead focusing on the top, which tells us the type of the hole, and the bottom, which tells us which bindings are in scope that we can use to fill in the hole.</p>
<p>In this case we aren’t learning anything new, and we already know that the hole is of type <code>[b]</code>, but it’s useful to know that our view of the world agrees with GHC’s. Of the bindings available to us, <code>ls</code> looks like the most promising, and we can split it into one of two cases: an empty list, or some element and the rest of the list. We can put a typed hole on the right hand side of each case alternative:</p>
<div class="sourceCode" id="cb7"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb7-1" data-line-number="1"><span class="kw">import</span> <span class="dt">Prelude</span> <span class="kw">hiding</span> (map)</a>
<a class="sourceLine" id="cb7-2" data-line-number="2"></a>
<a class="sourceLine" id="cb7-3" data-line-number="3">map<span class="ot"> ::</span> (a <span class="ot">-&gt;</span> b) <span class="ot">-&gt;</span> [a] <span class="ot">-&gt;</span> [b]</a>
<a class="sourceLine" id="cb7-4" data-line-number="4">map f ls <span class="fu">=</span> <span class="kw">case</span> ls <span class="kw">of</span></a>
<a class="sourceLine" id="cb7-5" data-line-number="5">    [] <span class="ot">-&gt;</span> _1</a>
<a class="sourceLine" id="cb7-6" data-line-number="6">    x<span class="fu">:</span>xs <span class="ot">-&gt;</span> _2</a>
<a class="sourceLine" id="cb7-7" data-line-number="7"></a>
<a class="sourceLine" id="cb7-8" data-line-number="8"><span class="ot">plusOne ::</span> <span class="dt">Int</span> <span class="ot">-&gt;</span> <span class="dt">Int</span></a>
<a class="sourceLine" id="cb7-9" data-line-number="9">plusOne i <span class="fu">=</span> i <span class="fu">+</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb7-10" data-line-number="10"></a>
<a class="sourceLine" id="cb7-11" data-line-number="11"><span class="ot">main ::</span> <span class="dt">IO</span> ()</a>
<a class="sourceLine" id="cb7-12" data-line-number="12">main <span class="fu">=</span> print ((map plusOne [<span class="dv">1</span>, <span class="dv">2</span>, <span class="dv">3</span>]) <span class="fu">==</span> [<span class="dv">2</span>, <span class="dv">3</span>, <span class="dv">4</span>])</a></code></pre></div>
<p>And our <code>ghcid</code> output changes:</p>
<pre><code>Main.hs:5:11-12: error:
    • Found hole: _1 :: [b]
      Where: ‘b’ is a rigid type variable bound by
               the type signature for:
                 map :: forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
               at Main.hs:3:1-29
      Or perhaps ‘_1’ is mis-spelled, or not in scope
    • In the expression: _1
      In a case alternative: [] -&gt; _1
      In the expression:
        case ls of
          [] -&gt; _1
          x : xs -&gt; _2
    • Relevant bindings include
        ls :: [a] (bound at Main.hs:4:7)
        f :: a -&gt; b (bound at Main.hs:4:5)
        map :: (a -&gt; b) -&gt; [a] -&gt; [b] (bound at Main.hs:4:1)
  |
5 |     [] -&gt; _1
  |           ^^
Main.hs:6:13-14: error:
    • Found hole: _2 :: [b]
      Where: ‘b’ is a rigid type variable bound by
               the type signature for:
                 map :: forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
               at Main.hs:3:1-29
      Or perhaps ‘_2’ is mis-spelled, or not in scope
    • In the expression: _2
      In a case alternative: x : xs -&gt; _2
      In the expression:
        case ls of
          [] -&gt; _1
          x : xs -&gt; _2
    • Relevant bindings include
        xs :: [a] (bound at Main.hs:6:7)
        x :: a (bound at Main.hs:6:5)
        ls :: [a] (bound at Main.hs:4:7)
        f :: a -&gt; b (bound at Main.hs:4:5)
        map :: (a -&gt; b) -&gt; [a] -&gt; [b] (bound at Main.hs:4:1)
  |
6 |     x:xs -&gt; _2
  |             ^^</code></pre>
<p>We haven’t learned anything new about the types, but we can make progress another way. The only sensible thing to put on the right hand side when given an empty list is another empty list, and when given an element and a list the most reasonable thing to do is to operate on each of them and put them together into a new list:</p>
<div class="sourceCode" id="cb9"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb9-1" data-line-number="1"><span class="kw">import</span> <span class="dt">Prelude</span> <span class="kw">hiding</span> (map)</a>
<a class="sourceLine" id="cb9-2" data-line-number="2"></a>
<a class="sourceLine" id="cb9-3" data-line-number="3">map<span class="ot"> ::</span> (a <span class="ot">-&gt;</span> b) <span class="ot">-&gt;</span> [a] <span class="ot">-&gt;</span> [b]</a>
<a class="sourceLine" id="cb9-4" data-line-number="4">map f ls <span class="fu">=</span> <span class="kw">case</span> ls <span class="kw">of</span></a>
<a class="sourceLine" id="cb9-5" data-line-number="5">    [] <span class="ot">-&gt;</span> []</a>
<a class="sourceLine" id="cb9-6" data-line-number="6">    x<span class="fu">:</span>xs <span class="ot">-&gt;</span> _1<span class="fu">:</span>_2</a>
<a class="sourceLine" id="cb9-7" data-line-number="7"></a>
<a class="sourceLine" id="cb9-8" data-line-number="8"><span class="ot">plusOne ::</span> <span class="dt">Int</span> <span class="ot">-&gt;</span> <span class="dt">Int</span></a>
<a class="sourceLine" id="cb9-9" data-line-number="9">plusOne i <span class="fu">=</span> i <span class="fu">+</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb9-10" data-line-number="10"></a>
<a class="sourceLine" id="cb9-11" data-line-number="11"><span class="ot">main ::</span> <span class="dt">IO</span> ()</a>
<a class="sourceLine" id="cb9-12" data-line-number="12">main <span class="fu">=</span> print ((map plusOne [<span class="dv">1</span>, <span class="dv">2</span>, <span class="dv">3</span>]) <span class="fu">==</span> [<span class="dv">2</span>, <span class="dv">3</span>, <span class="dv">4</span>])</a></code></pre></div>

        </div>
        <div id="footer">
            <div class="rc-scout">
                <script async defer src="https://www.recurse-scout.com/loader.js?t=5ac465e5d3396a7e491e42afac4c5c90"></script>
            </div>
        </div>
    </body>
</html>
<commit_msg>Travis build 408 pushed to Github Pages<commit_after><!doctype html>
<html lang="en">
    <head>
        <meta charset="utf-8">
        <meta http-equiv="x-ua-compatible" content="ie=edge">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <title>Moving Towards Dialogue - Vaibhav Sagar</title>
        <link rel="stylesheet" type="text/css" href="../../css/default.css" />
        <link rel="stylesheet" type="text/css" href="../../css/syntax.css" />
        <script>
          (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
          (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
          m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
          })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');

          ga('create', 'UA-79891461-1', 'auto');
          ga('send', 'pageview');

        </script>
    </head>
    <body>
        <div id="header">
            <div id="logo">
                <a href="../../">Vaibhav Sagar</a>
            </div>
            <div id="navigation">
                <a href="../../about/">About</a>
                <a href="../../talks/">Talks</a>
                <a href="../../archive/">Archive</a>
            </div>
        </div>

        <div id="content">
            <h1>Moving Towards Dialogue</h1>

            <div class="info">
    Posted on 25 September 2018
    
</div>
<div class="info">
    
        Tags: <a href="../../blog/tags/programming/">programming</a>, <a href="../../blog/tags/haskell/">haskell</a>
    
</div>

<p><em>This blog post is essentially a transcript of <a href="https://www.youtube.com/watch?v=0oo8wIi2qBE">a 10-minute talk I gave at !!Con</a>, the slides for which are available <a href="https://vaibhavsagar.com/presentations/typed-holes/">here</a>.</em></p>
<p>Let’s talk about typed holes. What’s a typed hole? A definition I like is <em>“a placeholder for an expression with a known type and an unknown value”</em>.</p>
<p>Why are typed holes useful? Because they allow the language to help us write programs! To demonstrate, let’s look at some code in Python, a language that lacks this feature.</p>
<p>Suppose I want to write a function that takes another function and a list and applies the function to each element of that list. A first stab might look like this:</p>
<div class="sourceCode" id="cb1"><pre class="sourceCode python"><code class="sourceCode python"><a class="sourceLine" id="cb1-1" data-line-number="1"><span class="op">&gt;&gt;&gt;</span> <span class="kw">def</span> <span class="bu">map</span>(f, ls): <span class="cf">return</span> []</a></code></pre></div>
<p>This is obviously wrong: this function ignores its arguments and gives us an empty list each time. This is no good, but what’s worse is that Python will accept this definition without complaint. It doesn’t seem to know (or care).</p>
<p>Let’s try again. I hear the way to do things with lists in Python is to use a list comprehension, so I make sure to use one of those this time:</p>
<div class="sourceCode" id="cb2"><pre class="sourceCode python"><code class="sourceCode python"><a class="sourceLine" id="cb2-1" data-line-number="1"><span class="op">&gt;&gt;&gt;</span> <span class="kw">def</span> <span class="bu">map</span>(f, ls): [f(e) <span class="cf">for</span> e <span class="kw">in</span> ls]</a>
<a class="sourceLine" id="cb2-2" data-line-number="2">...</a>
<a class="sourceLine" id="cb2-3" data-line-number="3"><span class="op">&gt;&gt;&gt;</span> plusOne <span class="op">=</span> <span class="kw">lambda</span> i: i <span class="op">+</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb2-4" data-line-number="4"><span class="op">&gt;&gt;&gt;</span> <span class="bu">print</span>(<span class="bu">map</span>(plusOne, [<span class="dv">1</span>, <span class="dv">2</span>, <span class="dv">3</span>]))</a>
<a class="sourceLine" id="cb2-5" data-line-number="5"><span class="va">None</span></a></code></pre></div>
<p>But this definition is still wrong, because I forgot to put a <code>return</code> statement in! Again, Python will happily accept this.</p>
<p>I’m getting a bit frustrated at this point, so I look at how <code>map</code> is actually implemented. It uses a generator comprehension instead of a list comprehension, which makes it more general somehow, so I make sure to use that, and I remember to put a <code>return</code> statement in this time:</p>
<div class="sourceCode" id="cb3"><pre class="sourceCode python"><code class="sourceCode python"><a class="sourceLine" id="cb3-1" data-line-number="1"><span class="op">&gt;&gt;&gt;</span> <span class="kw">def</span> <span class="bu">map</span>(f, ls): <span class="cf">return</span> (f(e) <span class="cf">for</span> e <span class="kw">in</span> ls)</a>
<a class="sourceLine" id="cb3-2" data-line-number="2">...</a>
<a class="sourceLine" id="cb3-3" data-line-number="3"><span class="op">&gt;&gt;&gt;</span> <span class="bu">print</span>(<span class="bu">map</span>(plusOne, [<span class="dv">1</span>, <span class="dv">2</span>, <span class="dv">3</span>]))</a>
<a class="sourceLine" id="cb3-4" data-line-number="4"><span class="op">&lt;</span>generator <span class="bu">object</span> <span class="bu">map</span>.<span class="op">&lt;</span><span class="bu">locals</span><span class="op">&gt;</span>.<span class="op">&lt;</span>genexpr<span class="op">&gt;</span> at <span class="bn">0x7ffb92103ca8</span><span class="op">&gt;</span></a></code></pre></div>
<p>And now instead of giving me something useful, this function gives me an address in memory, which seems especially pointless.</p>
<p>I give up. This example seems contrived, but over the course of my relationship with Python, which is more than a decade long now, I’ve seen the same dynamic play out embarrassingly many times. How do I write programs that work? Surely this is a simple question with a straightforward answer.</p>
<p>Indeed, the most common response I get when I ask this question is to write tests. That sounds reasonable, so let’s do that:</p>
<div class="sourceCode" id="cb4"><pre class="sourceCode python"><code class="sourceCode python"><a class="sourceLine" id="cb4-1" data-line-number="1"><span class="op">&gt;&gt;&gt;</span> <span class="kw">def</span> <span class="bu">map</span>(f, ls):</a>
<a class="sourceLine" id="cb4-2" data-line-number="2">...     <span class="bu">print</span>(<span class="st">&quot;Where are your tests now?&quot;</span>)</a>
<a class="sourceLine" id="cb4-3" data-line-number="3">...     <span class="cf">return</span> [<span class="dv">2</span>, <span class="dv">3</span>, <span class="dv">4</span>]</a>
<a class="sourceLine" id="cb4-4" data-line-number="4">...</a>
<a class="sourceLine" id="cb4-5" data-line-number="5"><span class="op">&gt;&gt;&gt;</span> <span class="bu">map</span>(plusOne, [<span class="dv">1</span>, <span class="dv">2</span>, <span class="dv">3</span>]) <span class="op">==</span> [<span class="dv">2</span>, <span class="dv">3</span>, <span class="dv">4</span>]</a>
<a class="sourceLine" id="cb4-6" data-line-number="6">Where are your tests now?</a>
<a class="sourceLine" id="cb4-7" data-line-number="7"><span class="va">True</span></a></code></pre></div>
<p>Okay, my test passes, so everything must be good, right?</p>
<p>I contend that tests are necessary, but not sufficient. They are problematic for at least two reasons:</p>
<ol type="1">
<li>They are only as good as the specification they imply for how a program should behave. If that specification is incomplete or wrong, no amount of tests will guarantee software that works.</li>
<li>The language doesn’t understand tests, by which I mean that it’s extremely difficult to automatically go from a failing test to the part of the code where the error lives. The programmer has to do the legwork of tracking down the bug based on essentially one bit of information in many cases.</li>
</ol>
<p>Fortunately, tests aren’t the only specification of how a program should behave. Types can also serve as specifications, and they have the advantage that they are extremely well integrated into the language in a way tests usually are not.</p>
<p>What does this mean in practice? Let’s look at Haskell. Haskell is statically typed, which means it expects to know the types of all the expressions in your program at compile time. This is nothing special though, lots of other languages also claim to be statically typed. What is special about Haskell though is that it has type inference, which means that you don’t have to annotate expressions with their types most of the time because the compiler can figure it out. If you put these two features together, you get typed holes!</p>
<p>Let’s try to write that same program in Haskell with typed holes. To start, let’s create a file called <code>Main.hs</code> with the following contents:</p>
<div class="sourceCode" id="cb5"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb5-1" data-line-number="1"><span class="kw">import</span> <span class="dt">Prelude</span> <span class="kw">hiding</span> (map)</a>
<a class="sourceLine" id="cb5-2" data-line-number="2"></a>
<a class="sourceLine" id="cb5-3" data-line-number="3">map<span class="ot"> ::</span> (a <span class="ot">-&gt;</span> b) <span class="ot">-&gt;</span> [a] <span class="ot">-&gt;</span> [b]</a>
<a class="sourceLine" id="cb5-4" data-line-number="4">map f ls <span class="fu">=</span> _</a>
<a class="sourceLine" id="cb5-5" data-line-number="5"></a>
<a class="sourceLine" id="cb5-6" data-line-number="6"><span class="ot">plusOne ::</span> <span class="dt">Int</span> <span class="ot">-&gt;</span> <span class="dt">Int</span></a>
<a class="sourceLine" id="cb5-7" data-line-number="7">plusOne i <span class="fu">=</span> i <span class="fu">+</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb5-8" data-line-number="8"></a>
<a class="sourceLine" id="cb5-9" data-line-number="9"><span class="ot">main ::</span> <span class="dt">IO</span> ()</a>
<a class="sourceLine" id="cb5-10" data-line-number="10">main <span class="fu">=</span> print ((map plusOne [<span class="dv">1</span>, <span class="dv">2</span>, <span class="dv">3</span>]) <span class="fu">==</span> [<span class="dv">2</span>, <span class="dv">3</span>, <span class="dv">4</span>])</a></code></pre></div>
<p>To automate the cycle of loading this file into GHCi every time we make a change, we’re going to use <a href="https://github.com/ndmitchell/ghcid"><code>ghcid</code></a>, which does essentially that and not much else. This is the result of running <code>ghcid Main.hs</code>:</p>
<pre><code>Main.hs:4:12: error:
    • Found hole: _ :: [b]
      Where: ‘b’ is a rigid type variable bound by
               the type signature for:
                 map :: forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
               at Main.hs:3:1-29
    • In the expression: _
      In an equation for ‘map’: map f ls = _
    • Relevant bindings include
        ls :: [a] (bound at Main.hs:4:7)
        f :: a -&gt; b (bound at Main.hs:4:5)
        map :: (a -&gt; b) -&gt; [a] -&gt; [b] (bound at Main.hs:4:1)
  |
4 | map f ls = _
  |</code></pre>
<p>I’d suggest ignoring the middle and instead focusing on the top, which tells us the type of the hole, and the bottom, which tells us which bindings are in scope that we can use to fill in the hole.</p>
<p>In this case we aren’t learning anything new, and we already know that the hole is of type <code>[b]</code>, but it’s useful to know that our view of the world agrees with GHC’s. Of the bindings available to us, <code>ls</code> looks like the most promising, and we can split it into one of two cases: an empty list, or some element and the rest of the list. We can put a typed hole on the right hand side of each case alternative:</p>
<div class="sourceCode" id="cb7"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb7-1" data-line-number="1"><span class="kw">import</span> <span class="dt">Prelude</span> <span class="kw">hiding</span> (map)</a>
<a class="sourceLine" id="cb7-2" data-line-number="2"></a>
<a class="sourceLine" id="cb7-3" data-line-number="3">map<span class="ot"> ::</span> (a <span class="ot">-&gt;</span> b) <span class="ot">-&gt;</span> [a] <span class="ot">-&gt;</span> [b]</a>
<a class="sourceLine" id="cb7-4" data-line-number="4">map f ls <span class="fu">=</span> <span class="kw">case</span> ls <span class="kw">of</span></a>
<a class="sourceLine" id="cb7-5" data-line-number="5">    [] <span class="ot">-&gt;</span> _1</a>
<a class="sourceLine" id="cb7-6" data-line-number="6">    x<span class="fu">:</span>xs <span class="ot">-&gt;</span> _2</a>
<a class="sourceLine" id="cb7-7" data-line-number="7"></a>
<a class="sourceLine" id="cb7-8" data-line-number="8"><span class="ot">plusOne ::</span> <span class="dt">Int</span> <span class="ot">-&gt;</span> <span class="dt">Int</span></a>
<a class="sourceLine" id="cb7-9" data-line-number="9">plusOne i <span class="fu">=</span> i <span class="fu">+</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb7-10" data-line-number="10"></a>
<a class="sourceLine" id="cb7-11" data-line-number="11"><span class="ot">main ::</span> <span class="dt">IO</span> ()</a>
<a class="sourceLine" id="cb7-12" data-line-number="12">main <span class="fu">=</span> print ((map plusOne [<span class="dv">1</span>, <span class="dv">2</span>, <span class="dv">3</span>]) <span class="fu">==</span> [<span class="dv">2</span>, <span class="dv">3</span>, <span class="dv">4</span>])</a></code></pre></div>
<p>And our <code>ghcid</code> output changes:</p>
<pre><code>Main.hs:5:11-12: error:
    • Found hole: _1 :: [b]
      Where: ‘b’ is a rigid type variable bound by
               the type signature for:
                 map :: forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
               at Main.hs:3:1-29
      Or perhaps ‘_1’ is mis-spelled, or not in scope
    • In the expression: _1
      In a case alternative: [] -&gt; _1
      In the expression:
        case ls of
          [] -&gt; _1
          x : xs -&gt; _2
    • Relevant bindings include
        ls :: [a] (bound at Main.hs:4:7)
        f :: a -&gt; b (bound at Main.hs:4:5)
        map :: (a -&gt; b) -&gt; [a] -&gt; [b] (bound at Main.hs:4:1)
  |
5 |     [] -&gt; _1
  |           ^^
Main.hs:6:13-14: error:
    • Found hole: _2 :: [b]
      Where: ‘b’ is a rigid type variable bound by
               the type signature for:
                 map :: forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
               at Main.hs:3:1-29
      Or perhaps ‘_2’ is mis-spelled, or not in scope
    • In the expression: _2
      In a case alternative: x : xs -&gt; _2
      In the expression:
        case ls of
          [] -&gt; _1
          x : xs -&gt; _2
    • Relevant bindings include
        xs :: [a] (bound at Main.hs:6:7)
        x :: a (bound at Main.hs:6:5)
        ls :: [a] (bound at Main.hs:4:7)
        f :: a -&gt; b (bound at Main.hs:4:5)
        map :: (a -&gt; b) -&gt; [a] -&gt; [b] (bound at Main.hs:4:1)
  |
6 |     x:xs -&gt; _2
  |             ^^</code></pre>
<p>We haven’t learned anything new about the types, but we can make progress another way. The only sensible thing to put on the right hand side when given an empty list is another empty list, and after splitting a list apart the most reasonable thing to do is to combine two other things into a new list:</p>
<div class="sourceCode" id="cb9"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb9-1" data-line-number="1"><span class="kw">import</span> <span class="dt">Prelude</span> <span class="kw">hiding</span> (map)</a>
<a class="sourceLine" id="cb9-2" data-line-number="2"></a>
<a class="sourceLine" id="cb9-3" data-line-number="3">map<span class="ot"> ::</span> (a <span class="ot">-&gt;</span> b) <span class="ot">-&gt;</span> [a] <span class="ot">-&gt;</span> [b]</a>
<a class="sourceLine" id="cb9-4" data-line-number="4">map f ls <span class="fu">=</span> <span class="kw">case</span> ls <span class="kw">of</span></a>
<a class="sourceLine" id="cb9-5" data-line-number="5">    [] <span class="ot">-&gt;</span> []</a>
<a class="sourceLine" id="cb9-6" data-line-number="6">    x<span class="fu">:</span>xs <span class="ot">-&gt;</span> _1<span class="fu">:</span>_2</a>
<a class="sourceLine" id="cb9-7" data-line-number="7"></a>
<a class="sourceLine" id="cb9-8" data-line-number="8"><span class="ot">plusOne ::</span> <span class="dt">Int</span> <span class="ot">-&gt;</span> <span class="dt">Int</span></a>
<a class="sourceLine" id="cb9-9" data-line-number="9">plusOne i <span class="fu">=</span> i <span class="fu">+</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb9-10" data-line-number="10"></a>
<a class="sourceLine" id="cb9-11" data-line-number="11"><span class="ot">main ::</span> <span class="dt">IO</span> ()</a>
<a class="sourceLine" id="cb9-12" data-line-number="12">main <span class="fu">=</span> print ((map plusOne [<span class="dv">1</span>, <span class="dv">2</span>, <span class="dv">3</span>]) <span class="fu">==</span> [<span class="dv">2</span>, <span class="dv">3</span>, <span class="dv">4</span>])</a></code></pre></div>
<p>Now the output gets a little more interesting:</p>
<pre><code>Main.hs:6:13-14: error:
    • Found hole: _1 :: b
      Where: ‘b’ is a rigid type variable bound by
               the type signature for:
                 map :: forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
               at Main.hs:3:1-29
      Or perhaps ‘_1’ is mis-spelled, or not in scope
    • In the first argument of ‘(:)’, namely ‘_1’
      In the expression: _1 : _2
      In a case alternative: x : xs -&gt; _1 : _2
    • Relevant bindings include
        xs :: [a] (bound at Main.hs:6:7)
        x :: a (bound at Main.hs:6:5)
        ls :: [a] (bound at Main.hs:4:7)
        f :: a -&gt; b (bound at Main.hs:4:5)
        map :: (a -&gt; b) -&gt; [a] -&gt; [b] (bound at Main.hs:4:1)
  |
6 |     x:xs -&gt; _1:_2
  |             ^^
Main.hs:6:16-17: error:
    • Found hole: _2 :: [b]
      Where: ‘b’ is a rigid type variable bound by
               the type signature for:
                 map :: forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
               at Main.hs:3:1-29
      Or perhaps ‘_2’ is mis-spelled, or not in scope
    • In the second argument of ‘(:)’, namely ‘_2’
      In the expression: _1 : _2
      In a case alternative: x : xs -&gt; _1 : _2
    • Relevant bindings include
        xs :: [a] (bound at Main.hs:6:7)
        x :: a (bound at Main.hs:6:5)
        ls :: [a] (bound at Main.hs:4:7)
        f :: a -&gt; b (bound at Main.hs:4:5)
        map :: (a -&gt; b) -&gt; [a] -&gt; [b] (bound at Main.hs:4:1)
  |
6 |     x:xs -&gt; _1:_2
  |</code></pre>
<p>Our first hole is now of type <code>b</code>, and we see that it’s possible to get a value of this type by applying <code>f</code> to <code>x</code>. The second hole is still of type <code>[b]</code>, and we see that the most reasonable way to get a value of this type is to recurse, using <code>map</code> with <code>f</code> and <code>xs</code>.</p>
<div class="sourceCode" id="cb11"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb11-1" data-line-number="1"><span class="kw">import</span> <span class="dt">Prelude</span> <span class="kw">hiding</span> (map)</a>
<a class="sourceLine" id="cb11-2" data-line-number="2"></a>
<a class="sourceLine" id="cb11-3" data-line-number="3">map<span class="ot"> ::</span> (a <span class="ot">-&gt;</span> b) <span class="ot">-&gt;</span> [a] <span class="ot">-&gt;</span> [b]</a>
<a class="sourceLine" id="cb11-4" data-line-number="4">map f ls <span class="fu">=</span> <span class="kw">case</span> ls <span class="kw">of</span></a>
<a class="sourceLine" id="cb11-5" data-line-number="5">    [] <span class="ot">-&gt;</span> []</a>
<a class="sourceLine" id="cb11-6" data-line-number="6">    x<span class="fu">:</span>xs <span class="ot">-&gt;</span> f x<span class="fu">:</span> map f xs</a>
<a class="sourceLine" id="cb11-7" data-line-number="7"></a>
<a class="sourceLine" id="cb11-8" data-line-number="8"><span class="ot">plusOne ::</span> <span class="dt">Int</span> <span class="ot">-&gt;</span> <span class="dt">Int</span></a>
<a class="sourceLine" id="cb11-9" data-line-number="9">plusOne i <span class="fu">=</span> i <span class="fu">+</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb11-10" data-line-number="10"></a>
<a class="sourceLine" id="cb11-11" data-line-number="11"><span class="ot">main ::</span> <span class="dt">IO</span> ()</a>
<a class="sourceLine" id="cb11-12" data-line-number="12">main <span class="fu">=</span> print ((map plusOne [<span class="dv">1</span>, <span class="dv">2</span>, <span class="dv">3</span>]) <span class="fu">==</span> [<span class="dv">2</span>, <span class="dv">3</span>, <span class="dv">4</span>])</a></code></pre></div>
<p>And <code>ghcid</code> is satisfied:</p>
<pre><code>All good (1 module, at &lt;time&gt;)</code></pre>
<p>It compiles! But does it work?</p>
<pre><code>$ runhaskell Main.hs
True</code></pre>
<p>Fantastic! We were able to ask the compiler for hints and get useful answers back. This is a gigantic improvement over anything I’m aware of in Python land.</p>
<p>Unfortunately, there is a catch: this program is too easy to break. Let me demonstrate my favourite way:</p>
<div class="sourceCode" id="cb14"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb14-1" data-line-number="1"><span class="kw">import</span> <span class="dt">Prelude</span> <span class="kw">hiding</span> (map)</a>
<a class="sourceLine" id="cb14-2" data-line-number="2"></a>
<a class="sourceLine" id="cb14-3" data-line-number="3">map<span class="ot"> ::</span> (a <span class="ot">-&gt;</span> b) <span class="ot">-&gt;</span> [a] <span class="ot">-&gt;</span> [b]</a>
<a class="sourceLine" id="cb14-4" data-line-number="4">map f ls <span class="fu">=</span> []</a>
<a class="sourceLine" id="cb14-5" data-line-number="5"></a>
<a class="sourceLine" id="cb14-6" data-line-number="6"><span class="ot">plusOne ::</span> <span class="dt">Int</span> <span class="ot">-&gt;</span> <span class="dt">Int</span></a>
<a class="sourceLine" id="cb14-7" data-line-number="7">plusOne i <span class="fu">=</span> i <span class="fu">+</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb14-8" data-line-number="8"></a>
<a class="sourceLine" id="cb14-9" data-line-number="9"><span class="ot">main ::</span> <span class="dt">IO</span> ()</a>
<a class="sourceLine" id="cb14-10" data-line-number="10">main <span class="fu">=</span> print ((map plusOne [<span class="dv">1</span>, <span class="dv">2</span>, <span class="dv">3</span>]) <span class="fu">==</span> [<span class="dv">2</span>, <span class="dv">3</span>, <span class="dv">4</span>])</a></code></pre></div>
<p>The astute reader will notice that this is the same as my earliest Python program. Here is what <code>ghcid</code> has to say:</p>
<pre><code>All good (1 module, at &lt;time&gt;)</code></pre>
<p>So what’s going on here? It turns out an empty list is a valid list of any type. Is it a list of Strings? Yup. Is it a list of Ints? Sure!</p>
<p>One way of avoiding this class of incorrect program is to specify that the input and the output lists should be of the same length. It’s possible to do this in Haskell, but it is a lot of work. Can we do better?</p>

        </div>
        <div id="footer">
            <div class="rc-scout">
                <script async defer src="https://www.recurse-scout.com/loader.js?t=5ac465e5d3396a7e491e42afac4c5c90"></script>
            </div>
        </div>
    </body>
</html>

{'fraction_non_alphanumeric': 0.21062792605820743, 'fraction_numerical': 0.020391910806506104, 'mean_word_length': 4.198720361309748, 'pattern_counts': {'":': 0, '<': 1367, '<?xml version=': 0, '>': 1367, 'https://': 10, 'lorem ipsum': 0, 'www.': 6, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5383336', 'n_tokens_mistral': 14616, 'n_tokens_neox': 14261, 'n_words': 4302}