第1页 第一章翻译（很水）

　　当一个C程序员需要一个高效的数据结构来解决问题时，他只需随意找一本手册或课本。
　　不幸的是，使用ML或Haskell等函数式语言的程序员没有这样的奢侈。虽然那些数据结构书旨在所说语言独立，不幸的是他们的语言独立只是亨利·福特意义上的：程序员可以使用任何他们想要的语言，只要它是命令式语言。为了纠正这种不平衡，这本书将以函数式语言的视角介绍数据结构。
　　我们在例子中使用标准ML，并且很容易转换成其他函数式语言版本比如Haskell或Lisp的。在附录A中提供了范例的Haskell版本。

　　1.1 函数式数据结构 vs. 指令式数据结构
　　使用函数式语言的好处是众所周知的[Bac78，hug89，HJ94]但是绝大多数程序员仍在使用C这样的指令式语言。这个看似矛盾的事实很容易解释，因为一直以来函数式语言比指令式语言运行的慢。但是这个差距正在缩小。得益于编译器技术和精巧的分析和优化，函数式语言的运行速度已经取得了令人印象深刻的进步。然而，还有另一个编译器无法解决的问题——使用劣质或不适当的数据结构。不幸的是，还没有很多这方面的书。
    为什么设计函数式语言数据结构比指令式语言的更难呢？有两个基本的问题。首先，从设计高效的数据结构的观点来看，没有破坏性更新（destructive
 updates）的函数式语言本来就不好设计，无异于没收一个师傅的刀。就像刀一样，破坏更新误用时，可能会有危险，但恰当使用时就极其有效。
    指令式数据结构的实现常常依赖基于破坏性更新来实现的特定方法，所以函数式数据结构必须要另辟蹊径。
    第二个困难是我们希望函数式数据结构比指令式的更加灵活好用。特别是，当我们更新指令式数据结构，我们通常接受之前的数据结构将不再可用，但当我们更新函数式数据结构时，我们要求原版和新版本的数据结构都可用，以供后续处理。
　　　同时支持多个版本的数据结构是persistent的,只支持一个版本的数据结构是ephemeral 的[ DSST89 ]。函数式数据结构就有这种神奇的性质，即所有的数据结构自动是persistent的指令式数据结构是典型的ephemeral 的。但是当需要persistent数据结构时，指令式程序员也会允许性能变差。
　　　此外，理论家已经建立了一个下界表明：在一定情况下，函数式语言就是要比指令式语言更慢[BAG92, Pip96]。按照所有这些观点，函数式数据结构有时就像是“跳舞的熊”——”要点不是他跳的有多好，而是他毕竟能跳舞！”在实际中，情况没那么惨。我们将会看到：我们经常有可能设计出和指令式一样高效的函数式数据结构！

　　1.2 严格求值 vs. 惰性求值
　　根据求值顺序，大多数(连续)函数式语言可被归类为严格求值或惰性求值。
哪种求值更好有时会被函数式程序员以宗教式的热情讨论。两种求值最明显的区别是他们对函数和参数的处理。在严格求值中，函数的参数在函数被求值之前求值。在惰性求值中，参数以需求驱动的方式求值，希望能做到尽量传递未求值的参数，当且仅当计算需要求值才能继续时才求值。此外，一旦一个参数被求值了，这个值就会被缓存，当再次需要这个值时，就可以查找这个值而不是重新计算这个值。这种暂存技术被称为备忘——memoization[Mic68]。
　　每个求值顺序都有其优点和缺点，但至少在一个方面严格求值有明显的优势：容易求渐进的的复杂度。在严格语言中，仅靠语法分析，何时哪个子表达式将被求值是显而易见的。因此，求给定程序的运行时间也相对简单。与之相对，惰性求值语言，即使是专家有时也很难预测一个给定的子表达式的运行时间。
惰性语言程序员往往假设其语言是严格语言，以此来粗略的估计运行时间。
　　1.3术语学
　　任何对数据结构的讨论都隐含着潜在的混乱，因为数据结构这个术语至少有四个不同的，但相关的含义。
一个抽象的数据类型（即，一个类型和操作该类型的一系列函数）。
我们将把这个概念称作“抽象”（abstraction）。
一抽象类型的具体实现。
我们将把这个概念称作“实现”（implementation），但要注意实现，不一定是现实代码，结构设计就足够了。
一个类型的实例，比如一个特定的表或树。
我们将把这样的实例一般地作为“对象”（object）或“版本”（version）。要注意，特定的数据类型往往有自己的术语。例如，我们将把堆栈或队列对象只称为堆栈或队列。
一种不随更新操作改变的独特性质。
例如，在一个基于堆栈的解释器中，我们常常不严谨的认为只有“一个堆栈”，而事实上不同时候堆栈有着不同的版本。我们把这个性质称作persistent（持久）性质。
这个问题主要在持久性数据结构中讨论，如果不同版本共享同一持久性质，我们就说这些不同版本是同一数据结构。
　　粗略地说，在标准ML（standard ML）语言中Abstraction（抽象）对应于signature（签名），Implementation（实现）对应于structure或functor。
　　“操作”（operation）这个术语也有类似的多重含义，既指抽象类型提供的函数又指这些函数的应用。约定在本书中“操作”指代函数的应用这个含义。
　　1.4	 途径
    本书不会为提供足以实现所有目标的所有数据结构（换大神也搞不定啊......）。而是专注于讨论设计高效函数式数据结构和抽象每种技术和实现所需的技术。比如队列，堆（优先队列）和搜索结构。一旦你理解了设计的技术，你就能将已有的数据结构应用到你特定的需要，或者甚至从草图开始重新设计新的数据结构。
　　1.5 总览
　　本书分为三部分，第一部分（2，3章）介绍函数式数据结构。第二部分（4~7章）关注于惰性求值和记账偿还的关系。第三部分（8~11章）探索了一系列设计函数式数据结构的通用技术。