haskell - tipos - ¿Qué es el rigor de la columna vertebral?

test evaluacion columna vertebral

Question

En Haskell, el término severidad de la columna se menciona a menudo en relación con la evaluación perezosa. Aunque entiendo vagamente lo que significa, sería bueno tener una explicación más concreta sobre:

• ¿Cuál es el lomo de una estructura de datos?
• ¿Qué significa rigidez de columna vertebral ?
• ¿Cuáles son los beneficios cuando se comparan las estructuras estrictas de datos espinales con las perezosas?

Answer 1

Aquí hay un ejemplo

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

La primera lista contiene fondos como elementos, pero la "forma" de la lista está completamente definida. En términos generales, cada celda de lista tiene un "puntero" claramente definido para su siguiente elemento. Esta "forma" se llama espina dorsal.

La segunda lista, en comparación, tiene elementos completamente definidos, pero su columna vertebral no está definida. Esto se debe a que no termina con la lista vacía [] , pero con una expresión undefined terminada undefined . En este caso, la columna vertebral no está definida.

La length función se preocupa por la columna vertebral, no por los elementos. Entonces es capaz de funcionar en el primer caso (gracias a la pereza), pero no en el segundo. Decimos que la length es estricta en la columna vertebral, pero no en los elementos de la lista.

Del mismo modo, en las estructuras de datos de árbol, la columna vertebral es la "forma" del árbol. Algunas funciones, como la altura del árbol, se pueden escribir sin inspeccionar elementos, sino solo el lomo. Tales funciones son estrictas en la columna vertebral.

Mientras que algunas funciones tienen que ser rigurosas (por ejemplo, la duración), otras pueden escribirse tanto de manera estricta como estricta. Por ejemplo, el map en las listas es espinoso: devolverá el primer elemento de la salida antes de acceder a toda la columna vertebral de su entrada. Una variante más estricta se puede obtener

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

Si esto es beneficioso depende del contexto. Considerar

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

Si exijo head list1 la aplicación de los 1000 mapas solo en el primer elemento de la lista. Esto significa que después de eso, habrá 1000 trozos asignados en la memoria que contengan espacio.

En cambio, head list2 forzará la aplicación de los 1000 mapas en toda la lista. Entonces, todos los 1000 thunks pueden ser recogidos de inmediato, recuperando memoria.