How to use the traverse TypeClass to accumulate state based on the elements and then map over the state and elements?

functional-programming, iterator, scala

Solution

When you use the `traverse` method with a function returning a `State`, you get exactly what you want:

   // a function using the current element and the previous state
   def function[S, T](s: S, t: T): R = // combine T and S

   // return a State instance to use as an Applicative with traverse
   def myState[T, S](t: T) = State[S, R]((s: S) => function(s, t))

   // a sequence to traverse
   val sequence: Seq[T] = ...

   // use the traverse method
   sequence.traverse(t => myState(t))

Problem

What is the function that I should pass to 'traverse' (from the essence of the iterator pattern) such that I can accumulate state based on each of the original elements and then map based on the original elements and the state so far. In 'collect' and 'disperse' only either the mapping depends on the state or the state depends on the element, but not both at the same time. The table at http://etorreborre.blogspot.co.uk/2011/06/essence-of-iterator-pattern.html appears to say that I should use 'traverse' but traverse is the function that implements all the others, so I'm a bit lost.

Original source