how to make these simple functions tail recursive in f#

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!


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
    

    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.

    链接地址: http://www.djcxy.com/p/14144.html

    上一篇: 为什么不是这个F#代码尾巴

    下一篇: 如何使这些简单的函数在f#中递归递归