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
11:
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)
9:
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.
Anonymous
November 04, 2008
PingBack from http://mstechnews.info/2008/11/parameterized-state-transformer-monad-in-f/Anonymous
November 05, 2008
The comment has been removed