F# tail recursion with monadic bind

Question

Using the 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 

with 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)

If I have a recursive function (convergence, Newton's method) with each iteration binding Writer results, I think this must not be tail recursive (even though it may look like it judged just from the recursive call):

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

because all the logs have to be held in a queue until the recursion ends (and then joined).

So one question is whether it's correct that the bind on Writer makes the recursion not a tail call. A second question is whether switching to the Either monad:

type Result<'e, 'a> = 
    | Ok of 'a
    | Err of 'e

with bind:

let bind ma fm =
    match ma with 
    | Ok a  -> fm a
    | Err e -> Err e

will make this now be tail recursive:

//...
        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
//...

Since the logic of Either's bind is short circuiting? Or could that adjustment >>= hold onto a stack position?

EDIT:

So in light of the clear answer, I can clarify and answer my question--which now amounts to something like whether tail call position is "transitive". (1) The recursive call to nextStep is a tail call in nextStep. (2) The (initial) call to nextStep is a tail call in bind (of my Either/Result monad). (3) bind is a tail call in the outer (recursive) solve function.

Does the tail call analysis and optimization carry through this nesting? Yes.

Answer 1

It's actually very simple to tell if a function call is tail-recursive: just see if the calling function needs to do other work after that call, or if that call is in tail position (i.e., it's the last thing the function does, and the result of that call is also the result returned by the calling function). This can be done with simple static code analysis, with no understanding of what the code does -- which is why the compiler is able to do it, and to produce proper .tail opcodes in the .DLL it produces.

You're correct that the bind function for Writer can't call its fm parameter in a tail-recursive way -- and the proof of that is very simple when you look at the implementation of bind that you wrote in your question:

let inline bind ma fm =
    let (Writer (a, log1)) = ma 
    let mb = fm a   // <--- here's the call
    let (Writer (b, log2)) = mb   // <--- more work after the call
    let sum = ( ^w : (static member add :  ^w * ^w -> ^w) (log1, log2) )
    Writer (b, sum)

That's all I need to look at. Because the call to fm isn't the last thing the bind function does (i.e., it isn't in tail position), I know that that call isn't tail-recursive and will use up a stack frame.

Now let's look at the bind implementation for Result:

let bind ma fm =
    match ma with 
    | Ok a  -> fm a  // <--- here's the call
    | Err e -> Err e // <--- not the same code branch
    // <--- no more work!

So in this implementation of bind, the call to fm is the last thing the function does along that code branch, and the result of fm is therefore the result of bind. So the compiler will convert the call to fm into a proper tail call, and it won't take up a stack frame.

Now let's look one level out, where you call bind. (Well, you use the >>= operator, but I assume that you've defined it as let (>>=) ma fm = bind ma fm, or something equivalent. NOTE: If your definition is significantly different than that, then my analysis below won't be correct.) Your call to bind looks like this:

let rec solve guess iteration =
    // Definition of `nextStep` that calls `solve` in tail position
    adjustment >>= nextStep

The line adjustment >>= nextStep is exactly equivalent to bind adjustment nextStep from the compiler's point of view. So for the sake of this tail-position code analysis, we'll pretend that that line is bind adjustment nextStep.

Assuming that that's the entire definition of solve and there isn't other code below that you haven't shown us, that call to bind is in tail position, so it will not consume a stack frame. And bind calls fm (which here is nextStep) in tail position. And nextStep calls solve in tail position. So you have a properly tail-recursive algorithm, and you won't blow the stack no matter how many adjustments you have to go through.