函数式语言中的就地算法

Question

我尝试研究更严格的编程主题，因为我意识到有很多我一无所知的范例。我遵循了《SICP》和《计算机科学基础》等书籍。我现在正在以正式的、面向证明的方式研究算法。当我学习快速排序时，我意识到我不知道如何用函数式语言实现它。这是一种就地排序算法，但如何在不发生突变的情况下实现这一点超出了我的范围。

也许有一个简单的答案，我还不知道很多实践和理论概念。但我读到函数式语言是基于 lambda 演算的，它的能力与图灵机相当。我在 Haskell 中找到了一个实现，但我不了解 monad，希望我最终能学会。

那么您能用尽可能简单的术语解释一下这是如何实现的吗？ lambda演算本身有变异的概念吗？不要对此过于严厉，因为我不太了解 lambda 演算，只是在Scheme 中编程。是或否的答案加上一点解释就足够了。

Answer 1

lambda演算本身有变异的概念吗？

不，不存在突变的概念。您只需拥有函数应用程序（apply）和函数抽象（lambda）。

Answer 2

当我学习快速排序时，我意识到我不知道如何用函数式语言来实现它。这是一种就地排序算法，但如何在不发生突变的情况下实现这一点超出了我的范围。

确实，你是对的，纯函数算法不能依赖于变异。这是因为纯函数式程序的整个想法与内存等想法无关。

你可以编写一个 Haskell 程序，如果你将它包装在 Monad 中，它确实涉及就地内存突变。这样，您就可以进行就地快速排序。来自这个博客

quicksort2 :: (Ord a) => Array Int a -> Array Int a
quicksort2 inputArr = runSTArray $ do
  stArr <- thaw inputArr
  let (minIndex, maxIndex) = bounds inputArr
  quicksort2Helper minIndex (maxIndex + 1) stArr
  return stArr

quicksort2Helper :: (Ord a)
  => Int 
  -> Int
  -> STArray s Int a
  -> ST s ()
quicksort2Helper start end stArr = when (start + 1 < end) $ do
  pivotIndex <- partition stArr start end
  quicksort2Helper start pivotIndex stArr
  quicksort2Helper (pivotIndex + 1) end stArr

最近，一些编程语言，例如 Lean 或 Roc 已经开始实现编译器优化，它可以检测某些突变是安全的情况，并自动通过突变来增强生成的代码。您可以在本文或此演讲（作者在其中讨论快速排序）中阅读相关内容。