Programming a state monad in Scala

Question

The theory of how a state monad looks like I borrow from Philip Wadler's Monads for Functional Programming:

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)

The way I would like to use a state monad is as follows:

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.

I guess the above would be modified as:

type M = State → (List[Data], State) 
type State = List[Data]
def unit(a: List[Data]) = (x: State) => (a,x)
def star(m: M, k: List[Data] => M): M = {
 (x: M) => 
   val (a,y) = m(x)
   val (b,z) = k(a)(y)
   (b,z)
} 
def get = ???
def update = ???

How do I fill in the details, i.e.?

How do I instantiate my hierarchy to work on a concrete list?
How do I implement get and update in terms of the above?

Finally, how would I do this using Scala's syntax with flatMap and unit?

It would probably be easier to implement if you make your State a class and define flatMap inside it. And you can define unit in the companion object. - Anyways, get is pretty straightforward you receive an M and return its State. And update would be, you receive an M and a new State and you create a new M. — Luis Miguel Mejía Suárez
@LuisMiguelMejíaSuárez thanks for your comment. What do you mean exactly by "receive an M". If its M of type M above, I don't know what is its state since it would a function. Do you mean a pair a x State? — Rodrigo
this link explains well the use in practice of state monads in haskell mmhaskell.com/monads/state — Rodrigo

user user · Accepted Answer · 2020-07-11T16:40:31

Your M is defined incorrectly. It should take a/A as a parameter, like so:

type M[A] = State => (A, State)

You've also missed that type parameter elsewhere.

unit should have a signature like this:

def unit[A](a: A): M[A]

star should have a signature like this:

def star[A, B](m: M[A], k: A => M[B]): M[B]

Hopefully, that makes the functions more clear.

Your implementation of unit was pretty much the same:

def unit[A](a: A): M[A] = x => (a, x)

However, in star, the parameter of your lambda (x) is of type State, not M, because M[B] is basically State => (A, State). The rest you got right:

def star[A, B](m: M[A])(k: A => M[B]): M[B] = 
  (x: State) => {
    val (a, y) = m(x)
    val (b, z) = k(a)(y)
    (b, z)
  }

Edit: According to @Luis Miguel Mejia Suarez:

It would probably be easier to implement if you make your State a class and define flatMap inside it. And you can define unit in the companion object.

He suggested final class State[S, A](val run: S => (A, S)), which would also allow you to use infix functions like >>=.

Another way to do it would be to define State as a type alias for a function S => (A, S) and extend it using an implicit class.

type State[S, A] = S => (A, S)
object State {
  //This is basically "return"
  def unit[S, A](a: A): State[S, A] = s => (a, s)
}

implicit class StateOps[S, A](private runState: S => (A, S)) {
  //You can rename this to ">>=" or "flatMap"
  def *[B](k: A => State[S, B]): State[S, B] = s => {
    val (a, s2) = runState(s)
    k(a)(s2)
  }
}

If your definition of get is

set the result value to the state and leave the state unchanged (borrowed from Haskell Wiki), then you can implement it like this:

def get[S]: State[S, S] = s => (s, s)

If you mean that you want to extract the state (in this case a List[Data]), you can use execState (define it in StateOps):

def execState(s: S): S = runState(s)._2

Here's a terrible example of how you can add elements to a List.

def addToList(n: Int)(list: List[Int]): ((), List[Int]) = ((), n :: list)

def fillList(n: Int): State[List[Int], ()] =
  n match {
    case 0 => s => ((), s)
    case n => fillList(n - 1) * (_ => addToList(n))
  }

println(fillList(10)(List.empty)) gives us this (the second element can be extracted with execState):

((),List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1))

Programming a state monad in Scala

1 Answers