F # continuation based on tail recursion

Question

Can someone clarify the need for acc "" when completing a tail recursive function based on a continuation, as in the following example:

 let rec repeat_cont is acc = if i = 0 then acc "" else repeat_cont (i-1) s (fun x -> acc(s + x)) repeat_cont 4 "xo" id val it : string = "abababab" 

If the result is a list, it will be acc [] and acc 0 for an integer.

Answer 1

While the other answers provide a good background for writing continuation-style functions, they miss one important point, which, in my opinion, also makes it easier to understand how CPS works:

You do not need to call a continuation in the base case. That is, there is no need for acc "" at the completion of the recursion.

I’m sure that you understand the idiom of transferring the battery through a series of recursive calls and gradually building up the data structure in this way - say, a list or a tree. CPS is no different, except that the structure you create in the battery is a function. And since we are in a functional language, this is like a good value, returned in the base case like any other.

Compare the following example:

 let inline repeat_cont is = let rec inner is acc = if i = 0 then acc else inner (i-1) s (fun x -> acc(s + x)) inner is id let res1: string -> string = repeat_cont 4 "xo" res1 "" // "xoxoxoxo" res1 "ab" // "xoxoxoxoab" let res2: int -> int = repeat_cont 4 1 res2 0 // 4 res2 5 // 9 

I rewrote repeat_cont to use the internal recursive function to make it work with inlining in fsi, otherwise it is the very same code. You will see that its type is int -> 'a -> ('b -> 'b) , i.e. You will return the function as the result. Which in a sense is no different from returning a list or int (the usual types used for batteries), except that you can call it by giving it an initial value.

Answer 2

edit: this is called a continuation style . Each recursive call builds its continuation function and passes it to the next recursive call, which will be used as this call is selected (depending on whether it is basic or not).

---

Just write down the recovery steps:

 repeat_cont 4 "xo" id repeat_cont 3 "xo" k1 where k1 x = id ("xo" + x) repeat_cont 2 "xo" k2 where k2 x = k1 ("xo" + x) repeat_cont 1 "xo" k3 where k3 x = k2 ("xo" + x) repeat_cont 0 "xo" k4 where k4 x = k3 ("xo" + x) k4 "" k3 ("xo" + "") k2 ("xo" + ("xo" + "")) k1 ("xo" + ("xo" + ("xo" + ""))) id ("xo" + ("xo" + ("xo" + ("xo" + "")))) "xoxoxoxo" 

Each ki continuation function is “what to do with the result that will be obtained from the recursive call”.

Recursive cases, ki , say "any recursive result x that I give, add s to it and pass the increased chain up the chain as a new, changed result."

The most external, id , simply says: "Returns the (final) result as".

When the base case 0 reached, the continuation function k4 been built and is ready to accept its argument in order to do its job. He will add the string "xo" to his argument and pass the result along the chain of continuation functions to k3 . The argument will be used in "xo" + x , so it must be a string.

Adding "" to a string is an identification operation, so in the basic case it says: "Just let the chain of continuation functions do their work without any additional interference from me."

NB: I was careful to always say “continuation function” to avoid confusion with first-class continuations , which are generally different and much more powerful beasts (not sure if F # has them, though).

Answer 3

When you create a list, the elements are of the same type as the result acc .

To complete the recursion, you need a base register, so you call acc with a known value to generate something with the correct type.

Given that in your example acc = id you can replace acc "" with ""