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 ()
IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us
Built with WebSharper