title: Programming a state monad in Scala
body: <p>The theory of how a state monad looks like I borrow from Philip Wadler's Monads for Functional Programming:</p>
  <pre><code>type M a = State → (a, State) 
  type State = Int
  unit :: a → M a
  unit a = λx. (a, x)
  (*) :: M a → (a → M b) → M b
  m * k = λx. 
           let (a, y) = m x in 
           let (b, z) = k a y in 
           (b, z)
  </code></pre>
  <p>The way I would like to use a state monad is as follows:</p>
  <blockquote>
  <p>Given a list L I want different parts of my code to get this list and update this list by adding new elements at its end.</p>
  </blockquote>
  <p>I guess the above would be modified as:</p>
  <pre><code>type M = State → (List[Data], State) 
  type State = List[Data]
  def unit(a: List[Data]) = (x: State) =&gt; (a,x)
  def star(m: M, k: List[Data] =&gt; M): M = {
   (x: M) =&gt; 
     val (a,y) = m(x)
     val (b,z) = k(a)(y)
     (b,z)
  } 
  def get = ???
  def update = ???
  </code></pre>
  <p>How do I fill in the details, i.e.?</p>
  <ol>
  <li>How do I instantiate my hierarchy to work on a concrete list?</li>
  <li>How do I implement get and update in terms of the above?</li>
  </ol>
  <p>Finally, how would I do this using Scala's syntax with flatMap and unit?</p>