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中。 正确吗？

- Jeff Burdges

---

@LightnessRacesinOrbit：显然你从未见过Benchmarks Game中的Haskell程序！ - ehird

我的幽默而善意的评论被删除了。 :( 去猜吧。 - Lightness Races in Orbit

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]或类似的形式，但这只是将开销移动到了将其展平回单个向量时，而且听起来您更感兴趣的是可变向量。

- ehird

---

@JeffBurdges：我已经扩展了我的回答，涵盖了向量 :) - ehird

谢谢！另一个小问题：如果我写了 minimumrotation x = minimum $ map f $ elemIndices (minimum x) x where f i = take (length x) $ drop i (x++x)。那么当 f 被解开时，length x 和 x++x 只会被计算一次吗？ - Jeff Burdges

@JeffBurdges：也许吧，但我不会指望它；GHC 对这种优化比较保守。你应该在与 f 的定义相同的 where 块中给 length x 起一个名字；我不会担心 (x++x) 部分。（请注意，f 本身已经处于弱头正常形式，因此永远不会被强制执行（“去想象”）；对于不同的 i 值，将强制执行 f i。） - ehird

我很好奇是否严格应用$!可以解决这个问题，而不需要创建新的标签，你有什么想法吗？ - Jeff Burdges

@JeffBurdges：那样做没有帮助；你必须将表达式提取到 lambda 表达式之外。 - ehird

Answer 2

尝试

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

我期望这比你拥有的更快，虽然在未包装的Vector或UArray上进行索引操作可能仍然更快。但是，这真的是瓶颈吗？

- Daniel Fischer

---

循环比xs++xs更快吗？我的先验假设是肯定的。交换两个take不应影响性能，因为所有这些thunk都必须计算完成。 - Jeff Burdges

cycle xs 就是 fix (xs ++)，所以如果有什么问题，xs ++ xs 会更便宜，但我不会担心它；开销将是微不足道的。交换 take len 和 map (take len) 不会产生任何影响。 - ehird

如果在这里xs ++ xs和cycle xs之间存在性能差异，如果它不是微不足道的话，我会感到惊讶。我认为交换take len和map (take len)不会有明显的差异，但我还没有进行基准测试。 - Daniel Fischer

Answer 3

如果您对快速连接和快速的splitAt感兴趣，请使用Data.Sequence。

我对您的代码进行了一些风格上的修改，使其看起来更像Haskell的惯用语法，但逻辑完全相同，除了一些转换到和从Seq的转换。

import qualified Data.Sequence as S
import qualified Data.Foldable as F

minimumRotation :: Ord a => [a] -> [a]
minimumRotation xs = F.toList
                   . F.minimum
                   . fmap (`swapAt` xs')
                   . S.elemIndicesL (F.minimum xs')
                   $ xs'
  where xs' = S.fromList xs
        swapAt n = f . S.splitAt n
          where f (a,b) = b S.>< a

- Dan Burton

---

哦，有几个巧妙的技巧，包括中缀 swapAt。哈哈 - Jeff Burdges

@JeffBurdges - 另一个选项是 (flip swapAt xs')，但我个人更喜欢中缀部分。 - Dan Burton

自然而然地，最好一直使用序列，这样toList和fromList不会占用程序太多时间。 - alternative