Rash thoughts about .NET, C#, F# and Dynamics NAV.


"Every solution will only lead to new problems."

Wednesday, 17. August 2011


Some special monads in F# – Part 5 of n – Application: Poker – Your chance to get rich!

Filed under: F#,Informatik — Steffen Forkmann at 8:52 Uhr

In the last part of this blog series I showed how we can utilize the DistributionMonad in order to solve the famous Monty Hall problem. This time I want to show you how we can use it to solve some basic Texas hold’em poker questions.

We start by defining a model for poker in F#:

As you can see we model cards as tuples of a rank and a suit. The complete deck is just a combination of all ranks with all suits.

Now we need some additional helpers for the DistributionMonad, which will allow us to draw cards from the deck. You can find further explanations about these helpers in the excellent paper by Martin Erwig and Steve Kollmansberger called "Functional Pearls: Probabilistic functional programming in Haskell". Like the DistributionMonad itself, these helpers are already in the FSharp.Monad project and you get the bits from nuget.org.

Now we are ready to perform our first query. Let’s see how we can compute the probability of drawing the Ace of Clubs and the Ace of Spades:

But we can easily go a step further:

If you keep this model in mind you might come up with a poker odds calculator on a smart phone. This might be your chance to get rich. 😉

Tags: ,

Tuesday, 16. August 2011


Some special monads in F# – Part 4 of n – Application: The Monty Hall problem

Filed under: F#,Informatik — Steffen Forkmann at 10:34 Uhr

In the last part of this blog series I showed a DistributionMonad, which allows to perform queries to probability scenarios. Today we will use this monad in order to solve the famous Monty Hall problem. This article is based on the excellent paper by Martin Erwig and Steve Kollmansberger called "Functional Pearls: Probabilistic functional programming in Haskell".

“Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what’s behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?”

[problem definition from Wikipedia]

Let’s start by modeling the first choice using the DistributionMonad:

As we can see the solution is 1/3 as we expected and if we don’t switch, we stay with these odds. But if we switch we might improve the probability for a car. Remember the host will always remove a Goat after your first pick. Let’s analyze the second pick if we switch:

Car behind First choice Temp. Outcome Host removes Switching to Outcome
Door 1 Door 1 Car Door 2 Door 3 Goat
Door 1 Door 1 Car Door 3 Door 2 Goat
Door 1 Door 2 Goat Door 3 Door 1 Car
Door 1 Door 3 Goat Door 2 Door 1 Car

If the Car is behind door 2 or door 3 the situation is symmetrical and therefor we can conclude, the following:

And if we run this, we get this nice solution:

Next time I will show how we can use the DistributionMonad to solve some basic poker scenarios.

Tags: ,

Monday, 15. August 2011


Some special monads in F# – Part 3 of n – DistributionMonad

Filed under: F#,Informatik — Steffen Forkmann at 18:41 Uhr

In part I of this blog series I showed a simple InfinityMonad, which allows to treat special calculations as infinity and in the second part I showed the UndoMonad, which defines an environment which allows to undo and redo state changes.

This and the following posts are based on a famous paper by Martin Erwig and Steve Kollmansberger called "Functional Pearls: Probabilistic functional programming in Haskell".

Let’s start by looking at a small scenario:

This simple query calculates the probability of the event, that an dice roll gives a value greater than 3 and an independent coin flip gives “Heads”. In order to do this the DistributionMonad enumerates all possibilities and calculates the joint probability using the following formula:

Probability

If we want the nice syntactic sugar we can easily define a computation expression builder:

In order to allow easier access to our monad, we define some helper functions and basic distributions for fair coins and dices:

In the next part of this blog series I will show how we can utilize the DistributionMonad in order to solve the famous Monty Hall problem.

Tags: ,

Some special monads in F# – Part 2 of n – UndoMonad

Filed under: F#,Informatik — Steffen Forkmann at 16:42 Uhr

In part I of this blog series I showed a simple InfinityMonad, which allows to treat special calculations as infinity. This time I want to demonstrate a ported version of the UndoMonad (see the Haskell version). This monad defines an environment which allows you to undo and redo state changes. You probably know this behavior from your favorite text editor.

Let’s start by using this monad in a small sample:

The definition of this monad is easy if we use the StateMonad, which is already implemented in the FSharp.Monad project (you get the bits from nuget.org). We only need to define the kind of state which should be passed through the monad.

Now we need some helpers, which allow to access and manipulate our history.

In the next part I’ll show a DistributionMonad, which allows to perform queries to probability scenarios.

Tags: ,

Some special monads in F# – Part 1 of n – InfinityMonad

Filed under: F#,Informatik — Steffen Forkmann at 15:04 Uhr

At the moment I am collecting some samples for the FSharp.Monad project (you get the bits from nuget.org) and I think I should describe some of these monads here, since they are not that common.

Today I will start with a very small monad which encapsulates infinity as a special value. I found the the idea to this specific monad at http://visualizationtools.net. Let’s start with the basic definition. Like every monad we need a container type and the two functions return and bind. Return will be used to get values into the monad and bind allows us to chain functions inside the monad.

The next thing is to create a computation expression builder which allows us to use the nice syntactic sugar in F#.

Now we can start using the monad. As a small sample we define a safe division function which treats all “division by zero” cases as infinity.

And we can use this division inside computation expressions.

Remark: You can easily define this InfinityMonad in terms of the common MaybeMonad. You can see this in the UnitTests of the FSharp.Monad project.

Next time I will show an UndoMonad which defines an environment which allows to undo and redo state changes.

Tags: ,

Friday, 23. October 2009


Using monads in F# – Part I: The State Monad

Filed under: F# — Steffen Forkmann at 10:10 Uhr

Currently I’m trying to implement some of the standard monads in F#. If you want to read about the theory behind monads and their implementation (in Haskell) it’s a good start to look into “All about Monads” on haskell.org.

In this blog post series I don’t care about mathematical details. Instead I will try to show how monads can help to simplify our code.

Motivation

We have a generic binary tree with some test data:

type Tree<‘a> =

| Leaf of ‘a

| Branch of Tree<‘a> * Tree<‘a> 

 

let tree =

  Branch(

    Leaf "Max",

    Branch(

      Leaf "Bernd",

      Branch(

        Branch(

          Leaf "Holger",

          Leaf "Ralf"),

        Branch(

          Leaf "Kerstin",

          Leaf "Steffen"))))

If we want to print this tree we can use the following recursive function:

/// prints a binary tree

let printTree t =

  let rec print t level  =

    let indent = new String(‘ ‘, level * 2)

    match t with

    | Leaf l -> printfn "%sLeaf: %A" indent l

    | Branch (left,right) ->

        printfn "%sBranch:" indent

        print left (level+1)

        print right (level+1)

  print t 0

 

printfn "Unlabeled:"

printTree tree 

And what we get is something like this:

Unlabeled:

Branch:

  Leaf: "Max"

  Branch:

    Leaf: "Bernd"

    Branch:

      Branch:

        Leaf: "Holger"

        Leaf: "Ralf"

      Branch:

        Leaf: "Kerstin"

        Leaf: "Steffen"

Labeling the tree with mutable state

Now we want to give every tree a unique label. This can be easily done by another recursive function:

let mutable label = -1

let rec labelTreeMS t =

  match t with

  | Leaf l ->

      label <- label + 1 // changing the state

      Leaf(l,label) 

  | Branch(oldL,oldR) ->

      let newL = labelTreeMS oldL

      let newR = labelTreeMS oldR

      Branch(newL,newR)        

 

let treeMS = labelTreeMS tree

printfn "Labeled (with global mutable state):"

printTree treeMS     

And the output would look like this:

Labeled (with global mutable state):

Branch:

  Leaf: ("Max", 0)

  Branch:

    Leaf: ("Bernd", 1)

    Branch:

      Branch:

        Leaf: ("Holger", 2)

        Leaf: ("Ralf", 3)

      Branch:

        Leaf: ("Kerstin", 4)

        Leaf: ("Steffen", 5)

The only problem with labelTreeMS is that it uses global state, which is very bad because we can’t be sure if the mutable label variable is changed (from maybe another thread) or not.

Labeling the tree without global state

If we want to remove this side effect, we can pass the state directly into the function:

// non-monadic version

// passing the state around explicitly

let rec labelTreeNM t s =

  match t with

  | Leaf l -> s+1,Leaf(l,s)  // changing the state

  | Branch(oldL,oldR) ->

      let stateL,newL =

        labelTreeNM oldL s

      let stateR,newR =

        labelTreeNM oldR stateL  // passing the state around

      stateR,Branch(newL,newR)              

 

let _,treeNM = labelTreeNM tree 0

printfn "Labeled (non-monadic):"

printTree treeNM

Labeling the tree by using the State Monad

With the help of the State Monad we get a very similar function:

/// labels a tree by using the state monad

/// (uses F#’s sugared syntax)

let rec labelTree t = state {

   match t with

   | Leaf l ->

       let! s = getState

       do! setState (s+1)  // changing the state

       return Leaf(l,s)

   | Branch(oldL,oldR) ->

      let! newL = labelTree oldL

      let! newR = labelTree oldR

      return Branch(newL,newR)}

 

 

printfn "Labeled (monadic):"

let treeM = Execute (labelTree tree) 0

printTree treeM

Thanks to the F# sugared syntax this labelTree and labelTreeMS are visually nearly the same. Every time we are dealing with state we use the exclamation mark. There is only one point (in the Leaf case) where have to use (and change) the state.

The nice thing is, that we can write the function like the first version, but we don’t have to perform the side effect on the shared state.

If we want to use the de-sugared version we have to write it like this:

/// labels a tree and uses de-sugared syntax

/// (implementation looks different to labelTreeNM)

let rec labelTreeDesugared t =

   match t with

   | Leaf l -> (fun s -> Leaf(l,s),(s+1))

   | Branch(oldL,oldR) ->

       labelTreeDesugared oldL >>=

        (fun newL ->

           labelTreeDesugared oldR >>=

             (fun newR ->

                 Branch(newL,newR) |> returnS))   

State monad implementation

In order to use the state monad, of course we have to implement it first. Here is my version, which allows to use the de-sugared and sugared version:

module StateMonad

 

let (>>=) x f =

   (fun s0 ->

      let a,s = x s0

      f a s)      

 

let returnS a = (fun s -> a, s)

 

type StateBuilder() =

  member m.Bind(x, f) = x >>= f

  member m.Return a = returnS a

 

let state = new StateBuilder()

 

let getState = (fun s -> s, s)

let setState s = (fun _ -> (),s) 

let Execute m s = m s |> fst

 

If you want to learn more about the State Monad I recommend watching Brian Beckman’s Channel 9 video “The Zen of Stateless State – The State Monad".

Tags: , ,