Утечки пространства потребляют память иначе, чем действительные ленивые алгоритмы?
Утечка пространства обычно определяется выполнением программы, которая занимает больше места, чем необходимо. Совместимо ли такое определение с алгоритмами, которые требуют ленивой оценки для амортизированной эффективности времени?
Интересно, имеют ли они тенденцию демонстрировать различный образец в структурах thunk. Например, простая утечка пространства может выглядеть так:
1 + (2 + 3 + ...)
Было бы нормально для ленивого алгоритма, подобного древовидному поиску, создавать структуры одинакового размера?
У меня есть подозрение, что правильные ленивые шаблоны оценки будут иметь тенденцию выглядеть по-разному, что позволяет легко обнаружить фактические утечки. Например, структура может выглядеть так:
[...] : a : b : c
куда [...] part - это префикс, который не имеет ссылок и мог быть уже собранным. В таком случае ленивый алгоритм вполне может работать на O(1) пространство и не может быть утечки пространства, что делает различие очень четким.
Интересно, распространено ли это или существует более широкий спектр компромиссов между пространственной и временной эффективностью в ленивых языках.
РЕДАКТИРОВАТЬ: Возможный контрпример - постоянные структуры. Их легко отличить от космических утечек?