list - Haskell，à la LYAH中差异列表上的头部和尾部

Question

向您学习 Haskell 提到的 difference lists (在该页面上搜索该术语)，其中列表 l不直接表示，而是作为函数 (l++) .这允许更有效的左右连接。串联变成函数组合，最终可以通过($[]) 转换成真正的列表.我想知道可以在差异列表上有效地支持哪些操作。例如，(:) 的等价物对于差异列表是

\x l -> (x:) . l

一个人可以有效地实现head和 tail对于差异列表？这是明显的实现:

headTailDifList :: ([a] -> [a]) -> (a, [a] -> [a])
headTailDifList dl = (head l, ((tail l)++))
    where
    l = dl []

对于真实列表，\l -> (head l, tail l)以恒定的时间运行。这个怎么样headTailDifList ?可能是由于延迟评估，只有 l 的第一个元素会被评估吗？

考虑到差异列表是一个函数而不是实际的“值”，问这是否在恒定时间内运行意味着什么？

是否 headTailDifList在恒定时间内运行？

还有其他一些恒定时间的实现吗？这是一个候选人:

headTailDifList dl = (head (dl []), tail.dl )

但是，如果 dl，尾部不会抛出异常。是 id (空差异列表)。

Answer 1

编辑:添加了更多关于 thunk 的信息。

首先查看从差异列表到常规列表的转换。仅此操作仅需要恒定时间，因为不需要评估。结果列表将作为 thunk 存在，其结构如下:


(++) 的基本定义是右结合的，需要遍历整个第一个参数才能继续第二个参数。这与差异列表生成的嵌套结构完美匹配，因为每个 (++)获取单个列表 block 作为其第一个参数。此外，因为 (++)是一个不错的列表生产者，整个结构都是懒惰的存在。尽管完全评估它需要 O(n)，但仅评估头部是 O(k)，其中 k=number of chunks .

考虑 a,b == []; c = [1..] .然后head需要先检查 a和 b在转到 c 之前是空的并找到第一个元素。在最坏的情况下head在找到空列表构造函数之前会遍历整个结构。然而，实际上这是一种非常罕见的情况，即使这样也不是特别有害，因为遇到空 block 并继续前进是一个恒定时间的操作。

在一般使用中，评估差异列表应该与常规列表在时间复杂度上的差异仅是等效操作的常数因子。

仅生成差异列表的第一个元素不需要 O(n) 时间，这可以通过使用无限列表轻松证明:

*Dl Control.Monad Control.Applicative> head $ ($ []) $ toDl [1..] . toDl [4..]
1
(0.01 secs, 2110104 bytes)

*Dl Control.Monad Control.Applicative> fmap (head . ($ [])) $ headTailDifList (toDl [1..])
(1,2)
(0.00 secs, 2111064 bytes)

*Dl Control.Monad Control.Applicative> fmap (head . ($ [])) $ headTailDifList (toDl [1..] . toDl [3..] . toDl [] . toDl [5..])
(1,2)
(0.01 secs, 3105792 bytes)

-- create a difference list
toDl :: [a] -> ([a] -> [a])
toDl l = (l ++)