haskell - 高效版 'inits'

Question

也就是说，inits "abc" == ["","a","ab","abc"]
有标准版inits在 Data.List ，但下面我自己写了一个版本:

myInits = f id
 where
  f start (l:ls) = (start []):(f (start . (l:)) ls)
  f start [] = [(start [])]

虽然我的版本比标准版本简单得多，但出于效率原因，我怀疑它并没有那么好。我怀疑当 myInits l经过全面评估需要 O(n^2)空间。以 myTails 为例， tails 的实现:

myTails a@(_:ls) = a:(myTails ls)
myTails [] = [[]]

这与标准版本几乎完全相同，我怀疑达到了 O(n)通过重用列表的尾部来留出空间。

有人可以解释一下:

为什么我的版本 inits不好。

为什么另一种方法更好(Data.List 中的标准方法或您自己的方法)。

Answer 1

您的 myInits使用一种称为 difference list 的技术制作在线性时间内构建列表的函数。我相信，但没有检查，完全评估的运行时间 myInits是 O(n^2)需要O(n^2)空间。全面评估 inits还需要 O(n^2)运行时间和空间。 inits 的任何版本将需要 O(n^2)空间;使用 : 构建的列表和 []只能共享它们的尾部，inits 的结果中没有共同的尾部. inits 的版本在 Data.List使用摊销时间 O(1)队列，很像 simpler queue described in the second half of a related answer . Snoc referenced in the source code in Data.List 在 Cons 上玩文字游戏吗？ (: 的另一个名称)向后 - 能够将项目附加到列表的末尾。

简要地试验这些功能建议 myInits在大列表上稀疏使用时表现令人满意。在我的电脑上，在 ghci 中，myInits [1..] !! 8000000在几秒钟内产生结果。不幸的是，我有 horrifyingly inefficient implementation ghc 7.8.3 附带的，所以我无法比较 myInits至inits .

严格
myInits 之间有一个很大的区别。和 inits在 myTails 之间和 tails .当应用于 undefined 时，它们具有不同的含义。或 _|_ (发音为“bottom”，我们用于 undefined 的另一个符号)。
inits具有严格属性 inits (xs ++ _|_) = inits xs ++ _|_ , 其中，当 xs是空列表[]说inits应用于 undefined 时仍会产生至少一个结果

inits (xs ++ _|_) = inits xs ++ _|_
inits ([] ++ _|_) = inits [] ++ _|_
inits        _|_  = [[]]     ++ _|_
inits        _|_  =  []      :  _|_

我们可以通过实验看到这一点

> head . inits $ undefined
[]

myInits对于空列表或更长的列表都没有此属性。

> head $ myInits undefined
*** Exception: Prelude.undefined

> take 3 $ myInits ([1,2] ++ undefined)
[[],[1]*** Exception: Prelude.undefined

如果我们意识到 f，我们可以解决这个问题。在 myInits将产生 start []在任一分支中。因此，我们可以延迟模式匹配，直到需要决定下一步做什么。

myInits' = f id
 where
  f start list = (start []):
                 case list of
                     (l:ls) -> f (start . (l:)) ls
                     []     -> []

这种懒惰的增加使得 myInits'像 inits 一样工作.

> head $ myInits' undefined
[]

> take 3 $ myInits' ([1,2] ++ undefined)
[[],[1],[1,2]]

同样，您的 myTails 之间的差异和 tails in Data.List 是 tails在决定是否存在列表的其余部分之前，将整个列表作为第一个结果。文档说它服从 tails _|_ = _|_ : _|_ ，但它实际上遵循一个更强大的规则，很难轻易描述。