如何在f#中使这些简单的函数尾部递归

Question

我有这两个函数

//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)
| [] -> []
| [_] -> []

那工作。

但我想，现在我已经在做了，我还不如学习一些关于尾部递归的知识，我很难掌握它。

这就是为什么我想，如果我能得到一些帮助来制作我让自己尾递归的函数，也许它的工作原理会变得更清楚，而不是在我可能不太理解的地方读一个例子，就像我自己的代码一样（记住，我是一个完全的f#新手：））

当然，欢迎对我的代码发表任何其他建设性的意见！

Answer 1

F#中使函数尾部递归的一种典型方法是使用列表（在本例中为acc）来累积结果，并将其反转以获得正确的顺序：

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

由于我们只是在每次递归调用loop之后返回结果，所以这些函数是尾部递归的。

你的功能看起来很不错，但我仍然有几个评论：

• 缩进在F#中很重要。我更希望match... with在lec rec声明后面有几个空格
• 模式匹配案例应遵循一致的顺序。先从基本情况开始是个好主意
• 无论何时使用fun t -> match t with模式，function关键字都很自然地用于缩短函数
• 最好去掉不必要的括号，尤其是在只有一个参数的函数中

应用以上评论，您的功能如下：

// 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

如果您需要一种更慢、更不易维护、使用更多内存的方法，可以使用continuation。

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

但是嘿，这是尾部递归。