Эта библиотека представляет собой простую комбинаторизацию хорошо известного метода запоминания.Давайте начнем с канонического примера:
fib = (map fib' [0..] !!)
where
fib' 0 = 0
fib' 1 = 1
fib' n = fib (n-1) + fib (n-2)
Я понимаю, что вы сказали, что вы знаете, как и почему это работает.Поэтому я сосредоточусь на комбинаторизации.
Мы по существу пытаемся уловить и обобщить идею (map f [0..] !!).Тип этой функции - (Int -> r) -> (Int -> r), что имеет смысл: она берет функцию из Int -> r и возвращает запомненную версию той же функции.Любая функция, которая семантически идентична и имеет этот тип, называется «памяткой для Int» (даже id, которая не запоминает).Мы обобщаем эту абстракцию:
type Memo a = forall r. (a -> r) -> (a -> r)
Таким образом, Memo a, памятник для a, берет функцию из a во что угодно и возвращает семантически идентичную функцию, которая была запомнена (илине).
Идея различных памятников заключается в том, чтобы найти способ перечислить домен со структурой данных, отобразить функцию над ними и затем проиндексировать структуру данных.Хороший пример - bool:
bool :: Memo Bool
bool f = table (f True, f False)
where
table (t,f) True = t
table (t,f) False = f
Функции из Bool эквивалентны парам, за исключением того, что пара будет оценивать каждый компонент только один раз (как в случае каждого значения, которое находится за пределами лямбды),Таким образом, мы просто отображаем пару и обратно.Существенным моментом является то, что мы поднимаем оценку функции над лямбда-аргументом (здесь последний аргумент table), перечисляя домен.
Memoizing Maybe a - похожая история, за исключениемТеперь нам нужно знать, как запоминать a для случая Just.Таким образом, памятник для Maybe принимает в качестве аргумента памятку для a:
maybe :: Memo a -> Memo (Maybe a)
maybe ma f = table (f Nothing, ma (f . Just))
where
table (n,j) Nothing = n
table (n,j) (Just x) = j x
Остальная часть библиотеки - всего лишь варианты этой темы.
Способ, которым она запоминает интегральнуюТипы используют более подходящую структуру, чем [0..].Он немного сложен, но в основном просто создает бесконечное дерево (представляющее числа в двоичном виде для выяснения структуры):
1
10
100
1000
1001
101
1010
1011
11
110
1100
1101
111
1110
1111
Так что поиск числа в дереве имеет время выполнения, пропорциональное числубиты в его представлении.
Как указывает sclv, библиотека Conal MemoTrie использует ту же базовую технику, но использует представление класса типов вместо представления комбинатора.Мы выпустили наши библиотеки в одно и то же время независимо (на самом деле, в течение пары часов!).Conal проще использовать в простых случаях (есть только одна функция, memo, и она будет определять структуру памятки для использования на основе типа), тогда как моя более гибкая, так как вы можете делать такие вещи:
boundedMemo :: Integer -> Memo Integer
boundedMemo bound f = \z -> if z < bound then memof z else f z
where
memof = integral f
, который запоминает только значения, меньшие заданной границы, необходимые для реализации одной из проблем проекта Эйлера.
Существуют и другие подходы, например, предоставление функции открытой точки привязки над монадой.:
memo :: MonadState ... m => ((Integer -> m r) -> (Integer -> m r)) -> m (Integer -> m r)
, что обеспечивает еще большую гибкость, например.очистка кешей, LRU и т. д. Но использование задницы - это боль, а также накладывает ограничения строгости на функцию, подлежащую запоминанию (например, отсутствие бесконечной левой рекурсии).Я не верю, что есть какие-либо библиотеки, которые реализуют эту технику.
Это ответило на то, что вам было интересно?Если нет, то, возможно, четко изложите те моменты, которые вас смущают?