了解FP：克服直觉和轻松障碍（循环与递归）-DEV365 开发者社区

ð〜讨厌阅读文章吗？查看涵盖相同内容的the complementary video。

有些人声明FP做事的方式更容易，而另一些人则说这更复杂，甚至不值得。让我探索这个。

不要太抽象了，让迭代围绕数据结构进行锚定：循环，递归和其他替代方案。

最后，我将走过解决一些面试任务，将它们捆绑在一起。

循环和递归

我认为您知道什么是循环。循环是命令编程中的一个基本概念。

这是JavaScript中典型的循环（请注意，我们将继续切换语言）。

for (let i = 0; i < 5; i++) {
  console.log(i)
}

此代码将数字从0到5。

然后是递归，在程序员中不太受欢迎，但基本上是：在数学，计算机科学和其他任何地方。

function print(n) {
  if (n < 5) {
    console.log(n)
    print(n + 1)
  } 
}

print(0)

两者都可以用来解决类似的问题。那么，哪一个更好？如果我们看一个例子怎么办？

这是一个简单的问题：给定一个具有items字段和可选parent的对象，编写一个函数来搜索needle：首先，在其items中，如果不存在，请搜索父母，换句话说，这是预期的结果：

search(40, {items:[1,40,3]}) // 40 (in items)
search(40, {items:[1,2,3], parent: {items:[1,40]}}) // 40 (in parent's items)
search(40, {items:[1,2,3], parent: {items:[1,2], parent: {items:[40]}}}) // 40
search(40, {items:[1,2,3], parent: {items:[1,2], parent: {items:[]}}}) // null

ðâ€如果搜索感觉毫无用处，请想象它正在按名称或其他物体搜索整个对象。

我们可以使用两个for-vor：
编写此书

function search(needle, scope) {
  for (let cur = scope; cur !== null; cur = cur.parent) {
    for (let i = 0; i < cur.items.length; i++) {
      const item = cur.items[i]
      if (item === needle) {
        return item
      }
    }
  return null
}

外循环：我们从当前的范围开始，并在所有父母存在时访问所有父母。
内部循环：我们浏览项目（索引从0到最后一个）。
一旦找到所需的对象，我们就会破裂；否则，我们返回nullðä·

另外，我们可以使用递归编写（我将外部环变成递归）：

function search(needle, scope) {
  for (let i = 0; i < scope.items.length; i++) {
    const item = scope.items[i]
    if (item === needle) {
      return item
    }
  }

  if (scope.parent) {
    return search(needle, scope.parent)
  } else {
    return null
  }
}

我们仍然浏览范围中的所有项目。

如果我们找不到对象并且父母存在，我们会重新启动父母的功能。
否则，我们返回nullðä·

这两项工作都没有打孔线。

直觉和轻松

即使您是功能编程场景的新手，有人可能会说服您的递归和FP一般如何优越 - 将某些FP概念或技术与替代品。

，如果您已经在FP方面有一定的经验，那么您可能会对自己感到内gui。它不断发生在我们身上：一个新的概念 - 我们想爬上最高的树以与其他所有人分享，因为它使我们的生活变得更好！

但对于新来者或旁观者来说，这并不是那么明显。为什么这个外星功能概念会更好？很常见：多年来，我一直在做X，还可以；我为什么无缘无故地重新学习？

然后我们有一个僵局。我有一个预感，这主要是由于一些误解或误解以及尝试新概念的障碍。

首先，快速扰流板，循环和递归实际上是对手；正如我稍后显示的那样，有各种循环和其他各种迭代方式。

第二，跨越直觉和轻松的障碍可能会使尝试一个新概念具有挑战性。当我们遇到一种新的做事方式时，这可能不会立即有意义。

，但我们不应该直观地掌握想法。有些概念可能很容易理解，需要很少的努力，而另一些概念可能会更复杂，并且需要更多的时间。

让我们回到迭代。让我们重新检查基本的循环和基本递归，但随后查看人们在生产中的真正作用。

循环还是不循环？

请注意，有许多不同的方法可以迭代数据结构：

for-loops;
递归;
迭代器;
列表 - 经验;
组合器/操作员/管道;
while-while-loops（你为什么要对自己这样做？）;
等。

我们已经看到了循环。这次让我们问自己，我们在编写循环时必须做出什么。

let numbers = [-1, 2, 3, 4, 5]

let sum = 0
for (let i = 0; i < numbers.length; i++) {
  sum += numbers[i]
}

console.log(`The sum is ${sum}`)
// Prints: The sum is 13

我们从哪里开始？
在这种情况下
如何迭代？或在这种情况下的步骤是什么？
在这种情况下
现在，让我们假装我们不必担心外部的状态。

因此，至少四个决定 for-loop。好吧，递归呢？

let numbers = [-1, 2, 3, 4, 5] function sumList(numbers) { if (numbers.length === 0) { return 0 } else { const [head, ...tail] = numbers return head + sumList(tail) } } console.log(`The sum is ${sumList(numbers)}`) // Prints: The sum is 13

ðâ€€递归功能包括2个部分：基础和递归情况。

基本情况是停止递归的条件。

递归情况是函数自称的地方。

在这种情况下，什么是基本情况？：如果列表为空，请返回0。

在这种情况下，什么是递归情况？：将当前数字添加到其余数字的总和中
另外：在这种情况下，我们完整传递numbers的初始输入是什么？，但是有时我们需要采用给定数据一些蓄能器。

我们必须使用递归做出更少的决定，这既不令人兴奋也不关键。至关重要的部分是我们决定的本质 - 请注意，我们从如何做的事情转变为做什么。

我们不必担心代码如何运行：从哪里开始，在哪里结束以及如何迭代；我们指定我们想实现的目标。

这是我们必须做的转变。这是功能性程序员喜欢的属性。

，但此属性与递归没有关系。让我看看这些天的语言提供的。

备择方案
例如，Rust具有更简洁的前面替代方案。这是一种总和数字的方法：

let numbers = vec![-1, 2, 3, 4, 5]; let mut sum = 0; for number in numbers { sum += number; } println!("The sum is ${sum}"); // Prints: The sum is 13

，在Scala中相同，我们可以使用for-loop或for compherens：

val numbers = List(-1, 2, 3, 4, 5) var sum = 0 for number <- numbers do sum += number println(s"The sum is $sum") // Prints: The sum is 13

此外，我们可以添加一些转换和过滤；例如，总结正数的平方：

val numbers = List(-1, 2, 3, 4, 5) var sum = 0 for number <- numbers if number > 0 square = number * number do sum += square println(s"The sum is $sum") // Prints: The sum is 54

这些结构比我们开始的JavaScript循环更具功能性 - 我们不必再担心 hows 。

另外，在两种语言中，这都是用于使用函数（或方法，操作，组合者或管道的特殊语法），或者您想称呼它的任何内容）。

ðâ€rustâsâfor-loop语法是iterators的句法糖，它负责迭代某些项目的逻辑。

ðâ€scala for complexhiens是句法糖，用于一系列对这些方法的调用：foreach，map，flatMap和withFilter，可以在任何定义这些方法的类型上使用。

因此，这些（和其他）功能通常可以直接用于更简洁的结果：

let numbers = vec![-1, 2, 3, 4, 5]; let sum: i32 = numbers .iter() .filter(|&n| *n > 0) .map(|x| x * x) .sum(); println!("The sum is ${sum}"); // Prints: The sum is 54

val numbers = List(-1, 2, 3, 4, 5) val sum = numbers.filter(_ > 0).map(n => n * n).sum println(s"The sum is $sum") // Prints: The sum is 54

我们说：将其过滤掉，将数字平整，然后将它们总结。我们不必担心集合的类型，它拥有多少元素，如何穿越等等
。
实用的演练

又名我通常如何使用递归解决问题

想象我们有一个问题：

我们有来自不同服务的响应列表。

每个响应是成功的数字或失败消息。

我们需要返回一个结果：

如果没有失败，则所有成功数字的列表，

或第一个失败的消息。

// From val responses: List[Either[String, Int]] // To val result: Either[String, List[Int]]

每个结果由Either类型表示（例如Rust中的koude20）：

Right代表成功并包含一个值（在我们的情况下，一个数字）。

Left代表故障并包含一个错误值（在我们的情况下是错误消息）。

这些是输入和输出的示例：

// If all the responses are successful List(Right(1), Right(25), Right(82)) // The result should be: // Right(List(1, 25, 82))

// If there is at least one error List(Right(1), Right(25), Left("boom"), Right(82), Left("boom 2")) // The result should be: // Left("boom")

我们从这个问题开始：递归函数的（初始）输入是什么？

我们需要所有元素吗？是的，没有办法解决。我们需要处理结果：

def process( results: List[Either[String, Int]] ): Either[String, List[Int]] = ???

我们还需要其他吗？这是一个提醒：

如果有错误，我们立即返回该元素。

如果没有错误，我们必须累积（跟踪）所有成功的值。

因此，在浏览结果时，我们必须积累一些值：我们从一个空列表开始（当我们看到成功的列表时，我们将其附加到列表中）。

def process( results: List[Either[String, Int]], accumulator: List[Int] ): Either[String, List[Int]] = ??? process(results, List.empty)

这不是最好的界面 - 不应该与内部累加器打交道。我们可以像糖果（或香肠）一样包装它，只揭露所需的东西：

def process(results: List[Either[String, Int]]): Either[String, List[Int]] = go(results, List.empty) // internal, recursive function def go( results: List[Either[String, Int]], accumulator: List[Int] ): Either[String, List[Int]] = ???

ð€â€非常普遍，请参见recursive go。

现在我们可以考虑递归案例。我们在清单上重复出现；列表要么为空（Scala中的Nil）或具有元素。此外，我们可以将列表分为 head （第一个元素）和 tail （其余元素）。让我们用骨骼展示它：

def go( results: List[Either[String, Int]], accumulator: List[Int] ): Either[String, List[Int]] = results match { case head :: rest => ??? case Nil => ??? }

什么是基本情况？当列表结束时（或者甚至没有开始），递归停止 - 当列表为空时。这意味着没有错误，我们返回成功。 accumulator应包含所有成功的值：

如果原始列表为空，则accumulator为空;

否则，accumulator包含所有数字。成功！

def go( results: List[Either[String, Int]], accumulator: List[Int] ): Either[String, List[Int]] = results match { case head :: rest => ??? case Nil => Right(accumulator) }

什么是递归情况？在每个步骤中，我们必须决定如何处理 head ， tail ，并打电话给递归。什么是头？它包含当前值，该值是成功的数字或故障消息：

def go( results: List[Either[String, Int]], accumulator: List[Int] ): Either[String, List[Int]] = results match { case Left(failure) :: rest => ??? case Right(result) :: rest => ??? case Nil => Right(accumulator) }

如果我们看失败，那就这样；我们已经完成了，我们可以将其归还 - 我们不关心列表的其余部分和累积的价值：

def go( results: List[Either[String, Int]], accumulator: List[Int] ): Either[String, List[Int]] = results match { case Left(failure) :: rest => Left(failure) case Right(result) :: rest => ??? case Nil => Right(accumulator) }

，如果成功>成功值？

我们将其添加到累加器。
我们保持递归的进行，我们必须通过列表的休息>迭代。

我们再次调用go函数，但是这次输入是列表的 rest ，累加器包含另一个成功的值：

def process(results: List[Either[String, Int]]): Either[String, List[Int]] = go(results, List.empty) def go( results: List[Either[String, Int]], accumulator: List[Int] ): Either[String, List[Int]] = results match { case Left(failure) :: rest => Left(failure) case Right(result) :: rest => go(rest, accumulator :+ result) case Nil => Right(accumulator) }

就是这样。

process(List(Right(1), Right(25), Right(82)) // Right(List(1, 25, 82)) process(List(Right(1), Right(25), Left("boom"), Right(82), Left("boom 2"))) // Left("boom")

备择方案

还记得我们如何谈论替代方案吗？

我们可以使用称为sequence的标准函数来重构process。

import cats.implicits._ def process(results: List[Either[String, Int]]): Either[String, List[Int]] = results.sequence

process(List(Right(1), Right(25), Right(82)) // Right(List(1, 25, 82)) process(List(Right(1), Right(25), Left("boom"), Right(82), Left("boom 2"))) // Left("boom")

就是这样。背后没有技巧或魔术。这是功能编程的美和力量。例如，它也可以重复使用且相当普遍，例如：

您发送了多个请求，一项服务失败了。您可以流产所有其他操作并返回失败 - 您不必等待或浪费资源。

与访问数据库相同。

解析您从前端获得的一些数据。

例如，如果将类型更改为可选值，我们不需要更改身体：

def process(results: List[Option[Int]]): Option[List[Int]] = results.sequence

最后一句话

如果您写了数千个循环，第一次写递归会很容易吗？否。

这会非常有益吗？好吧，取决于您的目标。如果您想打动同事，可能不会。如果您有长期目标或打算扩大视野？完美！

编写了数百个（或数千个）循环和递归后，我是否更喜欢递归而不是循环？是的，随时。

我更喜欢使用组合者还是更好的理解语法？是的，大多数时候。但是递归是某些工作的绝佳工具。