函数式编程中的 Immutable 数据结构

  • 函数式编程中的 Immutable 数据结构已关闭评论
  • 28 次浏览
  • A+
所属分类:Web前端
摘要

原视频链接:https://www.youtube.com/watch?v=Wo0qiGPSV-s by Anjana Vakil@JSConf   函数式编程避免了很多命令式和面向对象的编程的问题。

原视频链接:https://www.youtube.com/watch?v=Wo0qiGPSV-s by Anjana Vakil@JSConf

概述

  函数式编程避免了很多命令式和面向对象的编程的问题。

  在函数中,数据输入,数据输出和数据转换就是这个函数的目的功能。

 

  与之紧密相连的,就是要避免可变性带来的副作用。所以,不变性在这里就显得很酷。

 

  假如我们有一个数组zoo,里面存放着一排数据。依次存放猴子、兔子、熊猫、狗熊、章鱼、青蛙、老虎、考拉这八个动物。而我们需要用外星人取代兔子的位置。如果直接把外星人替代兔子的位置则改变了整个数组,即触发了可变性。通常的解决办法是,将原数组zoo复制成一个新数组newZoo。再将里面的兔子替换成外星人。这样即能避免触发可变性。但不可忽略的是,当原数组越大,这一过程会占用大量的时间和空间。copying wastes time / space。因此,如果要实现不变性,我们必须找到更好的方法。

 

解决方案

关于有效地实现不变性的解决方案:

  1. 不变的数据结构!like rock,just sit.
  2. 持久数据结构

    持久数据能访问其旧版本的数据。因此,我们一直在创建新的修改版本的同时保留了旧版本。部分持久性数据结构使我们可以访问它们,但不能返回并更新其中任何数据,我们只能修改最新版本。还有完全持久性数据结构,我们可以回去更新任何过去的版本,it's version control like git.

  我们将这些统称为持久不可变数据结构,特点是持久且不变。so,what should we do?

 

  所有的这些关键是,我们想要旧的数据版本,例如上面提到的原始数组zoo,我们只是想让它保持不变,like rock. 但同时又能有效地创建新版本。所以,Trees and sharing (树结构和共享)来拯救我们了。

  想象一下,将我们的数组zoo表示为一棵树,每片叶子拥有一个值,一只动物。让我们把它们每两个放在一起。like this:

  函数式编程中的 Immutable 数据结构

结构不断上升,现在得到根是一个表示为一棵树的数组:

  函数式编程中的 Immutable 数据结构

 

  基于这种数据结构,我们如何来更新我们的数据?(用外星人来替换兔子的位置)

  鉴于我的数据是永远不变的,所以在这里我们要做的是,先找出我要更改的节点;然后创建一个副本,兔子换成了外星人;再然后需要复制所有指向该节点之上的中间层节点;相当于基本上找到一条通往根的路径,且有了新的根 called new :

  函数式编程中的 Immutable 数据结构

表示数据的另一个版本。这种复制从叶子到根节点的做法称为 路径复制(path copying)。如今我们没有复制整个数组,只需要复制从根到我改变的叶子之间的节点。因此,时间复杂度从 O(N) 变成 O(logN) ,性能更高,that's pretty cool.

  黄色部分的节点在两个版本之间共享。因此,内存的消耗变小了,因为可以重用原始的部分,且不必复制没有改变的东西。这就是所谓的结构变更,共享树的结构在两个版本之间。

  事实证明这是一种叫做 TRIE(来自“retrieval”-- 检索) 的特殊树结构。

  TRIE 是一种树,叶子代表值,到达叶子节点的路径是值相关的键值。我们可以将二进制数作为索引,我们可以 bit-by-bit 逐渐查找树,for example(找索引为 5 的青蛙):

  函数式编程中的 Immutable 数据结构

  At the same time, 当索引值很大的时候,like zoo[ 18977 ] 则对应 zoo[ 0b10001000100001 ] ,意味着这将是一棵非常深的树,有 15 层。因此,在每个层级建立更多的分支,比如我们可以将其分成 5 位,zoo -> 10010 -> 10001 -> 00001,则只有 3 层分支。这是树的深度与广度之间的取舍。研究发现 32 在深度和广度之间是一个很好的权衡。

  当我们希望非整数作为键,应该怎么做?

  它不再是数组,而是对象。like M for monkey and P for panda。此处 键 是字符串。Broaden your mind,哈希表!因此,如果我想查找 “M”关联的值,我们可以对“M”进行哈希处理,得到数字索引。So,我们根据键的二进制表示搜索树,使用了哈希函数把任意对象转换成一个数字(即索引值)。

 

  综上,可变性让人头疼,函数式编程时尤其要避免。因为函数式编程就是关于避免副作用,只使用纯函数

纯函数除了计算输入输出之外不改变任何东西,而且不变性很好。

  在 Javascript 中,有一些很棒的库可以帮助我们使用这些数据结构。如:

  • Mori

        Mori基本上是Clojure Script 的移植,作者是David Nolan。这些数据结构的实现来自Clojure Script 把 Clojure 编译成原生 JavaScript。它的API是函数式的。

  函数式编程中的 Immutable 数据结构

  函数式编程中的 Immutable 数据结构

  •  Immutable.js

Facebook推出,由Lee Byron 创建。这是一个JavaScript实现的数据结构。尽管它返回的是新版本的数据结构,而不是原位改变数据。

  函数式编程中的 Immutable 数据结构

  它不是数组,是一个JS列表

  函数式编程中的 Immutable 数据结构

 

  两者区别

  函数式编程中的 Immutable 数据结构

  


 

  感谢您的阅读,文章中如有叙述不恰当的地方望不吝赐教。