haskell - 什么是脊椎僵硬

Question

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

什么是数据结构的脊椎

脊椎僵硬是什么意思？

比较 Spine 严格数据结构和惰性数据结构有什么好处？

Answer 1

这是一个例子

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

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

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

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

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

虽然有些函数必须严格脊椎(例如长度)，但其他函数可以以脊椎严格或脊椎懒惰的方式编写。例如 map on lists 是spine-lazy:它会在访问其输入的所有主干之前返回输出的第一个元素。可以通过以下方式获得更严格的变体

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 个 map 。这意味着之后将有 1000 个分配的 thunk 在内存中占用空间。

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