使用Writer Monad:
type Writer< 'w, 'a when 'w : (static member add: 'w * 'w -> 'w)
and 'w : (static member zero: unit -> 'w) > =
| Writer of 'a * 'w
使用 bind:
let inline bind ma fm =
let (Writer (a, log1)) = ma
let mb = fm a
let (Writer (b, log2)) = mb
let sum = ( ^w : (static member add : ^w * ^w -> ^w) (log1, log2) )
Writer (b, sum)
如果我有一个递归函数(收敛,牛顿法),每次迭代都会绑定Writer结果,我认为这不可能是尾递归的(即使从递归调用中判断出来看起来像)。
let solve params =
let rec solve guess iteration =
let (adjustment : Writer<Error,float>) = getAdjustment params guess
let nextStep adjustment =
if (abs adjustment) <= (abs params.tolerance) then
Writer.rtn guess
elif iteration > params.maxIter then
Writer (0.0, Error.OverMaxIter)
else
solve (guess + adjustment) (iteration + 1)
adjustment >>= nextStep
sovle params.guess 1
因为所有的日志都必须在递归结束之前保留在队列中(然后连接)。因此,一个问题是绑定写入器是否使递归不是尾调用。第二个问题是是否切换到Either monad:
type Result<'e, 'a> =
| Ok of 'a
| Err of 'e
使用 bind:
let bind ma fm =
match ma with
| Ok a -> fm a
| Err e -> Err e
现在将实现尾递归:
//...
let (adjustment : Result<Error,float>) = getAdjustment params guess
let nextStep adjustment =
if (abs adjustment) <= (abs params.tolerance) then
Result.rtn guess
elif iteration > params.maxIter then
Result.fail Error.OverMaxIter
else
solve (guess + adjustment) (iteration + 1)
adjustment >>= nextStep
//...
由于Either的绑定逻辑是短路的,所以
adjustment >>=
是否会保留堆栈位置?编辑:
鉴于明确的答案,我可以澄清和回答我的问题——现在问题变成了尾调用位置是否“可传递”。(1)对于
nextStep
的递归调用是在nextStep
中的尾调用。(2)对于Either
/Result
单子的bind
,(initial)调用在bind
中是一个尾调用。(3)solve
函数的外部(递归)中的bind
是一个尾调用。尾调用分析和优化是否通过这种嵌套?是的。
>>=
运算符定义为对bind
的简单调用,则行adjustment >>= nextStep
与bind adjustment nextStep
完全等效:仅当函数执行更多工作时,它将保留堆栈帧。由于此处的bind
调用位于尾部位置,因此不会有额外的堆栈帧。请参见下面的答案以获取更多信息。 - rmunnlet (>>=) ma fm = Result.bind ma fm
。 - RomnieEE