Should this sequence expression be recursive?

Question

This F # seq expression looks tail-recursive to me, but I get exceptions (with tail-calls enabled). Does anyone know what I am 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 are interested, although this should not be important, pick used to create combinations of elements in a sequence and interleave interleaves elements from two sequences. vector is a constructor for ResizeArray .

Answer 1

As Gideon pointed out, this is not a tail recursive, because you still have other elements in the "state" list to process. Performing this tail recursion is not easy because you need some queue of elements to be processed.

The following pseudo-code shows one possible solution. I added a work parameter that stores the remaining work. With each call, we process only the first element. All other items are added to the queue. When we finish, we select 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 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 2

I can’t find a definition of what calls inside the sequence expression are in the tail position in F #, so I highly recommend not writing code that depends on the semantics of the current implementation, i.e. this behavior is undefined.

For example, trying to enumerate (for example, using Seq.length ), the following sequence causes a stack overflow:

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

but, as Thomas noted, the following actually works:

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

My advice is to always replace recursive sequence expressions with Seq.unfold . In this case, you probably want to copy the work you are doing (for example, when you go to the left branch, you push the right branch onto the stack in the battery).

FWIW, even a link to the F # language is wrong. It gives the following code to align the 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 # interactively with stack overflow when it feeds a deep tree to the left.

Answer 3

This will not be tail recursive, because you can call recursively several times. To translate to pseudo code:

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