一些数据结构是否比其他数据结构更适合函数式编程？

Question

在Real World Haskell中,有一个标题为"没有数组或哈希表的生命"的部分,作者建议列表和树在函数式编程中是首选,而数组或哈希表可能在命令式程序中使用.

这是有道理的,因为在创建新列表或树时,重用部分(不可变)列表或树要比使用数组更容易.

所以我的问题是:

• 功能和命令式编程之间的数据结构是否存在明显不同的使用模式？
• 如果是这样,这是一个问题吗？
• 如果您确实需要某个应用程序的哈希表怎么办？您是否只是吞下了修改所产生的额外费用？

Answer 1

" 纯功能数据结构 "一书深入介绍了您的问题,包括主要在ML中的理论和实现的完美组合 - 附录还包含Haskell实现,因此您应该能够跟随一些额外的页面转换.如果你真的对你的问题的彻底回答感兴趣,这是一个非常好的(虽然部分困难)阅读.话虽如此,我认为ephemient给出了一个极好的简短回答.

编辑:史蒂文胡威格提供了一本链接到该书开头的论文.虽然我还没有读过它,但是缺少的唯一重要的东西(从目录中判断)是Haskell实现.

Answer 2

作为一个多年来一直在做OO的人,最近在Haskell建立了一个需要大量速度的大型项目(实时自动化期权交易系统):

• 功能和命令式编程之间的数据结构是否存在明显不同的使用模式？

如果你在谈论Haskell,是的,非常如此.然而,很大一部分是由于纯度; 在更常使用可变数据的其他函数语言中,差异稍微小一些.也就是说,正如其他人所指出的那样,递归代码和结构在所有或几乎所有函数语言中使用得更多.

• 如果是这样,这是一个问题吗？

除了不得不花一些时间学习新的工作方式之外,它不适合我.特别是,性能肯定不是问题:例如,我正在开发的系统运行速度比以前的Java实现快得多.

• 如果您确实需要某个应用程序的哈希表怎么办？您是否只是吞下了修改所产生的额外费用？

通常问题不在于"你确实需要一个哈希表",而是你需要在某些给定的时间限制内访问某些数据(这可能是"在某些给定的硬件上尽可能快".).为此,你环顾四周,做你需要做的事情.如果这包括引入可变性,我没有看到它的大问题,你可以在Haskell中做到这一点,尽管它可能不像在其他语言中那样方便.但是请记住,如果你有这种性质的问题,它肯定不会那么简单,"使用通用哈希表,你就完成了." 特定硬件平台上特定功能的极高性能总是需要大量工作,通常不仅仅是一些技巧.仅仅因为它有一些特殊的东西比其他语言更好,所以优先考虑一种语言实现,在我看来,这是一种相当简单的软件工程方法,不太可能始终如一地产生好的结果.

Answer 3

• 是.通常,元组,列表和部分评估的函数是函数式编程语言中非常常见的数据结构.可变数据结构(如数组和(实际)哈希表)的使用要少得多,因为它们不适合Haskell.SML(也是功能的,但不是懒惰的)可以比Haskell更自然地使用数组,但是列表仍然更常见,因为它们很好地映射到递归算法.
• 我不知道如何回答这个问题.谁的问题？
• 存在关联数组("哈希表"等价物)的实现,即使在不同的更新之后,它们也可以继续共享其大部分底层结构.我相信GHC Data.Map的确如此; 此外,爱迪生还有一些懒惰/功能友好的数据结构.

Answer 4

克里斯·冈崎（Chris Okasaki）的论文《纯功能数据结构》可免费在线获得。它涵盖了用于不变的持久数据表示的许多不同策略。

至于真正需要哈希表的情况，请考虑在搜索一百万个元素时，O（lg n）查找的速度仅为O（1）查找速度的二十倍。