In a previous question I was told how to rewrite my computation expressions so it uses tail recursion. I rewrote my code but still got a StackOverflowException. To locate the problem I wrote some small code using a state monad (taken from this blog entry):
type State<'a, 's> = State of ('s -> 'a * 's)
let runState (State s) initialState = s initialState
let getState = State (fun s -> (s,s))
let putState s = State (fun _ -> ((),s))
type StateBuilder() =
member this.Return a = State (fun s -> (a, s))
member this.Bind(m, k) =
State (fun s -> let (a,s') = runState m s in runState (k a) s')
member this.ReturnFrom a = a
let state = new StateBuilder()
let s max =
let rec Loop acc = state {
let! n = getState
do! putState (n + 1)
if acc < max then
return! Loop (acc + 1)
else return acc
}
Loop 0
runState (s 100000) 0
This is throwing a StackOverflowException again, although the Loop function could use tail recursion(?). I guess something is wrong with the StateBuilder class. I tried to do something with the Delay method. Wraping everything in an extra lambda, without success. Im totally stucked at the moment. Here my second attempt (does not compile):
type State<'a, 's> = State of ('s -> 'a * 's)
let runState (State s) initialState = s initialState
let getState = fun () -> State (fun s -> (s,s))
let putState s = fun () -> State (fun _ -> ((),s))
type StateBuilder() =
member this.Delay(f) = fun () -> f()
member this.Return a = State (fun s -> (a, s))
member this.Bind(m, k) =
fun () -> State (fun s -> let (a,s') = runState (m ()) s in runState ((k a) ()) s')
member this.ReturnFrom a = a
let state = new StateBuilder()
let s max =
let rec Loop acc = state {
let! n = getState
do! putState (n + 1 - acc)
if acc < max then
return! Loop (acc + 2)
else return acc
}
Loop 0
runState (s 100000 ()) 0
