转向函数式编程时有哪些权衡取舍？

Question

非功能性方式: arr = [1, 2, 3]成为arr = [1, 5, 3].这里我们改变相同的数组.

在函数式编程中不鼓励这样做.我知道,由于计算机每天变得越来越快,并且存储的内存越来越多,因此函数式编程似乎更可行,以提高可读性和清晰的代码.

功能方式: arr = [1, 2, 3]没有改变arr2 = [1, 5, 3].我看到一个大趋势,我们使用更多的内存和时间来改变一个变量.

在这里,我们加倍我们的记忆和改变的时间复杂度O(1)来O(n).

对于更大的算法,这可能是昂贵的.这在哪里得到补偿？或者,由于我们可以负担得起更昂贵的计算(例如量子计算成为主流),我们是否只是为了可读性而换取速度？

Answer 1

功能数据结构不一定占用更多空间或需要更多处理时间.这里的重要方面是纯粹的功能数据结构是不可变的,但这并不意味着你总是能够完整地复制某些东西.事实上,不变性正是高效工作的关键.

我将以一个简单的列表为例.假设我们有以下列表:

列表的头部是元素1.列表的尾部是(2, 3).假设此列表完全不可变.

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

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

如果我们的列表是可变的,这将是不安全的.如果您在旧列表中更改了某些内容(例如,将元素替换2为另一个元素),则更改也会反映在新列表中.这正是可变性的危险所在:需要同步数据结构上的并发访问以避免不可预测的结果,并且更改可能会产生意外的副作用.但是,因为不可变数据结构不会发生这种情况,所以在新的结构中重复使用另一个结构的一部分是安全的.有时你希望一件事的变化反映在另一件事上; 例如,当您删除MapJava 中的键集中的条目时,您也希望删除映射本身.但在其他情况下,可变性会导致麻烦(CalendarJava中臭名昭着的类).

那么如果你不能改变数据结构本身呢？你如何制作新名单？请记住,如果我们纯粹在功能上工作,我们会使用可变指针从经典数据结构中移开,而是评估函数.

在函数式语言中,使用该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头和上面的尾巴.

(cons 0 (cons 1 (cons 2 (cons 3 nil))))

由于我们创建的函数是不可变的,因此我们的列表变得不可变.添加元素之类的事情是制作一个新函数,在正确的位置调用旧函数.以命令式和面向对象的方式遍历列表是指向从一个元素到另一个元素的指针.以功能方式遍历列表是评估函数.

我喜欢将数据结构视为:数据结构基本上是将一些算法运行的结果存储在内存中.它"缓存"计算结果,因此我们不必每次都进行计算.纯功能数据结构通过函数对计算本身进行建模.

这实际上意味着它可以非常节省内存,因为可以避免大量数据复制.随着对处理中并行化的日益重视,不可变数据结构非常有用.

编辑

鉴于评论中的其他问题,我将尽我所能添加上述内容.

我的例子怎么样？它是缺点(1 fn)并且该函数可以是缺点(2 fn2)其中fn2是cons(3 nil)而在其他情况下cons(5 fn2)？

cons与单链表相比,该功能最佳.正如您可能想象的那样,如果您获得了由cons单元格组成的列表,那么您获得的是头部,因此无法随机访问某些索引.在你的数组中,您可以arr[1]在恒定的时间内调用并获取数组中的第二项(因为它是0索引的).如果你陈述类似的东西val list = (cons 1 (cons 2 (cons 3 nil)))你不能只是在没有遍历它的情况下询问第二个项目,因为list现在它实际上是你评估的一个函数.因此访问需要线性时间,访问最后一个元素所需的时间比访问头元素要长.此外,鉴于它等同于单链表,遍历只能在一个方向上进行.因此,行为和性能更像是单链表,而不是arraylist或数组.

纯功能数据结构不一定能为某些操作(如索引访问)提供更好的性能.对于某些操作,"经典"数据结构可以具有O(1),其中功能性数据结构可以具有针对相同操作的O(log n).这是一个权衡; 功能数据结构不是银弹,就像面向对象一样.你可以在有意义的地方使用它们.如果您总是要遍历整个列表或部分列表并希望能够安全并行访问,则由cons单元组成的结构可以完美地运行.在函数式编程中,您经常使用递归调用遍历结构,在命令式编程中,您将使用for循环.

当然还有许多其他功能数据结构,其中一些更接近于建模允许随机访问和更新的阵列.但它们通常比上面的简单例子复杂得多.当然有优点:由于不变性,并行计算可以轻松实现; memoization允许我们基于输入缓存函数调用的结果,因为纯函数方法总是为相同的输入产生相同的结果.

我们实际存放在底下的是什么？如果我们需要遍历列表,我们需要一种机制来指向下一个元素吗？或者如果我想一点,我觉得遍历列表是无关紧要的问题,因为每当需要列表时,它应该每次重建？

我们存储包含函数的数据结构.什么是cons？一个简单的结构,由两个元素组成:a 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.你组成功能.将其视为建模行为而非数据.这带给我们的是

你能详细说明"纯功能数据结构通过函数对计算本身建模吗？"？

调用list.tail上面的列表会返回可以计算的内容,然后返回一个值.换句话说,它返回一个函数.如果我list.tail在那个例子中调用它(max 2 3),它显然是一个函数.评估它会产生3最大数量的参数.在这个例子中

(cons 1 (cons 2 nil))

调用tail求值为一个新的cons((cons 2 nil)一个),然后可以使用.

假设我们想要列表中所有元素的总和.在Java中,在引入lambdas之前,如果你有一个数组,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让我们定义一个函数,使用name(sum)作为参数,函数((arg))的参数列表,然后是实际的函数体(其余的).

函数体由一个eq函数组成,我们将其定义为比较它的前两个参数(arg和nil),如果它们相等,它将评估它的下一个参数((0)在这种情况下),否则后面的参数(总和).因此,(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)它们是相同的.但是,对于对象,我们通常会进行一些相等性检查(如equals()Java中).那你怎么知道一个集合是否已经包含一个元素呢？您将遍历集合中的每个元素,并检查它是否等于您要查找的元素.

hash set但是,A 为每个元素计算一些散列函数,并将具有相同散列的元素放在相应的桶中.对于良好的散列函数,存储桶中很少会有多个元素.如果您现在提供一些元素并想要检查它是否在集合中,则操作为:

1. 获取所提供元素的哈希值(通常需要恒定时间).
2. 在该集合中查找该哈希的哈希桶(再次应该花费恒定时间).
3. 检查该存储桶中是否存在与给定元素相等的元素.

要求是两个相等的元素必须具有相同的散列.

所以现在你可以在恒定时间检查集合中是否有东西.原因是我们的数据结构本身存储了一些计算信息:哈希.如果将每个元素存储在与其哈希对应的存储桶中,我们将一些计算结果放在数据结构本身中.如果我们想要检查集合是否包含元素,这将节省时间.以这种方式,数据结构实际上是在内存中冻结的计算.我们不是每次都进行整个计算,而是预先做好一些工作并重新使用这些结果.

当您认为数据结构和算法以这种方式类似时,函数可以更清楚地模拟同一事物.

请务必查看经典书籍"计算机程序的结构和插入"(通常缩写为SICP).它会给你更多的洞察力.你可以在这里免费阅读:https://mitpress.mit.edu/sicp/full-text/book/book.html