Back to Questions
5.5k
views7
comments
Monad the Haskell way in F#
f#haskellmonad

This topic has come up before like [link:cs.hubfs.net], though I still find it to be a great excercise to learn F#'s type system and it actually gave me some more understanding of Haskell's monad.

I have tried to mimic the Haskell version like below :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

 

let inline Bind m (f:^b -> ^c): ^c = (^a : (member Bind : (^b -> ^c) -> ^c) (m,f))
let inline Return (x:^a):(^b) = (^b : (static member Return : ^a -> ^b) x) 
let inline (>>=) (m:^a) (f:_ -> ^b): ^b =
  (^a : (member Bind: (_ -> ^b) -> ^b)(m,f))
type 'a MayBe = 
  |Some of 'a 
  |None
  with 
    member m.Bind f = 
      match m with
      | Some(a) -> f a
      | None -> None 
    static member Return x = Some x

type StateM<'s,'a> =
  |State of ('s -> 'a*'s)
  with 
    static member Return x = State (fun s -> (x,s))
    member m.RunState s = match m with State(f) -> f s
    member m.Bind (f:_ -> StateM<_,_>) =
      match m with 
      | State(sf) -> State (fun s -> let (v,s') = sf s in (f v).RunState s')
    static member get = State (fun s -> (s,s))  
    static member set s = State (fun _ -> ((),s))
        
let inv x = if x <> 0 then Return (1/x) else None    
let y = (Some 0) >>= inv >>= inv

let (/) (x:MayBe<_>) (y:MayBe<_>) = x >>= (fun x -> y >>= (fun y -> if y = 0 then None else Some (x/y)))

let tick:StateM<int,_> = 
  StateM<int,_>.get 
  >>= (fun s -> StateM<int,_>.set (s+1) >>= (fun _ -> Return s))

It does work so far but there is a few thing that I don't like and don't know if it is solvable.

1. The generic Bind and Return's type is not strict enough as instead of ^a, ^b, ^c, it really should be more like 'a IMonad,^b and 'b IMonad

2. I cannot define IMonad<'a> as follow(abstract static member is syntax error but Return in this case is IMO a static member of the type, rather than a member of an object, unlike Bind) :

1
2
3
4

 
type IMonad<'a> = interface
  abstract static member Return:
  static member Bind:

3. Even if I can, my actual implementation of the class(with IMonad interface) would encounter type problem. F# doesn't see through that my Some(x) is Maybe<'a> which implements IMonad

4. How can I make the >>= formats better

1
2
3
4
5
6

 

let tick2:StateM<int,_> = 
  StateM<int,_>.get 
  >>= (fun s -> tateM<int,_>.set (s+1) 
  >>= (fun _ -> Return s))

The above would not compile unless I indent it but that would make it unreadable if I have a few >>=, as I don't have the do notation sugar.

5. The safe divide (/) needs type annotation even though the Some (x/y) should give enough hint that x and y must be Maybe.

.

Getting one step closer but now see some fundamental difference between Haskell's do notation sugar and F#'s computation expression. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

 

let inline (>>=) m f = (^a : (member Bind: (_ -> ^b) -> ^b)(m,f))
let inline Unit x = (^b : (static member Unit : ^a -> ^b) x) 
let inline Zero () = (^a : (static member Zero : unit -> ^a) ()) 
  
type Maybe<'a> = 
  |Just of 'a 
  |Nothing
  with 
    member m.Bind f = 
      match m with
      | Just(a) -> f a
      | Nothing -> Nothing 
    static member Unit x = Just x
    static member Zero () = Nothing

type StateM<'s,'a> =
  |State of ('s -> 'a*'s)
  with 
    static member Unit x = State (fun s -> (x,s))
    member m.RunState s = match m with State(f) -> f s
    member m.Bind (f:_ -> StateM<_,_>) =
      match m with 
      | State(sf) -> State (fun s -> let (v,s') = sf s in (f v).RunState s')
    static member get = State (fun s -> (s,s))  
    static member set s = State (fun _ -> ((),s))
        
let inv x = if x <> 0 then Just (1/x) else Nothing   
 
let y = (Just 0) >>= inv >>= inv

let div (x:'a Maybe) (y:'a Maybe) = x >>= (fun x -> y >>= (fun y -> if y = 0 then Zero() else Unit (x/y)))

type MonadBuilder() =
    member inline this.Bind(m:^a when ^a :(member Bind : (^b -> ^c) -> ^c),f) = m >>= f
    member inline this.Return(x):^b = Unit x
    member inline this.Zero() = Zero()
    member inline this.ReturnFrom x = x
    
let mdo = new MonadBuilder()

let tick1 =
  mdo {
    let! n = StateM<int,_>.get
    StateM<int,_>.set (n+1) |> ignore
    return n
  }    

let safed (x:'a Maybe) (y:'a Maybe) =
  mdo {
    let! a = x
    let! b = y
    if b <> 0 then return! Just(a/b) else return! Nothing
  }  
let tick:StateM<int,_> = 
  StateM<int,_>.get 
  >>= (fun s -> StateM<int,_>.set (s+1) >>= (fun _ -> Unit s))

I need to use the 'return!' in the case of safed which is not needed in Haskell's do notation.

Would continue to see if it is possible have let! inside the mdo where it would bind to different monads which seems to be the case in Haskell.

Comments or suggestions are welcome.

By on 2/13/2010 1:36 PM ()

Nice! Here are a couple of minor tips.

  • At least on my machine, F# is inferring a non-generic type for StateM<_,_>.get - you need to annotate it with the type StateM<'s,'s> to get your tick1 example to work. Once you do this, you don't even need to specify that the 's = int in that example.
  • Since you've got a Zero method, you can drop the whole else case in safed. I think that this would be more idiomatic:
1
2
3
4
5
6
7

let safed (x:Maybe<_>) (y:Maybe<_>) =
  mdo {
    let! a = x
    let! b = y
    if b <> 0 then 
      return a/b
  }
By on 2/13/2010 2:42 PM ()

thanks!

Spot a subtle bug in tick1, which also IMO demonstrate the problem of F# approach, too much thing behind the scene. The correct version is:

1
2
3
4
5
6
7
8
9

 

let tick1 =
  mdo {
    let! n = StateM<_,_>.get
    let! _ = StateM<_,_>.set (n+1) 
    return n
  }

Without the let! _ binding, the result is different. tick.RunState 0 <> tick1.RunState 0 even though they are supposed to be the same(just sugaring). Need to read the spec to see why.

The Zero() was added solely for the version you mentioned. Though again, I find the Haskell version's explicit approach easier to follow(say 3 years later reviewing the code). I need to go through the F# spec or else I don't know there is a Zero() being done behind the scene.

The is also what I mentioned the fundamental difference. The version in F# can lead to subtle bug as above which I don't think would happen in Haskell.

By on 2/13/2010 7:07 PM ()

The version in F# can lead to subtle bug as above which I don't think would happen in Haskell.

Never use 'ignore' unless you are trying to intentionally drop a real (non-"unit") value on the floor. (You typically only use 'ignore' when working with non-pure code, e.g. .Net Framework APIs that have effects and also return values that you might or might not care about.)

In this case, you had an M<unit>, and as is pointed out, "do!" is the correct way to "run" that computation (which produces no interesting value).

By on 2/13/2010 9:29 PM ()

thanks for the advices. This bug does remind me the C situation of assigning (*) to (**) warnings etc.

The take home message is that warning cannot be simply ignored, they usually means BUG.

F#'s computational expression does give more flexibility and at the same time more repsonsibility on the shoulder of the programmer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

 

let tick0 = 
  _do {
    let! n = StateM<_,_>.get
    StateM<_,_>.set (n+1) 
    return n
  }

let tick1 =
  _do {
    let! n = StateM<_,_>.get
    do! StateM<_,_>.set (n+1) 
    return n
  }    

let tick2 = 
  _do {
    let! n = StateM<_,_>.get
    let _ = StateM<_,_>.set (n+1) 
    return n
  }    
let tick3 = 
  _do {
    let! n = StateM<_,_>.get
    let x = StateM<_,_>.set (n+1) 
    do! StateM<_,_>.set (n+2)
    do! x
    return n
  }

tick0 is a straight translation of Haskell which is a buggy version in F#. The functional equvilaent is tick1(the explicit do!). tick2 is a naive version fixing the warning(same as |> ignore I believe) which is still buggy.

tick3 is a version that demonstrate(I assume) why F# do it this way. x is as brian mentioned a computation waiting to be executed. It is done automatically(the 'execution') in the case of Haskell.

The first 3 version would compile successfully and looks like they are the same(even though they are not). Only tick3 shows everything explicitly of what is going on there.

By on 2/14/2010 3:40 PM ()

The take home message is that warning cannot be simply ignored, they usually means BUG.

Right. Be very wary of ignoring warnings (there are only a handful that are reasonable to ignore).

F#'s computational expression does give more flexibility and at the same time more repsonsibility on the shoulder of the programmer

tick0 is a straight translation of Haskell which is a buggy version in F#. The functional equvilaent is tick1(the explicit do!). tick2 is a naive version fixing the warning(same as |> ignore I believe) which is still buggy.

tick3 is a version that demonstrate(I assume) why F# do it this way. x is as brian mentioned a computation waiting to be executed. It is done automatically(the 'execution') in the case of Haskell.

The first 3 version would compile successfully and looks like they are the same(even though they are not). Only tick3 shows everything explicitly of what is going on there.

It sounds like you've got a feel for it. Inside computation expressions you can use the various syntax forms like 'do!' with values of type M<'a> that run the computation, but you can also just use ('do') expressions and 'let's (sans '!') with values of type 'a and do 'normal' programming, e.g. for side-effects. For example, the code below ends with your tick0-tick3 examples, but with extra code that uses "printf" along the way to point out the state as a way to diagnose what's happening. The flexibility of F# computation expressions makes it easy to e.g. have a "printf" line inside (without e.g. having to 'lift' the function and run it as an M<'a>), but of course this flexibility means you need to pay attention to the distinction between 'do' and 'do!' (e.g. the difference between tick0 and tick1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

 

let inline (>>=) m f = (^a : (member Bind: (_ -> ^b) -> ^b)(m,f))
let inline Unit x = (^b : (static member Unit : ^a -> ^b) x) 
let inline Zero () = (^a : (static member Zero : unit -> ^a) ()) 
  
type StateM<'s,'a> =
  |State of ('s -> 'a*'s)
  with 
    static member Unit x = State (fun s -> (x,s))
    member m.RunState s = match m with State(f) -> f s
    member m.Bind (f:_ -> StateM<_,_>) =
      match m with 
      | State(sf) -> State (fun s -> let (v,s') = sf s in (f v).RunState s')
    static member get = State (fun s -> (s,s))  
    static member set s = State (fun _ -> ((),s))
        
type MonadBuilder() =
    member inline this.Bind(m:^a when ^a :(member Bind : (^b -> ^c) -> ^c),f) = m >>= f
    member inline this.Return(x):^b = Unit x
    member inline this.Zero() = Zero()
    member inline this.ReturnFrom x = x
    
let _do = new MonadBuilder()

let tick0 = 
  _do {
    let! n = StateM<_,_>.get
    printfn "orig state: %d" n
    StateM<_,_>.set (n+1)   // warning that suggests this is a bug (it is)
    let! z = StateM<_,_>.get
    printfn "new state: %d" z
    return n
  }

let tick1 =
  _do {
    let! n = StateM<_,_>.get
    printfn "orig state: %d" n
    do! StateM<_,_>.set (n+1)   // correct
    let! z = StateM<_,_>.get
    printfn "new state: %d" z
    return n
  }    

let tick2 = 
  _do {
    let! n = StateM<_,_>.get
    printfn "orig state: %d" n
    let _ = StateM<_,_>.set (n+1) // let _ = is equiv to 'ignore', hiding the bug
    let! z = StateM<_,_>.get
    do printfn "new state: %d" z  // aside: note 'do' is typically implicit
    return n
  }    
let tick3 = 
  _do {
    let! n = StateM<_,_>.get
    printfn "orig state: %d" n
    let x = StateM<_,_>.set (n+1) // grab a computation...
    let! z = StateM<_,_>.get
    printfn "next state: %d" z
    do! StateM<_,_>.set (n+2)
    let! z = StateM<_,_>.get
    printfn "next state: %d" z
    do! x                         // ...and run it later
    let! z = StateM<_,_>.get
    printfn "next state: %d" z
    return n
  }    

printfn "tick0"
printfn "%A" <| tick0 .RunState(100)
printfn "-----"
printfn "tick1"
printfn "%A" <| tick1 .RunState(100)
printfn "-----"
printfn "tick2"
printfn "%A" <| tick2 .RunState(100)
printfn "-----"
printfn "tick3"
printfn "%A" <| tick3 .RunState(100)
printfn "-----"

displays

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

tick0
orig state: 100
new state: 100
(100, 100)
-----
tick1
orig state: 100
new state: 101
(100, 101)
-----
tick2
orig state: 100
new state: 100
(100, 100)
-----
tick3
orig state: 100
next state: 100
next state: 102
next state: 101
(100, 101)
-----
By on 2/14/2010 4:34 PM ()

I think it would probably be more typical to do it like this:

1
2
3
4
5
6

let tick1 =
  mdo {
    let! n = StateM<_,_>.get
    do! StateM<_,_>.set (n+1)
    return n
  }

It takes a while to get used to how the F# constructs are desugared, but once you do I think they have a certain elegance to them.

By on 2/13/2010 7:20 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper