inits 和 tail 的 space 复杂度是多少？
What are the space complexities of inits and tails?
TL;博士
在阅读 Okasaki 的 纯函数式数据结构 中关于 持久性 的段落并复习了他关于单向链表的说明性示例（这是Haskell 的列表是如何实现的），我想知道 Data.List 的 inits 和 tails 的 space 复杂性...
在我看来
tails 的 space 复杂度在其参数长度上是 线性 ，并且 inits 的 space 复杂度在其参数长度上是 二次方，
但一个简单的基准表明并非如此。
理由
使用tails，可以共享原始列表。计算 tails xs 简单地包括遍历列表 xs 并创建指向该列表中每个元素的新指针；无需在内存中重新创建 xs 的一部分。
相比之下，因为inits xs"ends in a different way"的每个元素都不能这样共享，xs的所有可能的前缀都必须在内存中从头开始重新创建。
基准
下面的简单基准测试表明两个函数之间的内存分配没有太大区别：
-- Main.hs
import Data.List (inits, tails)
main = do
let intRange = [1 .. 10 ^ 4] :: [Int]
print $ sum intRange
print $ fInits intRange
print $ fTails intRange
fInits :: [Int] -> Int
fInits = sum . map sum . inits
fTails :: [Int] -> Int
fTails = sum . map sum . tails
用
编译我的Main.hs文件后
ghc -prof -fprof-auto -O2 -rtsopts Main.hs
和运行
./Main +RTS -p
Main.prof 文件报告如下：
COST CENTRE MODULE %time %alloc
fInits Main 60.1 64.9
fTails Main 39.9 35.0
分配给fInits的内存和分配给fTails的内存是同一个数量级的...嗯...
这是怎么回事？
- 我关于
tails（线性）和 inits（二次）的 space 复杂性的结论是否正确？
- 如果是这样，为什么 GHC 会为
fInits 和 fTails 分配大致相同的内存？ list fusion和这个有关系吗？
- 还是我的基准有缺陷？
Haskell 报告中 inits 的实现与 base 4.7.0.1 (GHC 7.8.3) 之前使用的实现相同或几乎相同，速度非常慢。特别是，fmap 应用程序以递归方式堆叠，因此强制结果的连续元素变得越来越慢。
inits [1,2,3,4] = [] : fmap (1:) (inits [2,3,4])
= [] : fmap (1:) ([] : fmap (2:) (inits [3,4]))
= [] : [1] : fmap (1:) (fmap (2:) ([] : fmap (3:) (inits [4])))
....
Bertram Felgenhauer 探索的最简单的渐近最优实现基于应用 take 和连续更大的参数：
inits xs = [] : go (1 :: Int) xs where
go !l (_:ls) = take l xs : go (l+1) ls
go _ [] = []
Felgenhauer 能够使用 take 的私有非融合版本从中获得一些额外的性能，但它仍然没有达到预期的速度。
在大多数情况下，以下非常简单的实现要快得多：
inits = map reverse . scanl (flip (:)) []
在一些奇怪的极端情况下（如 map head . inits），这个简单的实现是渐近非最优的。因此，我使用相同的技术编写了一个版本，但基于 Chris Okasaki 的 Banker's queues，它是渐近最优的并且几乎同样快。 Joachim Breitner 进一步优化了它，主要是通过使用严格的 scanl' 而不是通常的 scanl，这个实现进入了 GHC 7.8.4。 inits 现在可以在 O(n) 时间内生成结果的书脊；强制整个结果需要 O(n^2) 时间，因为 none 的 conses 可以在不同的初始段之间共享。如果你想要非常快的 inits 和 tails，你最好的选择是使用 Data.Sequence; Louis Wasserman 的实现 。另一种可能性是使用 Data.Vector——它可能对这些东西使用切片。
TL;博士
在阅读 Okasaki 的 纯函数式数据结构 中关于 持久性 的段落并复习了他关于单向链表的说明性示例（这是Haskell 的列表是如何实现的），我想知道 Data.List 的 inits 和 tails 的 space 复杂性...
在我看来
tails的 space 复杂度在其参数长度上是 线性 ，并且inits的 space 复杂度在其参数长度上是 二次方，
但一个简单的基准表明并非如此。
理由
使用tails，可以共享原始列表。计算 tails xs 简单地包括遍历列表 xs 并创建指向该列表中每个元素的新指针；无需在内存中重新创建 xs 的一部分。
相比之下，因为inits xs"ends in a different way"的每个元素都不能这样共享，xs的所有可能的前缀都必须在内存中从头开始重新创建。
基准
下面的简单基准测试表明两个函数之间的内存分配没有太大区别：
-- Main.hs
import Data.List (inits, tails)
main = do
let intRange = [1 .. 10 ^ 4] :: [Int]
print $ sum intRange
print $ fInits intRange
print $ fTails intRange
fInits :: [Int] -> Int
fInits = sum . map sum . inits
fTails :: [Int] -> Int
fTails = sum . map sum . tails
用
编译我的Main.hs文件后
ghc -prof -fprof-auto -O2 -rtsopts Main.hs
和运行
./Main +RTS -p
Main.prof 文件报告如下：
COST CENTRE MODULE %time %alloc
fInits Main 60.1 64.9
fTails Main 39.9 35.0
分配给fInits的内存和分配给fTails的内存是同一个数量级的...嗯...
这是怎么回事？
- 我关于
tails（线性）和inits（二次）的 space 复杂性的结论是否正确？ - 如果是这样，为什么 GHC 会为
fInits和fTails分配大致相同的内存？ list fusion和这个有关系吗？ - 还是我的基准有缺陷？
Haskell 报告中 inits 的实现与 base 4.7.0.1 (GHC 7.8.3) 之前使用的实现相同或几乎相同，速度非常慢。特别是，fmap 应用程序以递归方式堆叠，因此强制结果的连续元素变得越来越慢。
inits [1,2,3,4] = [] : fmap (1:) (inits [2,3,4])
= [] : fmap (1:) ([] : fmap (2:) (inits [3,4]))
= [] : [1] : fmap (1:) (fmap (2:) ([] : fmap (3:) (inits [4])))
....
Bertram Felgenhauer 探索的最简单的渐近最优实现基于应用 take 和连续更大的参数：
inits xs = [] : go (1 :: Int) xs where
go !l (_:ls) = take l xs : go (l+1) ls
go _ [] = []
Felgenhauer 能够使用 take 的私有非融合版本从中获得一些额外的性能，但它仍然没有达到预期的速度。
在大多数情况下，以下非常简单的实现要快得多：
inits = map reverse . scanl (flip (:)) []
在一些奇怪的极端情况下（如 map head . inits），这个简单的实现是渐近非最优的。因此，我使用相同的技术编写了一个版本，但基于 Chris Okasaki 的 Banker's queues，它是渐近最优的并且几乎同样快。 Joachim Breitner 进一步优化了它，主要是通过使用严格的 scanl' 而不是通常的 scanl，这个实现进入了 GHC 7.8.4。 inits 现在可以在 O(n) 时间内生成结果的书脊；强制整个结果需要 O(n^2) 时间，因为 none 的 conses 可以在不同的初始段之间共享。如果你想要非常快的 inits 和 tails，你最好的选择是使用 Data.Sequence; Louis Wasserman 的实现 Data.Vector——它可能对这些东西使用切片。