Recursive expression expressions

Question

In a previous question, I was told how to rewrite my calculation expressions so that it uses tail recursion. I rewrote my code but still got a StackOverflowException. To find the problem, I wrote a short code using the state monad (taken from this blog post ):

type State<'a, 's> = State of ( -> '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 ms in runState (ka) 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 again raises a StackOverflowException, although the Loop function can use tail recursion (?). I think something is wrong with the StateBuilder class. I tried to do something using the Delay method. Shake everything in extra lambda, without success. I am completely stuck at the moment. Here is my second attempt (not compiling):

 type State<'a, 's> = State of ( -> '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 ((ka) ()) 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 

Answer 1

I am afraid that you might get a StackOverflowException because you are running the program in debug mode with the tail call generation turned off. If you go to the project properties, you can select the Create Tails check box on the Assembly tab. When I create a new project, I can reproduce it, but after checking this parameter it works fine (even for a much larger number of iterations).

The reason debugging is disabled by default in Debug mode is that debugging is much harder (if the call is run as a tail call, you won’t see it in the Call Stack window)

That would be a pretty stupid reason for the mistake ... sorry I forgot to mention this when you asked before!