State Transformers

What is State transformer and STRef trying to achieve?

• Encapsulating stateful computations that manipulate multiple mutable objects in the context of non-strict purely functional language.
• Once the actions are encoded in ST, that if we try to access a naked mutable object, it throws a compilation error.

Let us define the ST monad (in scalaz). In the simplified form it is,

case class World[A]()

case class ST[S, A](f: World[S] => (World[S], A)) {
  def apply(s: World[S]) = ..
  def flatMap[B](g: A => ST[S, B]): ST[S, B] = ...
  def map[B](g: A => B): ST[S, B] = ....
}
x
def returnST[S, A](a: => A): ST[S, A] = ...

• Monad with unit as returnST and flatMap as flatMap itself.
• The difference between State and State-monad is, the state is mutated in place, and is not observable from outside.
• The World represents some state of the world. (I have tried to use scalaz’s State instead of ST monad (basically, S instead of a World[S]) to solve the same problem, but got stuck in between. If interested, you may have a look at this line of code in my FP exercise repo. implementations)
• It encapsulates a state transformer.
• The contents of the state doesn’t really matter, but the type is (for what we want to do with ST monad - transform the state by mutating objects in place)
• Since type S is unique for a given ST, it is going to be a pure function.

STRef

STRef is a mutable variable (updatable location in the state capabale of holding a value) that’s used only with in the context of ST Monad. And that is, ST[S, STRef[S, A]] `

case class STRef[S, A](a: A) { private var value: A = a

// only path-way to access the value (it will be encapsulated in ST) def read: ST[S, A] = returnST(value)

// associate the new value `a` to this reference. // write mutates the object in place. def write(a: A): ST[S, STRef[S, A]] = ...

// modifies the value at this reference, that is `read` and then `write` def mod[B](f: A => A): ST[S, STRef[S, A]] = ... }

def newVar(a: => A) = returnST(STRef(a))

A simplified version is [here] (https://github.com/afsalthaj/supaku-sukara/blob/master/src/main/scala/com/thaj/functionalprogramming/exercises/part1/PureStatefulAPIGeneric.scala#L243)

Characteristics of STRef in a ST

• Playing around with STRef is going to be easy with the availability of monadic combinators. Have a look at the mod function as an example.
• STRef is type parameterized by type S.
• S represents the state thread that created the reference (STRef) holding a value (updatable).
• A single state thread can’t oversee other state thread, since they are of incompatible types.
• Since state transformers are composed sequentially, it’s guaranteed that both of them won’t mutate the same STRef/mutable-value.

Taking STRef out of ST ? No….

• You shouldn’t separate them.
• All your changes to the mutable value held by STRef, is done through ST (should be done)
• You might wonder, providing an initial value for world, and calling the run function in ST should be give STRef (that’s wrong again)
• Providing an initial state for World[S], sounds right. Scalaz has its implementation here, where it is Tower[A] and providing an IvoryTower as its initial value. https://github.com/scalaz/scalaz/blob/fabab8f699d56279d6f2cc28d02cc2b768e314d7/effect/src/main/scala/scalaz/effect/World.scala (doesn’t really matter)

So what are we trying to achieve?

Exposing STRef by any chance should lead to compile time error, or in other words no freedom to compose STRef by itself without a State thread.

Examples

• i.e, newVar(a).run in scalaz will throw a compile time error.
• newVar(a).flatMap(_.mod(_ + 1).flatMap(read)).run exposes only a and not STRef(a) to the client making it super safe.
• Rank 2 polymorphism technique is used here.

trait Forall[P[_]] { def apply[A]: P[A] }

def runST[A](f: Forall[({type F[S] = ST[S, A]})#F]): A = ... 

Refer to [my project]((https://github.com/afsalthaj/supaku-sukara/blob/master/src/main/scala/com/thaj/functionalprogramming/exercises/part1/PureStatefulAPIGeneric.scala#L243) for further examples, where we try to run the actions in many ways resulting in compile time errors.