为什么 Swift 作为函数式语言很糟糕

Source: Dev.to

请提供您希望翻译的正文内容，我将为您翻译成简体中文。

Introduction

几个月前，我成为了大量裁员的众多受害者之一。
由于个人问题——其中包括在我父亲因感染 COVID 生病后照顾他——我仍在寻找工作。

在这次求职过程中，我遇到了一个对我而言相对新颖的趋势：编码测试的兴起。
我在学位期间学习了数据结构和算法，但那已经是很多年前的事了，我不太愿意承认。多年只是在数据库中存储数据并检索以显示在屏幕上，这并没有让这些技能保持锋利。

在我最近的一轮面试中，我失败的次数比我愿意承认的要多。
值得庆幸的是，我遇到了一位善良的团队负责人（是的，他们真的存在！），他给了我关于表现的宝贵反馈。
在他的指导下，我制定了一个在未来面试中取得成功的计划。但这将是另一篇文章的主题。

---

问题

我遇到的一个编码问题是 在整数数组中找到局部最大值。

• 局部最大值 是指大于其邻居的值，首尾元素只考虑一个邻居。
• 输入数组还有一个额外约束：不会出现重复值。

正确解决此问题所需的关键洞察（我在大脑某些部位严重生锈，未能自行发现）是：

如果你选择的任意一个 不是 局部最大值的数，你一定可以在比当前值更大的邻居所在的一侧找到局部最大值。

示例

let values = [5, 15, 1, 6, 8, 9, 7]

如果我们选取中间位置（6），它不是局部最大值，因为 6 …

Int? {
    guard numbers.count > 1 else { return numbers.first }

    var left = 0
    var right = numbers.count - 1

    while left < right {
        let mid = (left + right) / 2

        if (mid == 0 || numbers[mid] > numbers[mid - 1]) &&
           (mid == numbers.count - 1 || numbers[mid] > numbers[mid + 1]) {
            return numbers[mid]
        }

        // If left neighbour is greater, search the left half
        if mid > 0 && numbers[mid - 1] > numbers[mid] {
            right = mid - 1
        } else {
            // Otherwise, search the right half
            left = mid + 1
        }
    }

    return nil
}

函数式 Scala 解决方案

import scala.annotation.tailrec
import scala.collection.IndexedSeqView

def findAnyLocalMaxima(numbers: Array[Int]): Option[Int] =
  extension (numbers: IndexedSeqView[Int])
    def hasLocalMaximaAt(index: Int) =
      numbers(index) > numbers(index - 1) && numbers(index) > numbers(index + 1)

    def leftHalf = numbers.slice(0, numbers.length / 2)
    def rightHalf = numbers.slice(numbers.length / 2 + 1, numbers.length)

  @tailrec
  def findAnyLocalMaximaInView(numbers: IndexedSeqView[Int]): Option[Int] =
    numbers.length match
      case length if length > 2 =>
        val middleIndex = length / 2
        if numbers.hasLocalMaximaAt(middleIndex) then
          Some(numbers(middleIndex))
        else if numbers(middleIndex - 1) > numbers(middleIndex) then
          findAnyLocalMaximaInView(numbers.leftHalf)
        else
          findAnyLocalMaximaInView(numbers.rightHalf)

      case 2 => Some(math.max(numbers(0), numbers(1)))
      case 1 => Some(numbers(0))
      case 0 => None
  end findAnyLocalMaximaInView

  findAnyLocalMaximaInView(numbers.view)
end findAnyLocalMaxima

好吧，我承认，我在那个扩展上有点花哨，使得主代码更易读。

Functional Programming Thoughts

函数式编程强调 引用透明性 —— 只要使用纯函数，就可以用函数调用的结果替换该调用而不改变程序的行为。这与递归方法相契合，在递归中你将问题重写为更小的情况直至达到基例。因此，函数式编程更倾向于 递归调用而非循环，因为这样可以更好地表达代码的意图。

如果检查上面的函数式代码，算法的意图一目了然：

1. 检查中间值是否为局部最大值。
2. 如果不是，则递归到相应的一半。

在命令式版本中，这一意图完全丢失，因为它依赖副作用来调整索引以检查你感兴趣的数据。甚至需要注释来解释逻辑！

在 Swift 中完全函数式的弊端

一句话：栈溢出！

我敢打赌你曾经遇到过栈溢出异常。这是因为每次调用新函数时，都会在栈上压入一个帧，包含该调用的信息。因此，朴素的递归实现分而治之算法在处理大规模输入时会导致栈溢出，而迭代的 Swift 版本则能安全地保持在栈限制之内。

结论

Both solutions solve the same problem, but they illustrate a classic trade‑off:

如果你需要在函数式语言中保证不会出现栈溢出的解决方案，可以始终回退到使用显式栈或尾递归优化（当编译器支持时）。相反，如果你更喜欢递归的优雅且输入规模适中，函数式版本是对算法核心思想的精彩演示。

Source: …

Stack Overflow 和尾调用优化

当一个函数递归调用自身时，每一次调用都需要一个新的栈帧。
如果嵌套的调用太多，栈空间会耗尽，进而出现令人头疼的 stack overflow 异常。

为什么 Scala 没有这个问题

在这方面，Scala 是一种“正统”的函数式语言。
函数式编程大量依赖递归而不是循环，因此 尾调用优化（TCO） 是必不可少的。

• 有了 TCO，如果函数的最后一步操作是对自身的调用，当前的栈帧会 复用，而不是创建新的栈帧。
• @tailrec 注解（参见 findAnyLocalMaximaInView）告诉 Scala 编译器应用此优化，使得即使是潜在的无限递归调用也不会导致栈溢出。

Swift 与尾调用

Swift 有时会优化尾调用，但这种行为 没有保证。

• 调试构建（-Onone）通常会省略 TCO，导致栈溢出。
• 即使使用了优化标志 -Osize 或 -O，也 不能保证 尾调用会被优化。
  • Swift 文档中 Writing High‑Performance Swift Code 章节并未提及 TCO。
  • 早期的 Swift 论坛提案（引用了 Scala 的 @tailrec）已被关闭，未实现。

结论： 在 Swift 中使用尾递归是一场赌博——有时有效，有时无效。如果你依赖它，就在冒风险。

空间复杂度关注

编码测试同时评估 时间 和 空间 复杂度：

• 你的算法需要多少额外空间？
• 这些空间随输入规模如何增长？（常数、线性、对数、二次？）

如果函数式方法使用过多的额外空间，它可能不如命令式、可变的解决方案有吸引力。

不可变性与中间结构

函数式编程通常使用 不可变数据结构，通过管道进行转换。
每一次转换都可能创建在使用后被丢弃的中间结构。

对于分治递归：

1. 输入被分割成大约 一半大小的块，直到达到基例。
2. 然后从底部向上构建解决方案。

如果我们天真地为每次分割分配一个新数组，总的额外空间将变为 O(n)（与输入规模线性相关）。

---

Scala 与 Swift 如何避免过度分配

Swift – ArraySlice

Swift 的 Array 操作，如 prefix(_:) 或使用 Range 的下标访问，会返回 ArraySlice（或 Slice）。
这些是包装原始集合的 视图：

• 不会为元素分配额外的内存。
• 访问在时间和空间上都是 O(1)。

Scala – 视图

Scala 通过 视图 提供了类似的机制：

val view = numbers.view   // creates a view over the underlying collection

• 对视图的操作（例如 IndexedSeqView）在不分配新结构的情况下完成。
• 你可以无限次地对这些视图进行切片，同时保持 O(1) 的空间复杂度。

---

TL;DR

• 标题可能是诱导点击的，但讨论指出 Swift 仍然 落后 于真正的函数式语言。
• 如果你看到这里，可能已经认同 函数式方法：
  • 更清晰地表达算法，或者
  • 暗示 Swift 的尾递归优化并不可靠。

要点

1. Scala：@tailrec + 有保障的 TCO → 安全的递归算法。
2. Swift：尾调用优化是可选的 → 使用时需谨慎。
3. 两种语言都提供 零拷贝视图（ArraySlice / view），以保持线性或更佳的空间复杂度。

如果你对 Swift 的尾递归优化有更多了解，欢迎留言——我很想听听你的看法！