哈斯克尔的"++"多么懒惰？

Question

我很好奇我应该如何改进Has​​kell例程的性能,该例程找到一个字符串的按字典顺序最小的循环旋转.

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时候最低可及早消除串一样,因为它有一些非常后来字母开头.它是否正确？

Answer 1

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

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

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

也就是说,它必须在遍历结果时"重新构建"整个第一个列表.本文非常有助于理解如何以这种方式推理惰性代码.

要意识到的关键是不能一次性完成追加; 一个新的链表是通过首先遍历所有的xs,然后放在将去的ys地方逐步建立的[].

因此,您不必担心到达终点b并突然产生"追加"的一次性成本a; 成本分散在所有元素上b.

矢量完全是另一回事; 他们是在其结构严密,所以即使检查的只是第一个元素xs V.++ ys即被分配一个新的载体和复制的全部开销xs,并ys给它-就像在一个严格的语言.这同样适用于可变向量(除了在执行操作时产生成本,而不是强制生成向量时),尽管我认为你必须用这些来编写自己的追加操作.你可以代表一堆附加的(不可变的)向量,[Vector a]如果这对你来说是一个问题,但是当你将它展平成一个Vector时,它只会将开销转移到它,这听起来你对mutable更感兴趣向量.

Answer 2

尝试

minimumrotation :: Ord a => [a] -> [a]
minimumrotation xs = minimum . take len . map (take len) $ tails (cycle xs)
  where
    len = length xs

我希望它比你拥有的更快,虽然在未装箱的情况下索引玩杂耍Vector或者UArray可能仍然更快.但是,它真的是一个瓶颈吗？