F# 中的递归 |发生了什么事情？

Question

我找到了一个f＃递归功能的基本示例，该函数获取列表并返回仅整数的列表。我在大多数情况下都了解它，但是我对此感到困惑。

let numbers = [1..4]
let rec even ls =
   match ls with
   | [] -> []  
   |head :: tail when head % 2 = 0 -> head :: even tail
   |_::tail -> even tail 

匹配头的线使我感到困惑。这就是我阅读的方式。当头甚至在头时附加尾部，然后再次致电even tail。因为我们的头部尾巴附加了另外，我认为最后一行_::tail的意思是"什么都不做，再次恢复"，但是我在F＃中查找了操作员_，它说这是通配符模式。这本质上意味着如果我的前两场比赛中的任何一个都不涵盖，那就做这件事？

希望有人能澄清！F＃看起来很有趣，但是来自当务之急的背景很难理解。

Answer 1

这是模式匹配的表达式。读取每一行的方法是：在箭头->的左侧是如何检查数据的指示，在箭头的右边是如何处理检查结果的指示。

。

将其应用于您的情况，请按照评论(我为清晰度插入了一些新线(：

match ls with    // Look at `ls`
| [] ->        // when `ls` is an empty list,
    []         // return an empty list
| head :: tail            // when `ls` is a `head` attached to a `tail`, 
    when head % 2 = 0 ->  // AND `head` is an even number,
    head :: even tail     // call `even tail`, attach `head` to it, and return that result
| _::tail ->     // when `ls` is "something" attached to a `tail`,
    even tail    // call `even tail` and return that result

请注意，最后一个情况将适用于第二种情况的所有情况。案例的顺序解决了这种歧义：该程序将尝试根据每种情况匹配("查看"，"检查"(基准，并将执行匹配的第一个情况的代码。

您似乎缺少的另一个微妙的观点：不变性。列表是不可变的。您不能"更新"("更改"，" Alter"(列表。如果您有列表，它将始终保持这种状态，编译器可以保证它。相反，通过程序发展的方式是基于旧数据来创建新数据。特别是，如果您说a :: b，则不会修改列表b，而是创建一个新列表，其中a是头部，b是尾巴。

这些是F＃中的基本概念，而您缺少它们的事实向我表明，您刚刚开始看该语言(也许是在功能编程中(。如果这是真的，我建议您首先阅读一些介绍材料，以熟悉基本概念。我最喜欢的是fsharpforfunandprofit.com，我不能推荐它。

Answer 2

当head均匀时，将head附加到tail，然后再次致电even tail。因为我们将head附加到tail上，这不仅会被一遍又一遍地添加的循环吗？

关闭但不完全。它是预处理 head到递归even tail返回的列表中。每次递归中，此模式匹配表达式中的tail值在其中较少。

另外，最后一行_::tail我认为"什么都不做，再次重复"，但是我在F＃中查找了操作员_，它说这是通配符模式。这本质上意味着如果我的前两场比赛中的任何一个都不涵盖，那就做这件事？

_可以是通配符模式，但是在此模式匹配的示例中，它只是表明我们不在乎 head value 当我们破坏列表时；我们只关心tail。此条款(因为它是在测试均匀度的子句之后的(导致丢弃非平均值的值值。

Answer 3

您在这里处理不变的数据类型(不可变列表(。这意味着列表没有更改，每个操作都会创建并返回一个新列表。

模式匹配是将数据分解为多个部分的一种方式。举个例子。如果您有列表[1;2;3;4]，则写。

let list = [1;2;3;4]
let (head :: tail) = list

然后head是值1。tail是列表[2;3;4]，list仍然是[1;2;3;4]。

让我们逐步浏览您的示例。

even [1;2;3;4]被调用。然后有三种情况与图案匹配。第一个检查[1;2;3;4]是否是空列表。不是这样检查下一个。head :: tail将列表提取为上面的两个部分。因此，head是1，tail代表[2;3;4]，但when head % 2 = 0添加了条件。它检查head(当前1(是否可分为两个。不是，所以它是最后一个模式匹配的。

最后一个是_::tail。首先，它与head::tail完全相同。它提取第一个值1并将其存储在变量_中。使用_作为变量名称的原因是要澄清未使用的名字。您还可以将_更改为head，并且代码也相同。

最后的模式匹配匹配，现在您将1存储在_中，而[2;3;4]存储在tail中。您要做的就是致电even tail。或在这种情况下，您致电even [2;3;4]并将此功能调用的结果返回结果。

当even [2;3;4]称其为上述相同时。

它检查是否是空列表。它不是。然后，将head中的第一个值2和[3;4]提取到tail中。它检查何时条件。这次是真的。因此，现在它执行head :: even tail

，或者如果我们替换值，我们得到2 :: even [3;4]

::是列表的串联，但是在我们可以加入列表之前，首先需要函数调用even [3;4]需要返回列表。因此even [3;4]被称为。

然后再次检查。

1. 是[3; 4]一个空列表。不。
2. 是head值3可分为2。nope。
3. 将3提取到_中，将[4]提取到tail中，然后致电even [4]。

even [4]然后做同样的事情：

1. 是[4]一个空列表。不。
2. 值4是否分配给head偶数数字？是的。因此，4 :: even []被称为。

even []然后做同样的事情：

1. 是[]一个空列表。是的。因此，返回空列表。[]

然后向后。

-> means "returns"
even []         -> []
4 :: even []    -> [4]
even [3;4]      -> [4]
2 :: even [3;4] -> [2;4]
even [2;3;4]    -> [2;4]
even [1;2;3;4]  -> [2;4]