list - 如何使这些简单的函数在 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# 新手 :))

当然，欢迎对我的代码提出任何其他 build 性意见!

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后面是几个空格宣言。

模式匹配案例应该遵循一致的顺序。首先从基本案例开始是个好主意。

function只要您有 fun t -> match t with 模式，关键字就很自然地用于缩短函数。 .

最好去掉不必要的括号，尤其是在只有一个参数的函数中。

应用以上注释，您的功能如下:

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