F#中的递归发生了什么? [英] Recursion in F# | What's happening?

问题描述

我找到了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#看起来很有趣，但是由于其必不可少的背景，很难理解.

解决方案

这是一个模式匹配表达式.读取每一行的方式是这样的:箭头->的左侧是如何检查数据的指令，箭头的右侧是如何处理检查结果的指令.

将此应用于您的案例，请遵循注释(为清楚起见，我插入了一些换行符):

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，而是创建一个新列表，其中a是头，b是尾.

这些是F#中非常基本的概念，而您遗漏了它们的事实向我表明，您才刚刚开始研究该语言(也许一般来说是函数式编程).如果是这样，我建议您先阅读一些入门资料，以熟悉基本概念.我最喜欢的是 fsharpforfunandprofit.com ，我推荐得还不够.

I've found a basic example of an f# recursive function that takes a list and returns a list of only even integers. I understand it for the most part, but there's a little i'm confused about.

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

The line that matches head confuses me. This is how I read it. Append head to tail when head is even, then call even tail again. Because we appended head to tail, wouldn't that just get caught in a loop of adding head over and over again?
Also, the final line _::tail I assume means "do nothing, recurse again", but I looked up the operator _ in f# and it says it's a wildcard pattern. Does that essentially mean if not covered by either of my first two matches, do this thing?

Hoping someone can clarify! f# looks like a lot of fun, but coming from an imperative background it's difficult to understand.

解决方案

This is a pattern matching expression. The way to read each line is this: to the left of the arrow -> is the instruction of how to inspect the data, and to the right of the arrow is the instruction of what to do with the results of inspection.

Applying this to your case, follow the comments (I've inserted some newlines for clarity):

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

Note that the very last case will apply in all situations in which the second case applies. This ambiguity is resolved by the order of the cases: the program will attempt to match ("look at", "inspect") the datum according to each case in turn, and will execute code for the first case that matches.

Another subtle point that you seem to be missing: immutability. The list is immutable. You cannot "update" ("change", "alter") the list in place. If you have a list, it will always stay that way, the compiler guarantees it. Instead, the way data evolves through the program is by creating new data based on the old ones. In particular, if you say a :: b, this does not modify the list b, but instead creates a new list, in which a is head and b is tail.

These are pretty basic concepts in F#, and the fact that you're missing them suggests to me that you've only just started looking at the language (and perhaps at functional programming in general). If this is true, I recommend first reading some introductory material to familiarize yourself with basic concepts. My favourite is fsharpforfunandprofit.com, I can't recommend it enough.

这篇关于F#中的递归发生了什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！