F#树构建函数导致Xamarin Studio中的堆栈溢出

Question

我试图在树结构中建立一些规则,用逻辑门即和,不,或者还有条件,例如财产X等于值ÿ.我首先编写了最明显的递归函数,它起作用了.然后,我尝试编写一个不会导致继续传递样式的堆栈溢出的版本,从这篇帖子中获取关于泛型树折叠和stackoverflow上的这个答案的提示.

它适用于小树(深度约为1000),但不幸的是,当使用Xamarin Studio在我的Mac上运行它时,使用大树会导致堆栈溢出.谁能告诉我,我是否误解了F#如何处理尾递归代码或者这个代码是否不是尾递归的？

完整的样本在这里.

let FoldTree andF orF notF leafV t data = 
    let rec Loop t cont = 
        match t with
        | AndGate (left, right)->
            Loop left  (fun lacc ->  
            Loop right (fun racc -> 
            cont (andF lacc racc))) 
        | OrGate (left, right)->
            Loop left  (fun lacc ->  
            Loop right (fun racc -> 
            cont (orF lacc racc))) 
        | NotGate exp ->
            Loop exp (fun acc -> cont (notF acc))
        | EqualsExpression(property,value) -> cont (leafV (property,value))
    Loop t id

let evaluateContinuationPassingStyle tree data = 
    FoldTree (&&) (||) (not) (fun (prop,value) -> data |> Map.find prop |> ((=) value)) tree data

Answer 1

代码是尾递归的,你做对了.但问题在于Mono.看,Mono并不像官方那样高质量地实现.NET.特别是,它不会消除尾部呼叫.就像,完全一样.

对于最简单(也是最普遍)的自递归情况,这并不重要,因为编译器会更早地捕获它.F#编译器非常聪明,可以发现函数正在调用自身,弄清楚在什么条件下,并将其转换为整齐的while循环,这样编译后的代码根本不会进行任何调用.

但是当你的尾调用是作为参数传递的函数时,编译器不能这样做,因为调用的实际函数直到运行时才知道.实际上,即使两个函数的相互递归也不能可靠地转换为循环.

可能的解决方案:

• 切换到.NET Core.
• 不要使用递归延续,而是使用累加器(可能无法实现).
• 使用自递归并传递手动维护的延续堆栈.
• 如果所有其他方法都失败了,请使用可变堆栈.