我正在使用 Haskell。标准列表串联既幼稚又缓慢。我的情况是我有一个算法，可以多次构建单个列表连接(顺序无关紧要，因此可以是前置或附加或组合)，然后返回它。结果将仅使用一次。高性能至关重要。
所以，这是一个非常简单的情况。我听说过差异列表，它有助于解决这种情况。但这是最好的选择吗？
列表可能会变得很大:100,000 个条目。
最佳答案
这是一个经验问题，应该根据经验来回答。合理的替代方案包括
带有缺点的标准列表(在您的问题中称为“前置”)
具有恒定时间附加的差异列表(John Hughes 列表)
支持常量时间追加的代数数据类型:
data Alist a = ANil | ASingle a | AAppend (Alist a) (Alist a)最终
concat的列表列表。
所有这些都需要线性时间。但恒定因素很重要，找出答案的唯一方法是构建和衡量。如果您愿意，您可以创建一个完全忠实于原始代码的微基准测试，但通过将每个列表操作记录到编写器 monad 中，仅执行列表操作。但这可能是一个巨大的痛苦，而且不值得。相反，编写一个简单的基准测试，编译(打开优化)，然后测量。
请让我们知道结果。
关于haskell - 用于大量串联和单次迭代的最快不可变列表数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8494005/