Can the State monad be used for self-modifying functions?

Question

I'd like to represent a self-modifying function in a functional manner, which has led me to consider the state monad. The version from the "Functional Programming in Scala" book is essentially a case class wrapper for the function S => (R,S) where S is state and R is the result. For example, it works with this random number generator as follows:

trait RNG {
    def nextInt : Int
}

case State[S,R]( run : S => (R,S) ) { /* other details omitted */ }

type Rand[R] = State[RNG,R] // `random generator of R'

So this all works fine since we need no parameters other than RNG (the 'state' part) to return an R (the 'result' part).

For a self-modifying function, the desire is to use the state monad to come up with a more syntactically-sugared version of the following:

trait Fn[A,R] {
   def apply(a: A): (R,Fn[A,R])
}

and this would ideally be done with the map and flatMap methods (which can then be sugared automatically via Scala's for notation).

However, unlike the Rand example, Fn takes an argument of type A.

Is this sort of thing still representable using the state monad? If not, can it still be expressed as a monand and if so, how would one write whichever of map or flatMap are considered to be fundamental*?

*I mention this last point because the FPiS monad trait seems to treat map as the elementary operation.

lmm lmm · Accepted Answer · 2014-12-09T08:47:21

This should be fine; the obvious approach will work:

def applyState[A, R](a: A) = State(fn: Fn[A, R] => fn.apply(a))

val composedState = for {
  firstResult <- applyState[Int, Thingy](2)
  secondResult <- applyState[Int, Thingy](4)
} yield secondResult

composedState.run(new Fn[Int, Thingy]{...})

Can the State monad be used for self-modifying functions?

1 Answers