algorithm - 进行函数式编程时需要权衡哪些方面？

Question

非功能方式:arr = [1, 2, 3]变成arr = [1, 5, 3]。在这里，我们更改相同的数组。

在函数编程中不建议这样做。我知道，由于计算机每天都在变得越来越快，并且要存储更多的内存，因此函数式编程对于提高可读性和简洁代码似乎更为可行。

功能方式:arr = [1, 2, 3]不变arr2 = [1, 5, 3]。我看到一个普遍的趋势，就是我们使用更多的内存和时间来仅更改一个变量。

在这里，我们将内存加倍，时间复杂度从O(1)更改为O(n)。

对于较大的算法，这可能会代价高昂。这在哪里补偿？还是因为我们可以负担得起更昂贵的计算费用(例如当Quantum计算成为主流时)，我们是否只是为了提高可读性而牺牲了速度？

Answer 1

功能数据结构不一定占用更多空间或需要更多处理时间。这里重要的一点是，纯功能数据结构是不可变的，但这并不意味着您总是制作某些东西的完整副本。实际上，不变性正是有效工作的关键。

我将提供一个简单列表作为示例。假设我们有以下列表:



列表的开头是元素1。列表的末尾是(2, 3)。假设此列表是完全不变的。

现在，我们要在该列表的开头添加一个元素。我们的新列表必须如下所示:



您无法更改现有列表，它是不可变的。因此，我们必须重新制作一个，对吗？但是，请注意我们新列表的尾部是(1, 2 ,3)。这与旧列表相同。因此，您可以重复使用它。新列表只是元素0，其指针指向旧列表的开头作为尾部。这是新列表，突出显示了各个部分:



如果我们的清单是可变的，那将是不安全的。如果您更改了旧列表中的某些内容(例如，将元素2替换为其他列表)，则更改也将反映在新列表中。这就是可变性的危险所在:数据结构上的并发访问必须同步，以避免不可预测的结果，并且更改可能会带来意想不到的副作用。但是，由于不变的数据结构不可能发生这种情况，因此可以安全地在新结构中重用另一结构的一部分。有时候，您希望改变一件事情以反映另一件事情。例如，当您在Java中删除Map的键集中的条目时，您也希望删除映射本身。但是在其他情况下，可变性会带来麻烦(Java中臭名昭著的Calendar类)。

那么，如果您不能更改数据结构本身，怎么办呢？您如何制作新清单？请记住，如果我们仅在功能上工作，我们将使用可变指针来摆脱经典数据结构，而是评估函数。

在功能语言中，创建列表是使用cons函数完成的。 cons使两个元素成为一个“单元”。如果要仅列出一个元素，则第二个为nil。因此，只有一个3元素的列表为:
(cons 3 nil)
如果以上是一个函数，并且您询问其head是什么，则会得到3。询问tail，您得到nil。现在，尾巴本身可以是一个函数，例如cons。

然后，我们的第一个列表表示为:
(cons 1 (cons 2 (cons 3 nil)))
询问上述函数的head，您会得到1。询问tail，您会得到(cons 2 (cons 3 nil))。

如果我们想在前面添加0，则只需创建一个新函数，其计算结果为cons，其中0为头，上面为tail。
(cons 0 (cons 1 (cons 2 (cons 3 nil))))
由于我们执行的功能是不可变的，因此我们的列表也将不可变。诸如添加元素之类的事情就是创建一个新函数，在正确的位置调用旧函数。以命令式和面向对象的方式遍历列表是通过指针从一个元素到达另一个元素。以功能方式遍历列表就是评估功能。

我喜欢这样想数据结构:数据结构基本上是在内存中存储运行某种算法的结果。 它“缓存”计算结果，因此我们不必每次都进行计算。纯功能数据结构通过功能对计算本身进行建模。

实际上，这意味着它可以提高内存效率，因为可以避免很多数据复制。随着对处理并行化的日益关注，不可变数据结构将非常有用。

编辑

考虑到评论中的其他问题，我将尽我所能在上面添加一些内容。

What about my example? Is it something like cons(1 fn) and that function can be cons(2 fn2) where fn2 is cons(3 nil) and in some other case cons(5 fn2)?

与单链列表相比， cons函数是最好的。就像您想象的那样，如果给您一个由 cons单元格组成的列表，那么您得到的只是头，因此不可能随机访问某个索引。在您的数组中，您可以只调用 arr[1]并以恒定的时间获取数组中的第二项(因为它的索引为0)。如果您声明类似 val list = (cons 1 (cons 2 (cons 3 nil)))的内容，则不能不遍历就直接询问第二个项目，因为 list实际上是您要评估的函数。因此，访问需要线性时间，并且访问最后一个元素所需的时间将比访问head元素花费的时间更长。同样，由于它等效于单链接列表，因此遍历只能在一个方向上进行。因此，其行为和性能更像是单链接列表，而不是数组列表或数组。

纯功能数据结构不一定为某些操作(例如索引访问)提供更好的性能。对于某些操作，“经典”数据结构可能具有O(1)，而功能相同的数据结构可能具有O(log n)。这是一个权衡；功能数据结构不是万灵宝，就像面向对象不是。您可以在有意义的地方使用它们。如果您总是要遍历整个列表或列表的一部分，并且希望能够进行安全的并行访问，则由 cons单元格组成的结构可以很好地工作。在函数式编程中，您经常使用递归调用遍历结构，而在命令式编程中，您将使用 for循环。

当然，还有许多其他功能数据结构，其中一些更接近于对允许随机访问和更新的数组进行建模。但是它们通常比上面的简单示例复杂得多。当然有优势:由于不变性，并行计算可以轻松实现。备忘录使我们能够基于输入来缓存函数调用的结果，因为纯函数方法对于相同的输入始终会产生相同的结果。

What are we actually storing underneath? If we need to traverse a list, we need a mechanism to point to next elements right? or If I think a bit, I feel like it is irrelevant question to traverse a list since whenever a list is required it should probably be reconstructed everytime?

我们存储包含函数的数据结构。什么是 cons？由两个元素组成的简单结构: head和 tail。只是下面的指针。在像Java这样的面向对象的语言中，您可以将其建模为 Cons类，该类包含两个在构造时分配的 最终字段 head和 tail(不可变)，并具有相应的获取方法。这是LISP变体
(cons 1 (cons 2 nil))
相当于
new Cons(1, new Cons(2, null))
在Java中。

函数语言的最大区别在于函数是一流的类型。它们可以像对象引用一样传递并分配给变量。您可以编写函数。我可以用一种功能语言轻松地做到这一点
val list = (cons 1 (max 2 3))
如果我问 list.head，我得到1，如果我问 list.tail，我得到 (max 2 3)，然后求值，结果就是3。您编写了 函数。将其视为建模行为而不是数据。这带给我们

Could you elaborate "Purely functional data structures model the computation itself via functions."?

在上面的列表中调用 list.tail将返回可以评估的值，然后返回一个值。换句话说，它返回一个函数。如果在该示例中调用 list.tail，它将返回 (max 2 3)，显然是一个函数。计算它会产生 3，因为它是参数的最大数量。在这个例子中
(cons 1 (cons 2 nil))
调用 tail会得出一个新的 cons(即 (cons 2 nil)一个)，然后可以使用它。

假设我们想要列表中所有元素的总和。在Java中，在引入Lambda之前，如果您有一个 int[] array = new int[] {1, 2, 3}数组，则需要执行以下操作

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

在功能语言中，它将类似于(简化的伪代码)

(define sum (arg)
    (eq arg nil
        (0)
        (+ arg.head (sum arg.tail))
    )
)

到目前为止，我们使用的前缀前缀表示法类似于 cons。因此 a + b被写为 (+ a b)。 define让我们定义一个函数，名称( sum)，该函数的参数列表( (arg))，然后是实际的函数主体(其余)作为参数。

该函数体由 eq函数组成，我们将其定义为比较其前两个参数( arg和 nil)，如果它们相等，则对下一个参数(在这种情况下为 (0))求值，否则对之后的参数(总和)。因此，可以将其视为带有true和false的 (eq arg1 arg2 true false)(无论您想要什么)(值，函数...)。

然后，递归位出现在总和 (+ arg.head (sum arg.tail))中。我们要说明的是，我们将参数的 head加上尾部对 sum函数本身的递归调用。假设我们这样做:

val list = (cons 1 (cons 2 (cons 3 nil)))
(sum list)

仔细地浏览最后一行将执行的操作，以了解它如何计算 list中所有元素的总和。

请注意，现在 sum是 函数的方式。在Java示例中，我们有一些数据结构，然后对其进行迭代，对其进行访问，以创建总和。在功能示例中，评估 是计算的。其中一个有用的方面是， sum作为函数可以仅在实际需要时才传递和评估。那是懒惰的评价。

数据结构和算法实际上是不同形式的同一事物的另一个示例。取一个 set。对于元素相等性的某种定义，一组只能包含一个元素的一个实例。对于整数这样的事情很简单；如果它们是相同的值(例如 1 == 1)，则它们相等。但是，对于对象，我们通常进行一些相等性检查(例如Java中的 equals())。那么如何知道集合中是否已经包含元素？您遍历集合中的每个元素，并检查其是否等于要查找的元素。

但是， hash set为每个元素计算一些哈希函数，并将具有相同哈希值的元素放在相应的存储桶中。对于一个良好的哈希函数，存储桶中很少有一个以上的元素。如果现在提供一些元素，并且想要检查它是否在集合中，则操作为:

获取所提供元素的哈希值(通常需要固定时间)。

在集合中找到该哈希的哈希存储桶(同样应该花费固定的时间)。

检查该存储桶中是否有一个元素与给定的元素相等。

要求是两个相等的元素 必须具有相同的哈希值。

因此，现在您可以检查时间是否恒定。原因是我们的数据结构本身已经存储了一些计算信息:哈希。如果将每个元素存储在对应于其哈希的存储桶中，则我们会将一些计算结果放入数据结构本身中。如果我们要检查集合是否包含元素，则可以节省时间。这样， 数据结构实际上就是冻结在内存中的计算。我们不必每次都进行完整的计算，而是预先进行了一些工作并重新使用了这些结果。

当您认为数据结构和算法以这种方式相似时，功能将如何建模相同的事物变得更加清晰。

确保检查经典书籍“计算机程序的结构和插入”(通常缩写为SICP)。它会为您提供更多的见解。您可以在这里免费阅读: https://mitpress.mit.edu/sicp/full-text/book/book.html