F# Continuation-based tail recursion on list

Question

I have this quite simple function which takes an int and adds it to the head of the list and is recursively called with i multiplied with itself:

let rec f i = function
    | []    -> []
    | x::xs -> (x+i)::f (i*i) xs

f 2 [1;2;3]
val it : int list = [3; 6; 19]

Now, I'm attempting to rewrite it using a continuation, but I'm a little stuck. Here's what I've come up with so far:

let fC i l =
    let rec loop cont = function
        | []    -> []
        | x::xs -> cont(x+i)::loop (fun acc -> (acc*acc)) xs
    loop id l

fC 2 [1;2;3] //Expected [3;6;19]
val it : int list = [3; 16; 25]

Any hints to what I'm doing wrong?

It's not tail recursive, but maybe will help you get there: let fC i l = let rec loop cont = function | [] -> [] | x::xs -> x+cont(i)::loop (fun acc -> cont(acc*acc)) xs loop id l — DevNewb, Dec 15 '17 at 09:36
if you read carefully answer Q from link above and the answer to you previous Q you will easily convert your function to new version — FoggyFinder, Dec 15 '17 at 10:54
@FoggyFinder it's not a duplicate, that question asks about Tail Recursive which is not exactly the same as CPS. — Gus, Dec 15 '17 at 12:12
@Gustavo yeah, but the the accepted answer contains answer for this Q too — FoggyFinder, Dec 15 '17 at 12:19
@FoggyFinder true, but still the question itself I don't consider it a duplicate, I think it can be linked, since the answer on that other question also expands on CPS. — Gus, Dec 15 '17 at 12:24
https://stackoverflow.com/questions/3248091/f-tail-recursive-function-example — FoggyFinder, Dec 15 '17 at 12:31

Gus · Accepted Answer · 2017-12-15T21:43:56.183

Looking at this questions and the comments it seems to me that there is some confusion.

Tail recursive does not necessary mean continuation passing style (CPS).

Here's the function in CPS:

let f' i p =
    let rec loop i p k =
        match p with
        | []    -> k []
        | x::xs -> loop (i*i) xs (fun a -> k ((x+i)::a))
    loop i p id

And of course, it's tail recursive. But you can also write it tail recursive by using an accumulator instead of a continuation:

let f'' i p =
    let rec loop i p acc = 
        match p with
        | []    -> acc
        | x::xs -> loop (i*i) xs ((x+i)::acc)
    loop i p [] |> List.rev

See also the answer to this question to understand better CPS.

F# Continuation-based tail recursion on list

1 Answers1