<commit_before><!DOCTYPE html>
<html lang="en">
<head>
        <meta charset="utf-8" />
        <title>Lazy Functional State Threads</title>
        <link rel="stylesheet" href="http://www.vaibhavsagar.com/theme/css/main.css" />
        <link href="http://www.vaibhavsagar.com/feeds/all.atom.xml" type="application/atom+xml" rel="alternate" title="Vaibhav Sagar's Site Atom Feed" />

        <!--[if IE]>
            <script src="https://html5shiv.googlecode.com/svn/trunk/html5.js"></script>
        <![endif]-->
</head>

<body id="index" class="home">
<a href="https://github.com/vaibhavsagar">
<img style="position: absolute; top: 0; right: 0; border: 0;" src="https://s3.amazonaws.com/github/ribbons/forkme_right_red_aa0000.png" alt="Fork me on GitHub" />
</a>
        <header id="banner" class="body">
                <h1><a href="http://www.vaibhavsagar.com/">Vaibhav Sagar's Site </a></h1>
                <nav><ul>
                    <li><a href="/blog/archives/">all</a></li>
                    <li><a href="http://www.vaibhavsagar.com/about/">about</a></li>
                    <li><a href="http://www.vaibhavsagar.com/blog/misc/">misc</a></li>
                    <li class="active"><a href="http://www.vaibhavsagar.com/blog/programming/">programming</a></li>
                </ul></nav>
        </header><!-- /#banner -->
<section id="content" class="body">
  <article>
    <header>
      <h1 class="entry-title">
        <a href="http://www.vaibhavsagar.com/drafts/lazy-functional-state-threads.html" rel="bookmark"
           title="Permalink to Lazy Functional State Threads">Lazy Functional State Threads</a></h1>
    </header>

    <div class="entry-content">
<footer class="post-info">
        <abbr class="published" title="2017-06-19T00:00:00+10:00">
                Published: Mon 19 June 2017
        </abbr>

        <address class="vcard author">
                By                         <a class="url fn" href="http://www.vaibhavsagar.com/author/vaibhav-sagar.html"><NAME></a>
        </address>
<p>In <a href="http://www.vaibhavsagar.com/blog/programming/">programming</a>.</p>

</footer><!-- /.post-info -->      <p>A funny thing happened when I was writing my Imperative Haskell post: after
railing against Haskell's tendency to tell you to go off and read a paper when
introducing a library, I went off and read 'Lazy Functional State Threads' and
was gobsmacked by how accessible I found it. I'd like to try and demystify it
for other people!</p>
<p>The paper begins by stating that the authors want to express strict stateful
computations in a purely-functional language efficiently. They want to do this
<a href="http://www.threewordphrase.com/pardonme.gif">because of reasons</a>. Some
examples of algorithms they'd like to express are those based on mutable hash
tables, union find, and especially input/output. However, the language they are
working with is renowned for its laziness, which means the order of evaluation
can be counterintuitive, and its referential transparency, which means a lack
of side effects.</p>
<p>The authors manage to square this circle by leveraging the type system, which
simultaneously allows most of the features we take for granted in imperative
languages (multiple named variables, in-place updates) as well as being
encapsulated and referentially transparent (in a sense).</p>
    </div><!-- /.entry-content -->

  </article>
</section>
        <section id="extras" class="body">
                <div class="social">
                        <h2>social</h2>
                        <ul>
                            <li><a href="http://www.vaibhavsagar.com/feeds/all.atom.xml" type="application/atom+xml" rel="alternate">atom feed</a></li>

                        </ul>
                </div><!-- /.social -->
        </section><!-- /#extras -->

        <footer id="contentinfo" class="body"><commit_msg>Travis build 148 pushed to Github Pages<commit_after><!DOCTYPE html>
<html lang="en">
<head>
        <meta charset="utf-8" />
        <title>Lazy Functional State Threads</title>
        <link rel="stylesheet" href="http://www.vaibhavsagar.com/theme/css/main.css" />
        <link href="http://www.vaibhavsagar.com/feeds/all.atom.xml" type="application/atom+xml" rel="alternate" title="Vaibhav Sagar's Site Atom Feed" />

        <!--[if IE]>
            <script src="https://html5shiv.googlecode.com/svn/trunk/html5.js"></script>
        <![endif]-->
</head>

<body id="index" class="home">
<a href="https://github.com/vaibhavsagar">
<img style="position: absolute; top: 0; right: 0; border: 0;" src="https://s3.amazonaws.com/github/ribbons/forkme_right_red_aa0000.png" alt="Fork me on GitHub" />
</a>
        <header id="banner" class="body">
                <h1><a href="http://www.vaibhavsagar.com/">Vaibhav Sagar's Site </a></h1>
                <nav><ul>
                    <li><a href="/blog/archives/">all</a></li>
                    <li><a href="http://www.vaibhavsagar.com/about/">about</a></li>
                    <li><a href="http://www.vaibhavsagar.com/blog/misc/">misc</a></li>
                    <li class="active"><a href="http://www.vaibhavsagar.com/blog/programming/">programming</a></li>
                </ul></nav>
        </header><!-- /#banner -->
<section id="content" class="body">
  <article>
    <header>
      <h1 class="entry-title">
        <a href="http://www.vaibhavsagar.com/drafts/lazy-functional-state-threads.html" rel="bookmark"
           title="Permalink to Lazy Functional State Threads">Lazy Functional State Threads</a></h1>
    </header>

    <div class="entry-content">
<footer class="post-info">
        <abbr class="published" title="2017-06-19T00:00:00+10:00">
                Published: Mon 19 June 2017
        </abbr>

        <address class="vcard author">
                By                         <a class="url fn" href="http://www.vaibhavsagar.com/author/vaibhav-sagar.html"><NAME></a>
        </address>
<p>In <a href="http://www.vaibhavsagar.com/blog/programming/">programming</a>.</p>

</footer><!-- /.post-info -->      <p>A funny thing happened when I was writing my Imperative Haskell post: after
railing against Haskell's tendency to tell you to go off and read a paper when
introducing a library, I went off and read 'Lazy Functional State Threads' and
was gobsmacked by how accessible I found it. I'd like to try and demystify it
for a wider audience.</p>
<p>The paper begins by admitting that we sometimes want to express strict stateful
computations in a purely-functional language efficiently. We want to do this
<a href="http://www.threewordphrase.com/pardonme.gif">because of reasons</a>. Some
examples of algorithms we'd like to express are those based on mutable hash
tables, union find, and especially input/output. However, the language we are
working with is renowned for its laziness, which means the order of evaluation
can be counterintuitive, and its referential transparency, which means a lack
of side effects.</p>
<p>We square this circle by leveraging the type system, which simultaneously
allows most of the features we take for granted in imperative languages
(multiple named variables, in-place updates) as well as being encapsulated and
referentially transparent (for certain values of referentially transparent).
Let's define a 'state transformer' that takes an initial state as input and
returns a final state. This can be represented as a value of type <code>ST s a</code>
where <code>s</code> is the state type and <code>a</code> is the return type.</p>
<!-- picture of state transformer -->

<p>A state transformer can have multiple inputs (multiple arguments to a function)
and multiple outputs (a tuple).</p>
<!-- picture of multiple input/output state transformer -->

<p>The simplest state transformer takes a value of type <code>a</code> and sticks it in a
state transformer. We'll call it <code>returnST</code>.</p>
<!-- picture of returnST -->

<p>Let's talk about 'state' now, specifically mutable variables or references.
Let's specify an API for working with references:</p>
<div class="highlight"><pre><span></span><span class="nf">newVar</span>   <span class="ow">::</span> <span class="n">a</span> <span class="ow">-&gt;</span> <span class="kt">ST</span> <span class="n">s</span> <span class="p">(</span><span class="kt">MutVar</span> <span class="n">s</span> <span class="n">a</span><span class="p">)</span>
<span class="nf">readVar</span>  <span class="ow">::</span> <span class="kt">MutVar</span> <span class="n">s</span> <span class="n">a</span> <span class="ow">-&gt;</span> <span class="kt">ST</span> <span class="n">s</span> <span class="n">a</span>
<span class="nf">writeVar</span> <span class="ow">::</span> <span class="kt">MutVar</span> <span class="n">s</span> <span class="n">a</span> <span class="ow">-&gt;</span> <span class="n">a</span> <span class="ow">-&gt;</span> <span class="kt">ST</span> <span class="n">s</span> <span class="nb">()</span>
</pre></div>


<p>In other words, <code>newVar</code> takes a value of type <code>a</code> and returns a state
transformer that can be supplied a state to output a new state containing a
fresh reference to the provided value. <code>readVar</code> is a state transformer which
leaves the provided state unchanged but extracts the value in the reference
from it. <code>writeVar</code> takes a reference and a new value and returns a state
transformer that updates the reference to point to the new value. The fact that
the return value is <code>()</code> indicates that this state transformer is only useful
for its effect on the state.</p>
<p>To compose these state transformers together we can define a <code>thenST</code>:</p>
<div class="highlight"><pre><span></span><span class="nf">thenST</span> <span class="ow">::</span> <span class="kt">ST</span> <span class="n">s</span> <span class="n">a</span> <span class="ow">-&gt;</span> <span class="p">(</span><span class="n">a</span> <span class="ow">-&gt;</span> <span class="kt">ST</span> <span class="n">s</span> <span class="n">b</span><span class="p">)</span> <span class="ow">-&gt;</span> <span class="kt">ST</span> <span class="n">s</span> <span class="n">b</span>
</pre></div>


<!-- picture of thenST -->

<p>Two things to note here: both <code>s1</code> and <code>s2</code> have to work with the same state
type <code>s</code>, and they way they work is inherently sequential, because the output
of <code>s1</code> is the input of <code>s2</code>. This is where 'thread' in the title comes from. I
like to think of this as the baton in a relay: you can't run when you're not
holding the baton, and you can't use a different team's baton because that's
against the rules.</p>
<p>While we let that sink in, I'd like to make a brief historical digression. At
this stage in Haskell's history, monads had been identified as a useful
abstraction and a predecessor to this paper had proposed a particular syntax
for working with them, but do-notation had not yet made its way into the
language. If you're not familiar with monads, you can think of them as an
interface for a type defined by two functions, <code>return</code> and <code>&gt;&gt;=</code>
(pronounced 'bind') and certain laws that these functions must obey:</p>
<div class="highlight"><pre><span></span><span class="kr">class</span> <span class="kt">Monad</span> <span class="n">m</span> <span class="kr">where</span>
    <span class="n">return</span> <span class="ow">::</span> <span class="n">a</span> <span class="ow">-&gt;</span> <span class="n">m</span> <span class="n">a</span>
    <span class="p">(</span><span class="o">&gt;&gt;=</span><span class="p">)</span>  <span class="ow">::</span> <span class="n">m</span> <span class="n">a</span> <span class="ow">-&gt;</span> <span class="p">(</span><span class="n">a</span> <span class="ow">-&gt;</span> <span class="n">m</span> <span class="n">b</span><span class="p">)</span> <span class="ow">-&gt;</span> <span class="n">m</span> <span class="n">b</span>
</pre></div>


<p>The actual definition differs slightly in ways that aren't relevant here. Why
do I bring this up? If you look closely, we've encountered functions that look
very similar to the two above. If we textually replace <code>m</code> with <code>ST s</code>, we get</p>
<div class="highlight"><pre><span></span><span class="nf">return</span> <span class="ow">::</span> <span class="n">a</span> <span class="ow">-&gt;</span> <span class="kt">ST</span> <span class="n">s</span> <span class="n">a</span>
<span class="p">(</span><span class="o">&gt;&gt;=</span><span class="p">)</span>  <span class="ow">::</span> <span class="kt">ST</span> <span class="n">s</span> <span class="n">a</span> <span class="ow">-&gt;</span> <span class="p">(</span><span class="n">a</span> <span class="ow">-&gt;</span> <span class="kt">ST</span> <span class="n">s</span> <span class="n">b</span><span class="p">)</span> <span class="ow">-&gt;</span> <span class="kt">ST</span> <span class="n">s</span> <span class="n">b</span>
</pre></div>


<p>which are exactly the type signatures of <code>returnST</code> and <code>thenST</code>. This isn't a
coincidence. I will also claim (but not prove) that these definitions are
law-abiding.</p>
<p>What can we do with this information? Let's take this code snippet that swaps
the contents of two references:</p>
<div class="highlight"><pre><span></span><span class="nf">swap</span> <span class="ow">::</span> <span class="kt">MutVar</span> <span class="n">s</span> <span class="n">a</span> <span class="ow">-&gt;</span> <span class="kt">MutVar</span> <span class="n">s</span> <span class="n">a</span> <span class="ow">-&gt;</span> <span class="kt">ST</span> <span class="n">s</span> <span class="nb">()</span>
<span class="nf">swap</span> <span class="n">v</span> <span class="n">w</span> <span class="ow">=</span> <span class="n">readVar</span> <span class="n">v</span>    <span class="p">`</span><span class="n">thenST</span><span class="p">`</span> <span class="p">(</span><span class="nf">\</span><span class="n">a</span> <span class="ow">-&gt;</span>
           <span class="n">readVar</span> <span class="n">w</span>    <span class="p">`</span><span class="n">thenST</span><span class="p">`</span> <span class="p">(</span><span class="nf">\</span><span class="n">b</span> <span class="ow">-&gt;</span>
           <span class="n">writeVar</span> <span class="n">v</span> <span class="n">b</span> <span class="p">`</span><span class="n">thenST</span><span class="p">`</span> <span class="p">(</span><span class="nf">\</span><span class="kr">_</span> <span class="ow">-&gt;</span>
           <span class="n">writeVar</span> <span class="n">w</span> <span class="n">a</span><span class="p">)))</span>
</pre></div>


<p>This requires working with infix backticks and lambdas and looks pretty ugly,
but we can do better! We have do-notation which is syntax sugar that converts</p>
<div class="highlight"><pre><span></span><span class="kr">do</span> <span class="n">x</span> <span class="ow">&lt;-</span> <span class="n">f</span>
   <span class="n">y</span>
</pre></div>


<p>into</p>
<div class="highlight"><pre><span></span><span class="nf">f</span> <span class="o">&gt;&gt;=</span> <span class="p">(</span><span class="nf">\</span><span class="n">x</span> <span class="ow">-&gt;</span> <span class="n">y</span><span class="p">)</span>
</pre></div>


<p>and</p>
<div class="highlight"><pre><span></span><span class="kr">do</span> <span class="n">x</span>
   <span class="n">y</span>
</pre></div>


<p>into</p>
<div class="highlight"><pre><span></span><span class="nf">x</span> <span class="o">&gt;&gt;</span> <span class="n">y</span>
</pre></div>


<p>where <code>&gt;&gt;</code> is like <code>&gt;&gt;=</code> that ignores the output of the left hand side:</p>
<div class="highlight"><pre><span></span>(&gt;&gt;) :: Monad m =&gt; m a -&gt; m b -&gt; m b
(&gt;&gt;) ma mb = ma &gt;&gt;= (\_ -&gt; mb)
</pre></div>


<p>Armed with this knowledge, we can rewrite the above example:</p>
<div class="highlight"><pre><span></span><span class="nf">swap</span> <span class="ow">::</span> <span class="kt">MutVar</span> <span class="n">s</span> <span class="n">a</span> <span class="ow">-&gt;</span> <span class="kt">MutVar</span> <span class="n">s</span> <span class="n">a</span> <span class="ow">-&gt;</span> <span class="kt">ST</span> <span class="n">s</span> <span class="nb">()</span>
<span class="nf">swap</span> <span class="n">v</span> <span class="n">w</span> <span class="ow">=</span> <span class="kr">do</span>
    <span class="n">a</span> <span class="ow">&lt;-</span> <span class="n">readVar</span> <span class="n">v</span>
    <span class="n">b</span> <span class="ow">&lt;-</span> <span class="n">readVar</span> <span class="n">w</span>
    <span class="n">writeVar</span> <span class="n">v</span> <span class="n">b</span>
    <span class="n">writeVar</span> <span class="n">w</span> <span class="n">a</span>
</pre></div>


<p>Much better! We even define <code>(&gt;&gt;)</code> directly as <code>thenST_</code>. The rest of the code
samples in this post will use do-notation.</p>
<p>The authors also mention the existence of <code>fixST</code>, but this isn't discussed
elsewhere in the paper so I'll skip that.</p>
    </div><!-- /.entry-content -->

  </article>
</section>
        <section id="extras" class="body">
                <div class="social">
                        <h2>social</h2>
                        <ul>
                            <li><a href="http://www.vaibhavsagar.com/feeds/all.atom.xml" type="application/atom+xml" rel="alternate">atom feed</a></li>

                        </ul>
                </div><!-- /.social -->
        </section><!-- /#extras -->

        <footer id="contentinfo" class="body">
{'fraction_non_alphanumeric': 0.1993123273772617, 'fraction_numerical': 0.005016628149484246, 'mean_word_length': 4.02891156462585, 'pattern_counts': {'":': 0, '<': 751, '<?xml version=': 0, '>': 751, 'https://': 6, 'lorem ipsum': 0, 'www.': 22, 'xml': 8}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2127114', 'n_tokens_mistral': 5973, 'n_tokens_neox': 5697, 'n_words': 1634}