Git是纯函数式数据结构？

前言

最近看到一篇文章，标题是“Git is a purely functional data structure” , 把Git的Commit， Branch等操作和数据的不变性做了类比，很有意思，和大家分享一下。 

注意，这篇文章并不是一字一句的翻译。 

原文地址： 

https://blog.jayway.com/2013/03/03/git-is-a-purely-functional-data-structure/ 

作者：Philip Nilsson

不变性

函数式编程中有个很重要的概念就是不变性（immutablity），就是说一个对象的状态在构造完成以后不可改变。

比如有个list 是[3,2,1]，如果它是可变的，那我们就可以向头部插入一个元素4, 从而让这个列表变成[4,3,2,1]。之前的list 对我们来说丢失了，我们只能看到新的列表。

在函数式编程中，这是不应该发生的，当我们插入一个元素4的时候， 并不会修改老的列表，相反，我们会创建一个全新的列表：[4,3,2,1]， 老的列表[3,2,1]依然存在。

可能有人会想到：这个immutablity有什么好处呢？  

很重要的一点就是线程安全，一个线程对数据的修改不会影响到另外一个线程，哪些为了互斥而引入的锁就不需要了。

但是每次添加一个元素就要创建一个新的列表出来，这样做是不是很浪费、效率很低呢？

嗯，想办法做点优化，复用原来的列表吧， 就像这样：

老的列表和新的列表复用了内存中的元素，但是从外界的使用者看来，这是两个不同的列表。

如果线程要在[3,2,1]之前插入新的元素9 ， 怎么处理？  同样，还是可以复用：

如果我想把list 1中的元素3更新成元素5， 这就有点难办了，因为它会影响到两个新的列表，list 1和list 2。  没办法，只有把元素copy一下了：

（码农翻身注： 《Clojure编程》一书中有对不变性和共享存储有更多的讨论）

经过若干次操作，形成了四个列表：

老的列表： [3,2,1]

list 1: [4,3,2,1]

list 2: [9,3,2,1]

list 3: [4,5,2,1]

这四个列表对外界而言是完全独立的，只不过内部的数据是复用的。

Git vs 不变性

但是，这和Git有什么关系？和版本控制有什么关系？ 对比下不变性和版本控制：

版本控制的目的：

(1) 用新版本的文件来更新代码仓库，老版本的文件还要保留。

(2) 大家在同一个代码仓库中协作的时候，需要互不干涉。

不可变的数据结构能让我们：

(1)  保持老的数据结构不变的情况下，更新数据结构

(2)  一个线程对数据结构的更改不会影响另外一个线程

两者是不是很像？

更进一步，我们可以说Git就是一个纯函数式的、不变的数据结构，它给你提供了一个命令行客户端让你去操作。

为了完成这种类比，我们需要把上面例子中的数字替换成Commit。

假设说我们有一个代码仓库，其中的master 分支包含了三个按次序的Commit ： A， B， C。

用图来表示就是这样：

对于每个commit来讲，还有一些metadata，如comment，暂时忽略他们。

Git commit

如果我们新增一个Commit : D,  就会变成这样：

master “指针”相等于“后移”了一步， 老的history还在(即 master^)

Git amend

如果你用过Git的话，你也许知道可以使用 commit --amend来更新最近一次的Commit, 但是你真的把那个Commit给更新了吗？ 

实际上并没有，Git只是创建了一个新的Commit （下图中的E），并且让branch指针指向它而已。 通过git reflog命令，你依然能看到那个Commit （假设它的hash value 是 33b90b7）。

Git branch

正如你在上面看到的，每次你使用 commit --amend ， 你实际上创建了一个新的分支！

分支实际上就是给一个我们想引用的commit起了个名字而已。

我们甚至可以使用那个“被替换掉的”，“废弃的”Commit (33b90b7)来创建一个分支：

git checkout -b mybranch 33b90b7

所以，只要你理解了Git 是函数式数据结构的本质，你就可以“为所欲为”，从任何commit上来创建分支了。

原文还讲了Rebase/Merge和不变性的比较，我觉得就不是很贴切了，这里不再展开，感兴趣的同学可以看下原文。

总结

与其把Git描述成一个版本控制系统，不如说版本控制是“不变性”数据结构的一个自然属性。

如果以这种方式来思考的话，Git在概念上比SVN, CVS等要简单。 大家认为Git更加复杂可能是因为这种复杂性能支持更有趣的workflow。

（码农翻身注： 老刘认为Git看起来很复杂，主要是因为是分布式的，需要在本地仓库和远程仓库之间协作。）

（完）

码农翻身，用故事讲解技术本质， 更多精彩文章，请移步《码农翻身三年文章精华 》