递归计算表达式

Question

在之前的一个问题中,我被告知如何重写我的计算表达式,因此它使用尾递归.我重写了我的代码,但仍然得到了StackOverflowException.为了找到问题,我使用状态monad编写了一些小代码(取自此博客条目):

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

这会再次抛出StackOverflowException,尽管Loop函数可以使用尾递归(？).我想StateBuilder类有问题.我尝试用Delay方法做一些事情.在额外的lambda中扯掉一切,但没有成功.我现在完全被困住了.这是我的第二次尝试(不编译):

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

Answer 1

我担心您可能会StackOverflowException因为您在调试模式下运行程序而禁用尾部调用生成.如果转到项目属性,则可以在" 构建"选项卡上找到" 生成尾调用"复选框.当我创建一个新项目时,我可以重现该行为,但在检查此选项后,它可以正常工作(即使迭代次数更多).

默认情况下在调试模式下禁用尾调用的原因是它使调试变得更加困难(如果调用作为尾调用执行,则不会在调用堆栈窗口中看到它)

这对于错误来说是一个非常愚蠢的原因...对不起,当你提前提问时我忘了提这个!