haskell - 具有惰性脊柱和严格叶子的数据结构示例

Question

提到的性能技巧之一here是这样的:

As a safe default: lazy in the spine, strict in the leaves.

我无法想象这样的数据结构。

如果我以列表为例，如果我在叶子中设置严格，那么脊柱是否会自动严格？

是否有脊椎是惰性的而叶子是严格的数据结构示例？

Answer 1

“脊椎惰性，叶子严格”是API的属性，而不仅仅是数据结构的属性。以下是它如何查找列表的示例:

module StrictList (StrictList, runStrictList, nil, cons, uncons, repeat) where

newtype StrictList a = StrictList { runStrictList :: [a] }

nil :: StrictList a
nil = StrictList []

cons :: a -> StrictList a -> StrictList a
cons x (StrictList xs) = x `seq` StrictList (x:xs)

uncons :: StrictList a -> Maybe (a, StrictList a)
uncons (StrictList []) = Nothing
uncons (StrictList (x:xs)) = Just (x, StrictList xs)

repeat :: a -> StrictList a
repeat x = x `seq` StrictList (let xs = x:xs in xs)

请注意，与内置列表相比，这个 API 相当贫乏——这只是为了保持插图较小，而不是出于根本原因。这里的关键点是，您仍然可以支持像repeat这样的东西，其中spine必然是惰性的(它是无限的!)，但所有的叶子在其他事情发生之前都会被评估。许多其他可以生成无限列表的列表操作都可以适应叶严格版本(尽管不是全部，正如您所观察到的)。

您还应该注意到，不一定能够以自然的方式将 leaf-lazy、spine-lazy 结构转变为 leaf-strict、spine-lazy 结构；例如人们无法编写一个通用的 fromList::[a] -> StrictList a 这样:

• fromList (重复 x) = 重复 x 和
• runStrictList (fromList xs) = xs 对于所有有限长度 xs。

(请原谅我的双关语，我是一个屡犯的罪犯)。