什么是脊椎严格 [英] What is spine strictness

问题描述

在Haskell中，术语脊椎严格性经常被提及与懒惰评估有关。虽然我对它的含义有一个模糊的理解，但对于 的更多具体解释是很好的：

• 什么是数据结构的 spine
  
• spine strictness 是什么意思？


• 在比较spine严格数据结构和懒惰数据结构时， 有什么好处？
  

解决方案

以下是一个例子

 >长度（undefined：3：4：undefined：[]）
 4 
>长度（2：3：4：5：未定义）
<< loop>> 
  

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

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

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

同样，在树数据结构，脊椎是树的形状。一些功能如树高可以在不检查元素的情况下编写，而只是脊柱。这样的功能在脊椎上是非常严格的。

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

  map'::（a-> b） - > [a]  - > [b] 
 map'_ [] = [] 
 map'f（x：xs）=（f x :) $！ map'f xs 
  

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

   - 应用n次函数f 
 iter nf = foldr（。）id $ replicate nf 
 
 list1 = iter 1000（map succ）[1..10] 
 list2 = iter 1000（map'succ）[1..10] 
  

如果我要求头部列表1 我将强制1000个地图的应用只在第一个元素列表。这意味着在此之后将有1000个分配的thunk在内存中占据空间。

相反， head list2 会强制将1000张地图应用于整个列表。所以，所有1000个thunk都可以立即进行垃圾收集，回收内存。

In Haskell, the term spine strictness is often mentioned in relation to lazy evaluation. Though I have a vague understanding of that it means, it would be nice to have a more concrete explanation about:

• What is the spine of a data structure
• What does spine strictness mean?
• What are the benefits when comparing spine strict data structures with lazy ones?

解决方案

Here's an example

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

The first list contains bottoms as elements, but the "shape" of the list is fully defined. Roughly speaking, every list cell has a clearly defined "pointer" to its next element. This "shape" is called the spine.

The second list, by comparison, has completely defined elements, yet its spine is not defined. This is because it does not end with the empty list [], but with a non-terminating expression undefined. In this case the spine is not defined.

The function length cares about the spine, not the elements. So it is able to work in the first case (thanks to laziness), but not the second. We say that length is strict in the spine, but not in the elements of the list.

Similarly, in tree data structures, the spine is the "shape" of the tree. Some functions such as tree height can be written without inspecting elements, but only the spine. Such functions are strict in the spine.

While some functions have to be spine-strict (e.g. length), others can be written both in a spine-strict or spine-lazy fashion. For instance map on lists is spine-lazy: it will return the first element of the output before accessing all the spine of its input. A stricter variant can be obtained by

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

Whether this is beneficial depends on the context. Consider

-- 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]

If I demand head list1 I will force the application of the 1000 maps only at the first element of the list. This means that after that there will be 1000 allocated thunks in memory holding up space.

Instead, head list2 will force the application of the 1000 maps on the whole list. So, all the 1000 thunks can be immediately garbage collected, reclaiming memory.

这篇关于什么是脊椎严格的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！