Recursive functions in expressions of calculations

Question

First, consider some of the premises. I am currently learning some things about parser monadic combinators. Although I tried to pass the "chainl1" function from this article (p. 16-17), I came up with this solution:

let chainl1 p op = parser { let! x = p let rec chainl1' (acc : 'a) : Parser<'a> = let p' = parser { let! f = op let! y = p return! chainl1' (f acc y) } p' <|> succeed acc return! chainl1' x } 

I tested the function with some great input and got a StackOverflowException. Now I wonder if it is possible to rewrite a recursive function that uses some kind of calculation expression in such a way as to use tail recursion?

When I expand the calculation expression, I don’t see how this is even possible.

 let chainl1 p op = let b = parser b.Bind(p, (fun x -> let rec chainl1' (acc : 'a) : Parser<'a> = let p' = let b = parser b.Bind(op, (fun f -> b.Bind(p, (fun y -> b.ReturnFrom(chainl1' (f acc y)))))) p' <|> succeed acc b.ReturnFrom(chainl1' x))) 

Answer 1

In your code, the following function is not tail recursion, because - at each iteration - it makes a choice between p' or succeed :

 // Renamed a few symbols to avoid breaking SO code formatter let rec chainl1Util (acc : 'a) : Parser<'a> = let pOp = parser { let! f = op let! y = p return! chainl1Util (f acc y) } // This is done 'after' the call using 'return!', which means // that the 'cahinl1Util' function isn't really tail-recursive! pOp <|> succeed acc 

Depending on your implementation of parser combinators, the following rewriting file may work (I am not an expert here, but it might be worth a try):

 let rec chainl1Util (acc : 'a) : Parser<'a> = // Succeeds always returning the accumulated value (?) let pSuc = parser { let! r = succeed acc return Choice1Of2(r) } // Parses the next operator (if it is available) let pOp = parser { let! f = op return Choice2Of2(f) } // The main parsing code is tail-recursive now... parser { // We can continue using one of the previous two options let! cont = pOp <|> pSuc match cont with // In case of 'succeed acc', we call this branch and finish... | Choice1Of2(r) -> return r // In case of 'op', we need to read the next sub-expression.. | Choice2Of2(f) -> let! y = p // ..and then continue (this is tail-call now, because there are // no operations left - eg this isn't used as a parameter to <|>) return! chainl1Util (f acc y) } 

In general, a template works for writing tail recursive functions inside computations. Something like this will work (for expression calculations that are implemented in a way that allows tail recursion):

 let rec foo(arg) = id { // some computation here return! foo(expr) } 

As you can check, the new version matches this pattern, but the original did not.

Answer 2

In general, you can write tail recursive computation expressions (see 1 and 2 ), even with multiple let! thanks to the "delay" mechanism.

In this case, the last statement of chainl1 is what makes you think.