История изменений
Исправление qnikst, (текущая версия) :
линзы - в зависимости от использования или просто функции или замыкания, большая часть работы прододится в compile time, для зипперов создается биективная структура, но с удобными свойствами. из минусов, что под каждую структуру нужно находить своё подходящее отображение, см. пример ниже. Плюс поскольку haskell ленивый иммутабельный язык, то активно используется COW и ленивость, в следствии чего расход памяти снижается.
Простейший пример зипперов для списка. Список в haskell это это ленивый singli-linked-list. Вместо списка делаем:
data ZipperList = ZipperList [a] (Maybe a) [a]
где первый список это начало списка задом наперёд, потом текущий элемент (если есть), потом конец списка в правильной последовательности. Соот. перемещение по списку это O(1) по времени и месту.
отображение из List -> ZipperList O(1) по памяти и O(1) по времени, отображение назад O(размер-первой-части) по памяти и времени, в случае если списки вычислены.
Я вылетел из контекста, поэтому не понял про какие именно стукруты речь, но надеюсь, что на вопрос ответил. А все неоптимизированные структуры живут в куче.
Исходная версия qnikst, :
линзы - в зависимости от использования или просто функции или замыкания, большая часть работы прододится в compile time, для зипперов создается биективная структура, но с удобными свойствами. из минусов, что под каждую структуру нужно находить своё подходящее отображение, см. пример ниже. Плюс поскольку haskell ленивый иммутабельный язык, то активно используется COW и ленивость, в следствии чего расход памяти снижается.
Простейший пример зипперов для списка. Список в haskell это это ленивый singli-linked-list. Вместо списка делаем:
data ZipperList = ZipperList [a] (Maybe a) [a]
где первый список это начало списка задом наперёд, потом текущий элемент (если есть), потом конец списка в правильной последовательности. Соот. перемещение по списку это O(1) по времени и месту.
отображение из List -> ZipperList O(1) по памяти и O(1) по времени, отображение назад O(размер-первой-части) по памяти и времени, в случае если списки вычислены.