Что такое строгость позвоночника

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 блоков памяти.

Вместо, head list2 заставит приложение 1000 карт на весь список. Итак, все 1000 громов могут быть сразу же собраны мусором, восстанавливая память.