Should this sequence expression be tail-recursive?

Question

This F# seq expression looks tail-recursive to me, but I'm getting stack overflow exceptions (with tail-calls enabled). Does anybody know what I'm missing?

let buildSecondLevelExpressions expressions =
    let initialState = vector expressions |> randomize
    let rec allSeq state = seq {
        for partial in state do
            if count partial = 1
            then yield Seq.head partial
            if count partial > 1 || (count partial = 1 && depth (Seq.head partial) <= MAX_DEPTH) then
                let allUns = partial
                                |> pick false 1
                                |> Seq.collect (fun (el, rr) -> (createExpUnaries el |> Seq.map (fun bn -> add rr bn)))
                let allBins = partial  // Careful: this case alone produces result recursivley only if |numbers| is even (rightly!).
                                |> pick false 2
                                |> Seq.collect (fun (el, rr) -> (createExpBinaries el |> Seq.map (fun bn -> add rr bn)))
                yield! allSeq (interleave allBins allUns)
    }
    allSeq initialState

If you're wondering, though it shouldn't be important, pick is used to generate combinations of elements in a sequence and interleave interleaves elements from 2 sequences. vector is a constructor for a ResizeArray.

Answer 1

This is not going to be tail recursive because you could be calling recursively multiple times. To translate to a pseudo-code:

allSeq(state)
{
    foreach (partial in state)
    {
        if (...)
        {
            yield ...
        }
        if (...)
        {
            ...
            //this could be reached multiple times
            yield! allSeq(...)
        }
    }
}

Answer 2

As Gideon pointed out, this is not tail-recursive, because you still have other elements in the 'state' list to process. Making this tail-recursive isn't straightforward, because you need some queue of elements that should be processed.

The following pseudo-code shows one possible solution. I added work parameter that stores the remaining work to be done. At every call, we process just the first element. All other elements are added to the queue. When we finish, we pick more work from the queue:

let rec allSeq state work = seq { 
    match state with 
    | partial::rest -> 
        // Yield single thing to the result - this is fine
        if count partial = 1 then yield Seq.head partial 
        // Check if we need to make more recursive calls...
        if count partial > 1 || (* ... *) then 
            let allUns, allBins = // ...
            // Tail-recursive call to process the current state. We add 'rest' to 
            // the collected work to be done after the current state is processed
            yield! allSeq (interleave allBins allUns) (rest :: work)
        else
            // No more processing for current state - let's take remaining
            // work from the 'work' list and run it (tail-recursively)
            match work with 
            | state::rest -> yield! allSeq state rest
            | [] -> () //completed
    | _ -> 
        // This is the same thing as in the 'else' clause above. 
        // You could use clever pattern matching to handle both cases at once
        match work with 
        | state::rest -> yield! allSeq state rest
        | [] -> () } //completed

Answer 3

I cannot find a definition of which calls inside a sequence expression are in tail position in F# so I would strongly recommend not writing code that depends upon the semantics of the current implementation, i.e. this is undefined behaviour.

For example, trying to enumerate (e.g. applying Seq.length) the following sequence causes a stack overflow:

let rec xs() = seq { yield! xs() }

but, as Tomas pointed out, the following does actually work:

let rec xs n = seq { yield n; yield! xs(n+1) }

My advice is to always replace recursive sequence expressions with Seq.unfold instead. In this case, you probably want to accumulate the work to be done (e.g. when you recurse into a left branch you push the right branch onto the stack in the accumulator).

FWIW, even the F# language reference gets this wrong. It gives the following code for flattening a tree:

type Tree<'a> =
   | Tree of 'a * Tree<'a> * Tree<'a>
   | Leaf of 'a

let rec inorder tree =
    seq {
      match tree with
          | Tree(x, left, right) ->
               yield! inorder left
               yield x
               yield! inorder right
          | Leaf x -> yield x
    } 

Their own code kills F# interactive with a stack overflow when fed a deep tree on the left.