title: what is proper monad or sequence comprehension to both map and carry state across?
body: <p>I'm writing a programming language interpreter.</p>
  
  <p>I have need of the right code idiom to both evaluate a sequence of expressions to get a sequence of their values, and propagate state from one evaluator to the next to the next as the evaluations take place. I'd like a functional programming idiom for this.</p>
  
  <p>It's not a fold because the results come out like a map. It's not a map because of the state prop across.</p>
  
  <p>What I have is this code which I'm using to try to figure this out. Bear with a few lines of test rig first:</p>
  
  <pre><code>// test rig
  class MonadLearning extends JUnit3Suite {
  
    val d = List("1", "2", "3") // some expressions to evaluate. 
  
    type ResType = Int 
    case class State(i : ResType) // trivial state for experiment purposes
    val initialState = State(0)
  
  // my stub/dummy "eval" function...obviously the real one will be...real.
    def computeResultAndNewState(s : String, st : State) : (ResType, State) = {
      val State(i) = st
      val res = s.toInt + i
      val newStateInt = i + 1
      (res, State(newStateInt))
    }
  </code></pre>
  
  <p>My current solution. Uses a var which is updated as the body of the map is evaluated:</p>
  
  <pre><code>  def testTheVarWay() {
      var state = initialState
      val r = d.map {
        s =&gt;
          {
            val (result, newState) = computeResultAndNewState(s, state)
            state = newState
            result
          }
      }
      println(r)
      println(state)
    }
  </code></pre>
  
  <p>I have what I consider unacceptable solutions using foldLeft which does what I call "bag it as you fold" idiom:</p>
  
  <pre><code>def testTheFoldWay() {
  
  // This startFold thing, requires explicit type. That alone makes it muddy.
  val startFold : (List[ResType], State) = (Nil, initialState)
  val (r, state) = d.foldLeft(startFold) {
    case ((tail, st), s) =&gt; {
      val (r, ns) = computeResultAndNewState(s, st)
      (tail :+ r, ns) // we want a constant-time append here, not O(N). Or could Cons on front and reverse later
    }
  }
  
  println(r)
  println(state)
  
  }
  </code></pre>
  
  <p>I also have a couple of recursive variations (which are obvious, but also not clear or well motivated), one using streams which is almost tolerable:</p>
  
  <pre><code>def testTheStreamsWay() {
    lazy val states = initialState #:: resultStates // there are states
    lazy val args = d.toStream // there are arguments
    lazy val argPairs = args zip states // put them together
    lazy val resPairs : Stream[(ResType, State)] = argPairs.map{ case (d1, s1) =&gt; computeResultAndNewState(d1, s1) } // map across them
    lazy val (results , resultStates) = myUnzip(resPairs)// Note .unzip causes infinite loop. Had to write my own.
  
    lazy val r = results.toList
    lazy val finalState = resultStates.last
  
    println(r)
    println(finalState)
  }
  </code></pre>
  
  <p>But, I can't figure out anything as compact or clear as the original 'var' solution above, which I'm willing to live with, but I think somebody who eats/drinks/sleeps monad idioms is going to just say ... use this... (Hopefully!)</p>