递归计算表达式

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 ，因为您在调试模式下运行程序并禁用了尾部调用生成。如果您转到项目属性，则可以在构建选项卡上找到生成尾部调用复选框。当我创建一个新项目时，我可以重现该行为，但在检查此选项后，它工作正常（即使对于大量迭代）。

在调试模式下默认禁用尾部调用的原因是，它使调试变得更加困难（如果调用作为尾部调用执行，您将不会在调用堆栈中看到它 em> window）

这将是一个非常愚蠢的错误原因...抱歉，当您之前询问时我忘记提及这一点！