Home > Uncategorized > Poor mans state monad transformer in F#

Poor mans state monad transformer in F#

It seems like the type system of F# (and .NET) is currently not powerful enough to capture the semantics of (generic) monad transformers. The issue has been up for discussion at hubFS. One alternative is to give up generic and make explicit instantiation for the inner monads of interest. I think this approach is used by The F# Monad Library. Taking this approach for combining the State monad and the List monad has also been publish by Matthew Manela in his blog. I added methods for lift and execute and ended up having something like this:

//ref: http://www.randomhacks.net/articles/2007/03/12/monads-in-15-minutes

type ListMonad() =

   // Semantics

   member o.Return(x) = [x]

   member o.Bind(  (m:’a list), (f: ‘a -> ‘b list) ) = List.concat( List.map f m )

   member o.Zero() = []

   // Helpers

   member o.Guard(c) = if c then o.Return(()) else o.Zero()

 

// ref: http://matthewmanela.com/blog/parameterized-state-transformer-monad-in-f-2/

// ref: http://monads.haskell.cz/html/xformeranatomy.html

type StateMonadT(listM : ListMonad) =

    // Semantics

    member o.Return(v) = fun st -> listM.Return(v, st)

    member o.ReturnFrom(x) = x

    member o.Bind(m, f) =        

        fun st -> listM.Bind(m st, fun (v, st’) -> f v st’)

    member o.Zero() = fun st -> listM.Zero()

    // Helpers

    member o.Update(f) = fun st -> listM.Return(st, f st)

    member o.Get() = fun st -> listM.Return(st, st)

    member o.Set(st) = fun _ -> listM.Return((), st)

    member o.Execute(m, s0) = m s0 |> List.map fst

    member o.Lift(c) = fun st -> listM.Bind(c, fun x -> listM.Return(x,st))

 

let listM = ListMonad()

let stateMT = StateMonadT(listM)

 

I used the state monad transformer to write an n-queen program.

let rec checkHorizontal board q =

    match board with

    | x::xs -> q <> x && checkHorizontal xs q

    | _ -> true

 

let checkDiagonals board q =

    let rec checkDiagonals’ board q i =

        match board with

        | x::xs ->

            let j = i + 1

            q <> x + j && q <> x – j && checkDiagonals’ xs q j

        | _ -> true

    checkDiagonals’ (List.rev board) q 0

 

let validPositions board n = listM {

        let! q = [1..n]

        do! listM.Guard(checkHorizontal board q && checkDiagonals board q)

        return q

    }

 

#nowarn “40”

let rec addQueen = stateMT {

        let! board, n = stateMT.Get()

        if List.length board = n then

            return board

        else

            let! position = stateMT.Lift(validPositions board n)            

            do! stateMT.Set(board @ [position], n)

            return! addQueen

    }

 

stateMT.Execute(addQueen, ([],4)) |> printf “solutions: %A\n”

 

Do not take this as the best way to solve the N-queen problem (in fact I had to discard a compiler complaint, no 40, about recursion being implicit or something) but only as a sample usage of the monad transformer.

Advertisements
Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: