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
I'm afraid that you may be getting StackOverflowException
because you're running the program in Debug mode with disabled tail-call generation. If you go to Project properties, then you can find Generate tail calls checkbox on the Build tab. When I create a new project, I can reproduce the behavior, but after checking this option, it works fine (even for much larger number of iterations).
The reason why tail-calls are disabled by default in the Debug mode is that it makes debugging a lot more difficult (if a call is performed as a tail-call, you wouldn't see it in the Call Stack window)
This would be a pretty silly reason for the error... sorry that I forgot to mention this when you asked earlier!
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With