<h2 id="intro">Intro</h2>
<p>Last time we built a weighted list, this time we’re using that to build markov chains. Wikipedia states that “A Markov chain is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event.” and that they’re named after the Russian mathematician Andrey Markov.</p>
<h2 id="configuration">Configuration</h2>
<p>We’re after generic system, hence parametrized data types.</p>
<p>First part is <code>Configuration a</code> that lists possible starting elements of chain and elements that can follow a particular element.</p>
<pre><code>data Config a = Config
    { configStarts :: ![Item a]
    , configContinuations :: !(Map a [Item a])
    } deriving (Show, Read, Eq)</code></pre>
<p>Second part is <code>Item a</code>, that just holds single item that could appear in chain and relatively frequency for its appearance.</p>
<pre><code>data Item a =
    Item (Frequency (Maybe a))
    deriving (Show, Read, Eq)</code></pre>
<p>We’re using <code>Maybe a</code> as in some cases there’s chance of element being last element in chain. Thus, <code>Nothing</code> will represent end of chain.</p>
<p>In previous episode, we implemented <code>choose</code>, but later on I decided to rename it to <code>chooseM</code>. So when you see <code>chooseM</code>, it’s just different name for what we implemented previously.</p>
<h2 id="building-a-chain">Building a chain</h2>
<p>Since building a configuration depends on the case quite a bit, we’re just going to assume that we have one at hand.</p>
<p>Our chains are built by <code>chainM :: (Ord a, RandomGen g) =&gt; Config a -&gt; Rand g [a]</code>. Given a config, it creates computation that when run will return list of <code>a</code>, which is our chain.</p>
<p>Implementation is fairly straightforward:</p>
<pre><code>chainM config = do
    starter &lt;- chooseM (itemToFreq &lt;$&gt; configStarts config)
    case join starter of
        Nothing -&gt;
            return []

        Just h -&gt; do
            t &lt;- tailOfChain config h
            return $ h : t</code></pre>
<p>First we select item from starting elements. In case there isn’t one, result will be a empty list. Otherwise we use <code>tailOfChain</code> to compute rest of the list and return a list of starter element followed by that tail.</p>
<p>For tail we need to figure out first what possible elements there are that can follow a given element. This is done by <code>candidates</code> function. <code>lookup</code> finds a possible list of elements in <code>configContinuations</code>. We use <code>itemToFreq</code> to turn this list into frequencies. Since <code>items</code> might be <code>Nothing</code> (in case where there aren’t any suitable continuations present) and any continuation in the list might be <code>Nothing</code> (in case where this is possibly terminating element), we have to use <code>(fmap . fmap)</code> to apply <code>itemToFreq</code> to each possible element. Moreover, <code>concat</code> turns our <code>Maybe [Frequency (Maybe a)]</code> into <code>[Frequency (Maybe a)]</code>, if we have <code>Nothing</code> at this stage, result will be an empty list <code>[]</code>.</p>
<pre><code>candidates :: (Ord a) =&gt; Config a -&gt; a -&gt; [Frequency (Maybe a)]
candidates config x =
    concat $ (fmap . fmap) itemToFreq items
    where
        items = lookup x (configContinuations config)</code></pre>
<p>That <code>concat</code> part could have been written as:</p>
<pre><code>    case (fmap . fmap) itemToFreq items of
        Nothing -&gt;
            []

        Just x -&gt;
            x</code></pre>
<p>and the end result would be identical.</p>
<p>Now that we know how to figure our possible continuation elements, we can implement computing tail of chain:</p>
<pre><code>tailOfChain :: (Ord a, RandomGen g) =&gt; Config a -&gt; a -&gt; Rand g [a]
tailOfChain config c = do
    item &lt;- chooseM (candidates config c)
    case join item of
        Nothing -&gt;
            return []

        Just x -&gt; do
             xs &lt;- tailOfChain config x
             return $ x : xs</code></pre>
<p>Function first select <code>item</code> from candidates. If there isn’t suitable item or item is <code>Nothing</code>, result will be an empty list. Otherwise function recurses, computes tail starting from selected element and constructs chain starting by selected <code>item</code> and followed by tail.</p>
<p><code>join item</code> at the start of case analysis collapses two nested <code>Maybe</code>s together:</p>
<ul>
<li><code>Nothing</code> will result <code>Nothing</code> (no suitable continuation)</li>
<li><code>Just Nothing</code> will also result <code>Nothing</code> (end of chain reached)</li>
<li><code>Just a</code> will result <code>Just a</code> (suitable element found)</li>
</ul>
<p>In the end we have list that is sort of like: <code>h : chooseM (candidates config h) : chooseM (candidates config h') : chooseM (candidates config h'') : ... : []</code></p>
<h2 id="extra">Extra</h2>
<p>For convenience we define two other functions. First one is for when we don’t want to use <code>Rand g a</code>. It’s done by applying <code>runRand</code> function with our <code>chainM</code> function, config and <code>RandomGen</code>.</p>
<pre><code>chain :: (Ord a, RandomGen g) =&gt; Config a -&gt; g -&gt; ([a], g)
chain config g =
    runRand (chainM config) g</code></pre>
<p>More interesting is <code>chains</code> which builds infinite list of chains:</p>
<pre><code>chains :: (Ord a, RandomGen g) =&gt; Config a -&gt; g -&gt; [[a]]
chains config g =
        c : chains config g&#39;
    where
        (c, g&#39;) = chain config g</code></pre>
<p>This uses <code>chain</code> function to create starting element (which is markov chain) and new generator <code>g'</code>. Then it builds a list where that first chain is followed by list of chains that is created by calling <code>chains</code> with that new random generator. Since there’s no termination case in the function, it will compute infinitely long list of markov chains. This works because elements are computed only when needed. For all intents and purposes for program using this infinite list, items are there when needed.</p>
<h2 id="closing">Closing</h2>
<p>Hardest part working with markov chains (at least in my opinion) is building suitable configuration. When you have that configuration at hand, building chains from it requires relatively small amount of code. In the next episode we’re going to use this chains for our space game.</p>
<p>Questions, comments and feedback are always welcome. Best way to reach me is by email or in fediverse where I’m <code>Tuula@mastodon.social</code>.</p>
