Предположим, что кто-то делает программу для игры в шахматы или решает судоку. В этом виде программы имеет смысл иметь древовидную структуру, представляющую состояния игры.
Это дерево было бы очень большим, "практически бесконечным". Это само по себе не проблема, поскольку Haskell поддерживает бесконечные структуры данных.
Известный пример бесконечной структуры данных:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Узлы выделяются только при первом использовании, поэтому список принимает конечную память. Можно также перебирать бесконечный список, если они не содержат ссылок на его голову, позволяя сборщику мусора собирать свои части, которые больше не нужны.
Вернемся к примеру дерева - предположим, что вы выполняете некоторую итерацию по дереву, итерации деревьев, которые повторяются, не могут быть освобождены, если корень дерева по-прежнему необходим (например, при повторном углублении поиска дерево повторяется в течение нескольких раз, и поэтому корень должен быть сохранен).
Одним из возможных решений этой проблемы, о котором я думал, является использование "unmemo-monad".
Я попытаюсь продемонстрировать, что эта монада должна делать с помощью монадических списков:
import Control.Monad.ListT (ListT) -- cabal install List
import Data.Copointed -- cabal install pointed
import Data.List.Class
import Prelude hiding (enumFromTo)
nums :: ListT Unmemo Int -- What is Unmemo?
nums = enumFromTo 0 1000000
main = print $ div (copoint (foldlL (+) 0 nums)) (copoint (lengthL nums))
Используя nums :: [Int], программа займет много памяти, поскольку ссылка на nums нужна lengthL nums, пока она повторяется над foldlL (+) 0 nums.
Цель Unmemo заключается в том, чтобы заставить среду выполнения не перебирать узлы.
Я попытался использовать ((->) ()) как Unmemo, но он дает те же результаты, что и nums :: [Int] - программа использует много памяти, что очевидно, запустив ее с помощью +RTS -s.
Есть ли способ реализовать Unmemo, что делает то, что я хочу?
