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)))

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 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.

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))

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 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 ()