CODEWITHSUNDEEP
recursionf#
Khaine775
Khaine775

Reputation: 2765

F# Continuation-based tail recursion on list

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?

Upvotes: 4

Views: 1151

Answers (1)

Gus
Gus

Reputation: 26204

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.

Upvotes: 7

Related Questions