string - Haskell 的 `++` 有多懒？

Question

我很好奇我应该如何提高 Haskell 例程的性能，该例程可以找到字符串的字典最小循环旋转。

import Data.List
swapAt n = f . splitAt n where f (a,b) = b++a
minimumrotation x = minimum $ map (\i -> swapAt i x) $ elemIndices (minimum x) x

我想我应该使用 Data.Vector 而不是列表，因为 Data.Vector 提供就地操作，可能只是将一些索引操作到原始数据中。我实际上不应该自己费心跟踪索引以避免过度复制，对吗？

我很好奇 ++虽然影响优化。我想它会产生一个惰性字符串 thunk，在字符串被读取到那么远之前永远不会进行附加。因此， a不应该实际附加到 b只要 minimum 可以尽早消除该字符串，例如因为它以某个非常晚的字母开头。这个对吗？

Answer 1

xs ++ ys在 xs 的所有列表单元中添加一些开销, 但一旦到达 xs 的末尾它是免费的——它只是返回 ys .

查看 (++) 的定义有助于了解原因:

[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

即，它必须在遍历结果时“重新构建”整个第一个列表。 This article对于理解如何以这种方式推理惰性代码非常有帮助。

要意识到的关键是追加不是一次完成的。通过首先遍历所有 xs 逐步构建一个新的链表。 , 然后把 ys []会去。

因此，您不必担心到达 b 的末尾。并突然产生“追加”的一次性成本 a对它；成本分布在 b 的所有元素上.

向量完全是另一回事。它们的结构很严格，所以即使只检查 xs V.++ ys 的第一个元素产生分配新向量和复制 xs 的全部开销和 ys对它来说——就像用严格的语言一样。这同样适用于可变向量(除了在执行操作时会产生成本，而不是在强制生成向量时产生成本)，尽管我认为无论如何您都必须编写自己的附加操作。您可以将一堆附加的(不可变的)向量表示为 [Vector a]或类似的，如果这对您来说是个问题，但这只是将开销转移到您将其展平回单个向量时，听起来您对可变向量更感兴趣。