Sequence

liuxinyu95

经过了14个月锱珠积累，这一章终于脱稿了。

这一章具有里程碑式的意义。这一章写好后，所有的基本数据结构，从易到难：
二叉树，红黑树，AVL树，Trie，Patricia, Suffix tree，B-tree，binary heap，Leftist Heap, Skew Heap, 二项式heap，斐波纳契Heap，队列，序列
就全部给出了函数式实现。

我们面前已经没有任何基本数据结构的阻碍，使得我们无法用纯函数式的基本算法解决问题了！

本章是基本数据结构的最后一章。讲述sequence。
在imperative语言中，通常不用担心random access。原生的数组就可以满足O(1)时间的随机访问；然而在函数式编程中，由于使用链表作为底层的数据结构，而链表的random access是线性时间的。有没有可能提供比较满意的纯函数式sequence数据结构呢？

本章给出了一个综合性能很高的sequence实现目标，依次给出了多种尝试，最终的finger tree满足了全部的性能指标。本章一共60页，提供了Haskell, C, C++, Python等语言的例子程序。

全部内容可以在这里下载：
https://github.com/downloads/liuxinyu95/AlgoXY/sequence-en.pdf

AlgoXY全书的样稿，也假如了本章：
https://github.com/downloads/liuxinyu95/AlgoXY/main-en.pdf