how to make these simple functions tail recursive in f#

Question

I have these these two functions

//Remove all even indexed elements from a list and return the rest
let rec removeEven l =
match l with
| x0::x1::xs -> x1::removeEven (xs)
| [] -> []
| [_] -> []

//combine list members into pairs
let rec combinePair l =
match l with
| x0::x1::xs -> (x0,x1) :: combinePair(xs)
| [] -> []
| [_] -> []

That work.

But I thought now that I was at it that I might as well learn a bit about tail recursion which I'm having a hard time getting the grasp of.

That's why I thought that if I could get some help making functions I had made myself tail-recursive perhaps it would become more clear how it works, instead of reading an example somewhere which I might not understand as well as my own code (remember, I'm a complete f# newbie :))

Any other constructive comments about my code are of course most welcome!

Answer 1

A typical way of making functions tail-recursive in F# is using a list (acc in this case) to accumulate results and reversing it to get the correct order:

let removeEven l =
    let rec loop xs acc =
        match xs with        
        | [] | [_] -> acc
        | _::x1::xs' -> loop xs' (x1::acc)
    loop l [] |> List.rev

let combinePair l =
    let rec loop xs acc =
        match xs with        
        | [] | [_] -> acc
        | x0::x1::xs' -> loop xs' ((x0, x1)::acc)
    loop l [] |> List.rev

Since we simply return results after each recursive call of loop, these functions are tail-recursive.

Your functions look quite nice, but I still have several comments:

• Indentation is important in F#. I would prefer match... with is a few spaces behind lec rec declaration.
• Patter matching cases should follow a consistent order. It's a good idea to start with base cases first.
• The function keyword is natural to use for shortening functions whenever you have a pattern of fun t -> match t with.
• It's better to get rid of unnecessary parentheses, especially in functions with one argument.

Applying above comments, your functions become as follows:

// Remove all even indexed elements from a list and return the rest
let rec removeEven = function
    | [] | [_] -> []
    | _::x1::xs -> x1::removeEven xs

// Combine list members into pairs
let rec combinePair = function
    | [] | [_] -> []
    | x0::x1::xs -> (x0, x1)::combinePair xs

Answer 2

If you need a slower, less maintainable way to do it that uses more memory, you can use a continuation.

let removeEven items = 
  let rec loop f = function
    | _::h::t -> loop (fun acc -> f (h::acc)) t
    | [] | [_] -> f []
  loop id items

But hey, it's tail-recursive.