什么是脊柱严格

Question

在Haskell中,经常提到与懒惰评估相关的术语脊柱严格性.虽然我对这意味着有一个模糊的理解,但对于以下方面有一个更具体的解释会更好:

Answer 1

这是一个例子

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

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

相比之下,第二个列表已完全定义了元素,但其主干未定义.这是因为它不以空列表结尾[],而是以非终止表达式结束undefined.在这种情况下,脊柱未定义.

该功能length关心脊柱,而不是元素.所以它能够在第一种情况下工作(感谢懒惰),但不是第二种情况.我们说length脊柱是严格的,但不是列表的元素.

类似地,在树数据结构中,书脊是树的"形状".某些功能(如树高)可以在不检查元素的情况下编写,但只能编写脊柱.这种功能在脊柱上是严格的.

虽然某些功能必须是脊柱严格的(例如长度),但其他功能可以以脊柱严格或脊柱惰性方式编写.例如map,列表是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个地图.这意味着在此之后将在内存中分配1000个分配的thunks占用空间.

相反,head list2将强制在整个列表上应用1000个地图.因此,所有1000个thunk可以立即进行垃圾回收,回收内存.

@ Markus1189:如果你仍然想知道为什么它被称为*spine*,请在GHCi中尝试以下内容:`let x = map(+1)[1..10]`,`length x`,`:sprint x`.然后,您将清楚地看到列表的主干 (4认同)
然而,在第一个例子中,`length(2:3:4:5:undefined)`不会循环,但会立即给出异常,因为haskell中的未定义不是'非终止表达式'虽然我明白你的意思,但是显示它在repl风格使它令人困惑 (2认同)
@semicolon:chi是对的.使用`:set -ddump-simpl -ddump-ds`查看更多内容.`"foo"`是一个`CString`,而`['f','o','o']`已经是一个列表并在那时进行评估.顺便说一句,最好[问这样的问题](/sf/),因为评论通知可能不会被注意到. (2认同)