list - 反转列表的前 k 个元素

Question

我想高效地反转列表的前 k 个元素。

这是我想出的:

reverseFirst :: Int -> [a] -> [a] -> [a]
reverseFirst 0 xs rev     = rev ++ xs
reverseFirst k (x:xs) rev = reverseFirst (k-1) xs (x:rev)

reversed = reverseFirst 3 [1..5] mempty -- Result: [3,2,1,4,5]

它相当不错，但是 (++) 困扰着我。还是我应该考虑使用另一种数据结构？我想用短名单做这个数百万次。

Answer 1

让我们考虑一下reverse的通常结构:

reverse = rev [] where
  rev acc [] = acc
  rev acc (x : xs) = rev (x : acc) xs

它从空列表开始，从参数列表的前面添加元素，直到完成。我们想做类似的事情，只是我们想将元素添加到我们不反转的列表部分的前面。如果我们还没有未逆转的部分，我们怎么能做到这一点？

我能想到的避免两次遍历列表前面的最简单方法是使用惰性:

reverseFirst :: Int -> [a] -> [a]
reverseFirst k xs = dis where
  (dis, dat) = rf dat k xs

  rf acc 0 ys = (acc, ys)
  rf acc n [] = (acc, [])
  rf acc n (y : ys) = rf (y : acc) (n - 1) ys

dat 表示单独保留的列表部分。我们在执行反转的同一个辅助函数 rf 中计算它，但我们还在初始调用中将它传递给 rf。它从未在 rf 中实际检查过，所以一切正常。查看生成的核心(使用 ghc -O2 -ddump-simpl -dsuppress-all -dno-suppress-type-signatures)表明这些对被编译成未提升的对并且 Int 未装箱，因此一切都应该非常高效。

---

分析表明此实现的速度大约是差异列表的 1.3 倍，并且分配的内存大约是差异列表的 65%。