在函数式语言中，不变性的概念如何应用于内存中的地址？

Question

我试图理解很多基本的计算机科学概念是如何在函数式语言中实现的。我目前不能理解的一点是函数式语言和哲学是如何处理内存中的地址的。

在像排序这样非常基础的计算机科学概念的背景下，如何有效地处理不变性问题？我知道结构化共享对于防止内存爆炸是非常必要的。但在我看来，这意味着像选择排序这样相对简单的概念可能会变得相当复杂。

有人能解释一下函数式语言是如何就地处理排序的吗？“就地”的想法被抛弃了，取而代之的是支持结构化共享的数据结构吗？

我真的在试着理解不变性是如何与内存中的地址相适应的(想想指针)。例如，在就地排序中，数据不会被销毁，但会被移动到新地址。这算不算突变？我认为答案是肯定的。但是你如何做像旋转这样的事情来平衡二叉树呢？函数式程序员是如何看待指针的？

我知道这是一个相对很难回答的问题，但我觉得这是一个真正理解函数范式的大问题。我们将非常感谢您的任何见解或资源。

Answer 1

1. 只是为了解决这个问题：

例如，在就地排序中，数据不会被销毁，但会移动到新地址。

这没有任何意义。如果数据被“移动到新地址”，根据定义，算法将不再“就地”工作。

1. 函数式编程语言有着悠久的传统，它并不坚持100%的纯洁性。从Lisp开始，在ML之上，然后是OCaml、Scala或Clojure --所有这些语言都有可变的数据结构。在具有函数式编程特性的“多范式”语言中，例如JavaScript和Python，甚至Java，您也可以使用可变的数据结构。
2. 大多数函数式编程语言更喜欢持久化数据结构和处理不可变数据结构的算法。也就是说，这些语言通常更喜欢某种平衡排序树，而不是可变的哈希表，而不是可变的列表缓冲区，它们更喜欢不可变的单链表。为了对这些列表进行排序，您可以使用merge-sort，它可以很好地表达为纯函数式程序(但不是适当的，至少不需要一些额外的工作)。
3. 即使您坚持纯净，您仍然可以将计算机的可变内存视为可变“外部世界”的另一部分-就好像它是某种用户输入-输出、系统时钟、网络通信或随机数生成器。也就是说，要以纯函数的方式处理可变内存，您需要两个组件:首先，您需要一种方法，通过构造一个不可变的“计划”来描述如何处理可变内存；然后，您将需要一个解释器，该解释器可以接受这个不可变的计划，并将其应用于实际的可变内存块。也就是说，改变记忆的解释器在某种程度上处于语言核心之外，并且被视为“外部可变世界”的任何其他部分。
4. 在不坚持纯洁性的语言中，您既可以实现用于构造不可变计划的特定于域的小语言，也可以实现实际上改变内存的解释器，从而将纯部分与不纯的副作用可变部分分开。例如，Chiusano & Bjarnason在他们的书"Functional programming in Scala“中有一个第14.2.5章的字面意思是”在静态类型的函数式编程中，一个纯粹的函数式就地quicksort".
5. In general，不变性本身并不是目标。更确切地说，目标是确保半后端可变数据结构不会逃脱算法的狭窄范围，对于该算法来说，可变性是有利的。如果您找到了一种方法来确保这一点，那么这意味着您可以编写使用可变内存的纯函数式程序。

Answer 2

你的困惑来自混杂的抽象层次。

在您最喜欢的OO垃圾收集语言(Python、Java、Ruby等)中，内存分配是如何处理的？你不知道。该细节留给编译器和/或运行时。您混淆了编程语言的语义和该语言的编译器的实现细节。我承认C/C++模糊了很大的区别，但这种模糊可能是这些语言在这一点上最突出的特征。

考虑一种常见的关联数据结构，即C结构：

struct address 
{ 
   char number[10]; 
   char street[100]; 
   char city[50]; 
   char state[15]; 
};

我们预先知道，这在内存中会是什么样子。但是考虑一下类似的数据结构，比如Java：

public class Record {
  public int number;
  public String street;
  public String city;
  public String state;
}

这将如何在内存中进行布局？你不知道。即使你用字符缓冲区替换字符串，你也不会真正知道。显然，javac让这一切发生了。这与函数式语言中的持久化数据结构没有什么不同:将内容放到内存中的位置取决于编译器，而编译器并不受它正在编译的语言的语义的约束。