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

请注意,最后一种情况将适用于第二种情况适用的所有情况.这种不确定性通过案例的顺序来解决:程序将依次根据每种情况尝试匹配("查看","检查")数据,并将执行匹配的第一个案例的代码.

你似乎缺少的另一个微妙点:不变性.该列表是不可变的.您无法"更新"("更改","更改")列表.如果你有一个列表,它将始终保持这种状态,编译器保证它.相反,数据通过程序演变的方式是基于旧数据创建新数据.特别是,如果你说a :: b,这不会修改列表b,而是创建一个新的列表,其中ahead和btail.

这些都是F#中非常基本的概念,而你错过它们这一事实告诉我你刚刚开始研究这种语言(也许还有一般的函数式编程).如果这是真的,我建议先阅读一些介绍性材料,以熟悉基本概念.我最喜欢的是fsharpforfunandprofit.com,我不能推荐它.