函数式数据结构漫谈（一）
近期计划开这个系列的坑，内容大多都是“Purely Functional Data Structures”内容加一点自己的理解（改一张牌就是我的了:），算是打磨文笔？ 数据结构是什么 当我们在讨论数据结构的时候，我们在讨论什么。常见的介绍有“数据结构是一种数据组织、管理和存储的格式，它可以帮助我们实现对数据高效的访问和修改，更准确地说， 数据结构是数据值的集合，可以体现数据值之间的关系，以及可以对数据进行应用的函数或操作”。然而到更具体的场景，数据结构的概念还能够细化，比如我们经常会 讨论函数栈怎么怎么样，这里的“函数栈”也是数据结构，但它是一个泛指，是一个在程序执行过程中存在的概念，或者叫标识。Okasaki在他的“Purely Functional Data Structures”里指出，数据结构这一概念通常有四种含义： 抽象，即抽象数据类型(abstract data type，可以用Java中的interface理解)，即表示数据的类型和一组适用于该类型的函数； 实现，即对应于ADT的一个具体实现，通常是指对于该ADT做的具体设计； 实例，即在程序运行中对应于一个数据类型的具体实例； 泛指，即在程序运行中一个泛指的概念，不涉及具体的实例，例如上文提到的函数栈。 本系列将使用Haskell作为描述语言，则其中class可对应抽象的概念，data可对应实现的概念。具体到Java，可以用interface对应抽象的概念，用class对应实现 的概念。 函数式强调的是什么 抛开函数式编程本身强调的函数以外（不然就没法讲了），函数式编程通常还强调不可变（immutable）。因此，当我们说一个数据结构符合函数式的特性的时候主要在讨论不可变， 或者说持久性（persistence）。换句话说，在更新一个函数式的数据结构之后，它更新前的版本我们仍然能够访问到。这意味着所有有着破坏式更新的数据结构都不符合这一性质， 同时也表明相较于能够进行破坏式更新的数据结构，函数式数据结构的性能可能会更差，通常会有一个对数阶的更新代价在里面。实现持久性的方式非常简单，只需要将原有的数据结构 复制一遍，然后在复制后的数据结构上更新，由于没有破坏式的更，可以通过共享不变的部分来减少开销。下面讨论在函数式编程中经典的list。 List list在任何编程语言中都是非常常见的存在，函数式编程对其讨论则更多，著名的Lisp就取自“LISt Processor”。我们首先来看广泛的list定义 1 2 3 4 5 6 7 class List t where empty :: t a isEmpty :: t a -> Bool cons :: a -> t a -> t a -- error if the list is empty. head :: t a -> a tail :: t a -> t a 这里可以考虑将head和tail的结果包装一个Maybe，使之适合空的list，在这种情况下isEmpty就不再需要，因为head ls = Nothing或 tail ls = Nothing已经暗含isEmpty ls = true。本文为了偷懒就没用这种定义）。有了这些，我们就可以实现list上的各种“更高级的” 操作，例如经典的map： 1 2 3 4 map :: List t => (a -> b) -> t a -> t b map f ls = if isEmpty ls then emptll else cons (f $ head ls) (map f $ tail ls) 从这个定义上可以直接看出，这个List是不支持随机访问的。因此，我们额外定义支持“按下标”随机访问的class： ...