F# tail recursion and continuation with lists

Question

I'm struggling with some assignments in F# while I prepare for the exam.

The assignment says:

Consider the following F# declaration:

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

The type of f is int -> int list -> int list. The expression f 10 [0;1;2;3] returns the value [10;12;14;16;14].

The function f is not tail recursive. Declare a tail-recursive variant, fA, of f using an accumulating parameter.

AND

Declare a continuation-based tail-recursive variant, fC, of f.

So far I've tried something like:

let fA i = 
    let rec loop acc = function
        | [] -> acc
        | x::xs -> loop (i+x::acc) xs
    loop i []

But I just can't see why it is not working with with these. I know I miss some deeper understanding on this, so now I try all the brains in here.

Answer 1

accumulator

Well you are almost there - first you might remember that the original f has 2 arguments - so you probably should add another:

let fA i xs = ...

then the original changes i as it goes along - so you should too (add it to the loop):

let fA i xs = 
    let rec loop i acc = function

then you are almost there - you just have to call loop with the right arguments and maybe you have an order-problem ... keep trying :D

ah yes - as @Sehnsucht said - somewhere you need to have the i+1 in there ... well remember why you should take the i with your loop....

next hint

Ok seems you have some issues with your acc - well here is one more line - as you can see almost nothing changed:

let fA i xs = 
    let rec loop i acc = function
        | ???
        | x::xs -> loop (???) (???::acc) xs
    ???

obviously you have to insert (different) things into the ??? places :D

if you have still trouble you can get a compiling version like this:

let fA i xs = 
    let rec loop i acc = function
        | [] -> acc
        | x::xs -> loop i (x::acc) xs
    loop i [] xs

of course this will not work correctly but it will start you with something

continuation

you probably guessed it - the way from the accumulator-based to the continuation based is not to different (indeed this one might be easier - depending on how used you are to the backward-thinking):

start again with:

let fC i xs =
    let rec loop i cont = function

maybe you should let the compiler help you a bit if you have trouble - to do so add the type for cont like this:

let fC i xs =
    let rec loop i (cont : int list -> int list) = function

now remember that you will have to create new continuations as you go along - something like (fun res -> ...something... |> cont) to pass as the new continuations. Think of res as the result of doing my stuff with the rest of the list (your xs) then it should be easy.

For the very first continuation you will most likely don't want to do anything at all ... but this is almost always the same so you will probably know it right away.

some mean points your teacher put in

• the [] -> [i] can be nasty ... and yes you missed it right now ;) - once you got something compiling (should be your first concern) you will figure it out quite quickly I think
• i+x and i+1 ... don't mix don't forget ;)

PS: I don't want to spoil your homework to much - I'll make this into a full answer later - but it was to much/unreadable for a single comment IMO

Answer 2

I just came across this question and thought it would be nice exercise for me as well. I share the solution with hope that it will help someone. Please take it more as a humble suggestion than as the best solution. I am just an F# admirer with no education in computer science at all.

Please note that I use

let f list =
  match list with
  | ...

instead of the original and more succinct

let f =
  function
  | ...

as the former syntax makes the arguments of f visible.

The working solution is here:

// Original version
let rec f i list = 
  match list with
  | [] -> [i]
  | x::xs -> i+x :: f (i+1) xs

// Tail recursive version with accumulator
let fA i list =
  let rec loop i acc list =
    match list with
    | x::xs ->
      let newI = i + 1
      let newAcc = x + i :: acc
      let newList = xs
      loop newI newAcc newList
    | [] -> List.rev (i::acc)
  loop i [] list

// Continuation based version
let fC i list =
  let rec loop i (cont:int list -> int list) list =
    match list with 
    | x::xs ->
      let newI = i + 1
      let newCont = fun res -> cont (x + i :: res)
      let newList = xs
      loop newI newCont newList
    | [] -> cont (i::list) 
  loop i id list

// All these expressions evaluate to [10; 12; 14; 16; 14]
let res1 = f 10 [0..3]
let res2 = fA 10 [0..3]
let res3 = fC 10 [0..3]

If one of these solutions can be improved I would appreciate your comments.