Parameterized State Transformer Monad in F#?

I have have been playing around with F# and I decided to create a state monad.  This worked out really well since I was able to leverage the F# computation expressions.  I then decided to try to extend this and make it more general by creating a parameterized state transformer monad.  This is a state monad which encapsulates another monad.  What this allow you to do is turn any computation into a statefull one.


This concept exists in Haskell which you can see here. However, my attempts at replicating this in F# failed.  Unlike in Haskell, the computation expressions in F# don’t share a common interface (or type class).  This prevents a computation from being able to generically take another computation as a parameter.  The reason is that an operation on the parameterized state transformer monad such as bind will result in a bind called on its encapsulated monad.  But since there is no interface for computations there is no bind method to call. 

I attempted to fix this by creating my own monad interface but this didn’t work:

   1: type Monad =
   2:     abstract Bind : 'm * ('a -> 'm) -> 'm
   3:     abstract Delay : (unit ->'m) -> 'm
   4:     abstract Let : 'a * ('a -> 'm) -> 'm
   5:     abstract Return : 'a -> 'm
   6:     abstract Zero : unit -> 'm
   7:     abstract Combine : 'm -> 'm2 -> 'm3
   8:     abstract Run : (unit ->'m) -> 'm


After playing with that and failing I ended up with a less than ideal solution.  Given a Maybe monad like below:

   1: // Maybe Monad    
   2: type MaybeBuilder() =
   3:     member b.Return(x) = Some x
   4:     member b.Run(f) = f()
   5:     member b.Delay(f) = f
   6:     member b.Let(p,rest) = rest p
   7:     member b.Zero () = None
   8:     member b.Combine(m1,dm2) = match m1 with
   9:                                  | None -> dm2()
  10:                                  | x -> x
  12:     member b.Bind(p,rest) = match p with 
  13:                             | None -> None
  14:                             | Some r -> rest r


I created a state transformer monad which take an argument of type m:MaybeBuilder

   1: type StateMBuilder(m:MaybeBuilder) = 
   2:     member b.Return(x) = fun s -> m.Return (x,s)
   3:     member b.Run(f) = fun inp -> (f inp)()
   4:     member b.Delay(f) = fun inp -> fun () -> f() inp
   5:     member b.Let(p,rest) = rest p
   6:     member b.Zero () = fun s -> m.Zero()
   7:     member b.Bind(p,rest) = fun s -> m.Bind(p s,fun (v,s2) -> rest v s2)
   8:     member b.Combine(p1,dp2) = fun s -> m.Combine(p1 s, dp2 s)
  10:     // State specific functions
  11:     member b.Update f = fun s -> try m.Return (s, f s) with e -> m.Zero()
  12:     member b.Read () = b.Update id
  13:     member b.Set t = b.Update (fun _ -> t)


Now although this type is technically parameterized 😉 it isn’t really the idea since its not generic, it has to be a MaybeBuilder.  To use this with a different monad I would need to change m:MaybeBuild to m:SomeOtherMonad. 

I am still going to play with this but this is as far as I have gotten.

After all of that here is how you create a state transformer monad parameterized over the maybe monad:

   1: let maybe = MaybeBuilder()
   2: let state = StateMBuilder(maybe)


If anyone has an idea how I can make this work I would love to hear it.

Comments (2)

  1. int19h says:

    Lack of type classes is a known F# deficiency. Some time ago, Don said that it’s a high-priority feature on their long-term list (which, as I understand it, means that we will not see it in 1.0, but very likely to see it in 2.0).