haskell中与 "imperative"算法相关的性能

Question

我接受过 lisp 语言家族的一些培训，现在我为了我自己的利益学习一点 Haskell。在 lisp 中，函数式风格还可以，但有一些情况命令式风格对于获得良好的性能是必要的，例如

• 追加

  Append 很慢，因为它必须复制它的第一个参数(有时 x100与成功摆脱它的版本一样慢)。补救措施是将第一个列表的最后一个指针移动到开头第二个列表的，而不是追加。这当然是破坏性的操作。

• 排序

  快速排序的函数式版本创建了许多中间列表，这在某种程度上违背了算法的目的，是要尽可能快。 AFAIR，在普通的 lisp 中，sort 是唯一没有功能版本的破坏性功能。

• 长度

  这在 lisp 中是一项代价高昂的操作，因为必须沿着整个列表以获得它的长度。不必如此，afaik clojure以对数时间计算列表的长度。解决办法往往是在命令式循环中即时计算长度。

我的问题是，我们如何在 haskell 中处理这些问题？

Answer 1

正如 delnan 所说，这些问题与使用错误的数据结构有关，例如在需要向量时使用了链表。

您的特定操作

• append:cons 是 O(1)，因此我怀疑您指的是分配 cons 单元格、单元格上的模式匹配以及单元格的最终 GC 的行为。这是不可避免的，除非您优化列表，这在某些情况下确实会发生。

• sort:我建议您查看 ST monad，它允许您在纯上下文中使用需要突变的算法。查看vsort示例的实现。

• length:当然，获取链表长度的唯一方法是遍历链表。如果您经常需要长度，请考虑使用 Set、Map 或 Vector - 所有这些都记录了可以在 O(1) 中访问的总大小。

一般情况

• 研究 ST 的可变性。
• 针对正确的问题使用正确的数据结构。了解 Hackage 必须提供的结构(向量、数组、 HashMap 、哈希表、布隆过滤器等)。