这本书《纯函数数据结构》深入探讨了你的问题，并包含了理论和ML实现的精彩混合 - 附录还包含了Haskell的实现，所以你应该可以通过翻阅一些额外页面来跟上。如果你真的对这个问题有深入的兴趣，这是一本相当不错的（尽管有些难度）读物。话虽如此，我认为ephemient给出了一份非常出色的简短答案。

编辑：Steven Huwig提供了一个链接，指向书籍最初的毕业论文。虽然我没有读过它，但从目录的内容来看，唯一缺失的大部分是Haskell实现。

• Yes. Typically tuples, lists, and partially-evaluated functions are very common data structures in functional programming languages. Mutable data structures, like arrays and (real) hash tables, are used much less because they don t fit in as well with Haskell. SML (which is also functional, but not lazy) can use arrays more naturally than Haskell, but lists are still more common because they map well to recursive algorithms.
• I m not sure how to answer this. A problem for who?
• There exist implementations of associative arrays ("hash table" equivalent) which can continue to share most of their underlying structure even after different updates. I believe GHC s Data.Map does; also, Edison has quite a few lazy/functional-friendly data structures.

作为一个从事面向对象编程多年的人，最近在Haskell中开发一个需要很高速度（实时自动期权交易系统）的大型项目时说：

• Are there really significantly different usage patterns for data structures between functional and imperative programming?

如果你在谈论Haskell，那么非常明显。然而，这在很大程度上是由于纯度的原因；在其他更经常使用可变数据的函数式语言中，差异相对较小。话虽如此，正如其他人指出的那样，递归代码和结构在所有或几乎所有函数式语言中都被大量使用。

• If so, is this a problem?

这对我来说不是什么问题，除了需要花些时间学习新的工作方式。特别是，性能肯定不是问题：例如，我正在工作的系统比以前的Java实现运行速度要快得多。

• What if you really do need a hash table for some application? Do you simply swallow the extra expense incurred for modifications?

一般问题不在于"你真的需要哈希表"，而是你需要在一定的时间约束下访问某些数据（这可能就是"在某些特定的硬件上尽可能快地完成"）。为此，你需要四处寻找并做你需要做的事情。如果这包括引入可变性，我认为这并没有什么大问题，虽然在Haskell中可能不像其他语言那么方便。但请记住，如果你遇到这种问题，它肯定不会像"使用通用哈希表就可以了"那么简单。在特定的硬件平台上实现极高的性能通常需要大量的工作，往往需要不少技巧。只因某个语言实现比其他语言更适合某些特定的功能而更偏好某个语言实现，这在我看来是一种相当不成熟的软件工程方法，不太可能一致地产生好的结果。

Chris Okasaki的论文，《纯函数式数据结构》，可在网上免费获取。它涵盖了许多不同的策略，用于不可变的持久数据表示。

就需要使用哈希表而言，考虑到当您搜索一百万个元素时，O(lg n)查找只比O(1)查找慢20倍。

是的，使用模式截然不同，但这并不是问题。如果你想要哈希表，通常意味着你想要一个具有字符串键和快速访问的有限映射。Bentley和Sedgewick的三元搜索树是纯函数式的，在某些情况下，它们的性能优于哈希表。

如上所述，克里斯·奥卡萨基关于纯函数数据结构的书非常好。

功能性程序倾向于更加强调递归。这反过来又暗示着使用递归算法和递归数据结构。列表和树都是递归结构（列表上的“下一个”链接是另一个列表，树节点的子节点都是树）。

如果你在考虑算法的额外费用，你可能需要重新考虑。为什么哈希表（对于非递归算法而言，它是O（1））会产生额外费用？与使用树或列表相比，使用它的优势是什么？ (Note: This translation is in simplified Chinese)

是的，主要的区别是数据的不可变性，它可以包括代码（请参见高阶函数）。请参阅维基百科上关于“纯函数”的页面，了解常见数据类型和用法。它是否是一个问题取决于您如何看待它。如果它适合您正在处理的任务类型，那么使用函数式语言编程有很多优点。哈希表是一种关联数组类型，但不是您想在函数式语言中使用的类型，因为在插入时需要重新哈希，并且没有数组的性能差。相反，尝试使用Data.Map的Haskell实现来获取关联数组。

• Are there really significantly different usage patterns for data structures between functional and imperative programming?

大，巨大，日夜——这主要是因为在函数式编程中不容忍副作用。

• If so, is this a problem?

问题在于命令范例无法保持效率，随着并行化变得更加必要，他们将无法保持效率，这些语言唯一的出路就是摆脱副作用，但那时它们就会变成破碎的函数式语言。但既然有一些相当好的、工作良好的函数式语言，为什么要烦恼这些问题呢？此外，函数式语言的语意更容易控制，因此，函数程序可以被证明正确，而它们的C++对应物则不能（至少目前如此）。因此，许多形式验证工具都是基于函数式语言的。例如，ACL2是基于通用Lisp的，Cryptol则是基于Haskell的。由于形式验证是未来的大势所趋，函数式语言可以更好地与这些工具集成。简而言之，对于C、C++等语言说再见-好的告别！ 有人早该把它们打下去了。

• What if you really do need a hash table for some application? Do you simply swallow the extra expense incurred for modifications?

The wave of the future is this: you write a functional programming with specifying a hash table - the language you use is cryptol. When you are done and have proven that your program works you press a button and out pops an efficient version that uses a hash table if it has been decided that is the best thing to use.

就函数式语言中的哈希表而言: 因为上面提到了ACL2，我要指出ACL2有一个 "哈希共享" 库，提供了一个逻辑故事，它基本上具有关联列表语义但具有哈希表的性能（例如，您可以使用hons-get在表中查找值）。如果你有兴趣，请查看ACL2用户手册中的"hons"主题。