recursion - 使用 F# 递归思考

Question

我有一个函数，它需要一个 int 和一个 int 列表。它返回一个小于第一个参数的整数列表。

我想在不使用的情况下复制相同的代码List.Filter：

let less e L = 
   L |> List.filter(fun a -> a < e)

less 3 [1;2;4;5]

我想学习递归地思考，就好像我在用 SML 写这个一样

我将如何递归地写这个？

Answer 1

基本上逻辑是这样的。对于基本情况，如果列表为空，那么您就完成了。只需返回空列表。对于在头部 ( x) 和尾部 ( xs) 具有项目的列表，如果x < ereturnx附加了less应用于尾部的结果。否则，只需将返回less应用于尾部。

let rec less e L =
  match L with
  | [] -> []
  | x :: xs -> if x < e then x :: (less e xs) else (less e xs)

然而，这有点低效，因为它不是尾递归的。尾递归调用是立即返回递归调用的结果。这些更有效，因为编译器可以将它们基本上转换为循环，每次递归不会消耗额外的堆栈空间。为此，我们需要一个带有累加器的辅助函数：

let lessTailRec e L =
  let rec loop e L acc =
    match L with
    | [] -> acc
    | x :: xs -> if x < e then loop e xs (x :: acc) else loop e xs acc
  loop e L [] |> List.rev

Answer 2

我不确定这是否可以编译，因为我只是在 SO 中编写了它。此外，这当然不是最好的方法，但它会让你走上递归轨道（mike z 展示了一种更好的方法）。

let rec less e L =
    match L with
    | [] -> []
    | (head::tail) -> if head < e then (head :: less e tail) else (less e tail)

本质上，它由几个步骤组成。

首先是将头部从列表中拉出（如果它是一个空列表，则返回一个空列表）

二是比较head和e

第三是将列表的尾部发送到递归行

第四是重建列表，可选地包括列表的头部。

List.Filter 函数只是一个通用函数，它允许您注入一个函数来替换第二步并为您节省所有样板文件。通常你想在所有情况下都使用 List.Filter ，除非在学习它的作用时。