在Haskell,àlaLYAH的不同名单上的头尾

Question

了解一下Haskell提到差异列表(在该页面上搜索该术语),其中列表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？

1. 考虑到差异列表是一个函数而不是一个实际的"值",它甚至意味着询问它是否在恒定时间运行？
2. 是否headTailDifList在固定时间内运行？

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

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

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

Answer 1

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

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

基本定义(++)是右关联的,需要在继续第二个参数之前逐步执行整个第一个参数.这与差异列表生成的嵌套结构完全匹配,因为每个都(++)获得一个列表块作为其第一个参数.此外,因为(++)是一个好的列表生成者,整个结构懒惰存在.虽然完全评估它需要O(n),但只评估头部是O(k)在哪里k=number of chunks.

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

在一般使用中,评估差异列表应该与时间复杂度中的常规列表不同,只是等效操作的常数因子.

仅生成差异列表的第一个元素不需要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 ++)