haskell - 什么是脊椎僵硬

Question

在 Haskell 中，经常提到与惰性求值相关的术语脊椎严格性。尽管我对此含义有模糊的理解，但最好对以下内容进行更具体的解释：

• 什么是数据结构的脊椎
• 脊椎僵硬是什么意思？
• 比较 Spine 严格数据结构和惰性数据结构有什么好处？

Answer 1

这是一个例子

> length (undefined : 3 : 4 : undefined : [])
4
> length (2 : 3 : 4 : 5 : undefined)
<<loop>>

第一个列表包含底部作为元素，但列表的“形状”是完全定义的。粗略地说，每个列表单元都有一个明确定义的指向下一个元素的“指针”。这种“形状”被称为脊柱。

相比之下，第二个列表具有完全定义的元素，但它的脊椎没有定义。这是因为它不是以空列表结尾[]，而是以非终止表达式结尾undefined。在这种情况下，脊柱没有定义。

该功能length关心脊柱，而不是元素。所以它能够在第一种情况下工作（由于懒惰），但不能在第二种情况下工作。我们说length在脊椎中是严格的，但不是在列表的元素中。

同样，在树数据结构中，脊椎是树的“形状”。一些函数（例如树高）可以在不检查元素的情况下编写，但只需要检查脊椎。这种功能在脊柱中是严格的。

虽然有些函数必须严格脊椎（例如长度），但其他函数可以以脊椎严格或脊椎懒惰的方式编写。例如map，在列表上是脊椎惰性的：它会在访问其输入的所有脊椎之前返回输出的第一个元素。可以通过以下方式获得更严格的变体

map' :: (a->b) -> [a] -> [b]
map' _ []     = []
map' f (x:xs) = (f x :) $! map' f xs

这是否有益取决于上下文。考虑

-- apply n times function f
iter n f = foldr (.) id $ replicate n f

list1 = iter 1000 (map  succ) [1..10]
list2 = iter 1000 (map' succ) [1..10]

如果我要求head list1，我将仅在列表的第一个元素处强制应用 1000 个地图。这意味着之后将有 1000 个分配的 thunk 在内存中占用空间。

相反，head list2将强制应用整个列表中的 1000 个地图。因此，所有 1000 个 thunk 都可以立即被垃圾收集，回收内存。