Как работают Data.MemoCombinators?

Эта библиотека представляет собой прямую комбинаторизацию хорошо известной техники запоминания. Начнем с канонического примера:

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) путем перечисления домена.

Запоминание 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 и т. д. Но использовать это неудобно, а также накладывает ограничения строгости на функцию, которая должна быть запомнена (например, отсутствие бесконечной левой рекурсии). Я не верю, что есть библиотеки, реализующие эту технику.

Это ответ на то, что вам было интересно? Если нет, возможно, поясните, в чем вы запутались?

Сердце - это bits функция:

-- | Memoize an ordered type with a bits instance.
bits :: (Ord a, Bits a) => Memo a
bits f = IntTrie.apply (fmap f IntTrie.identity)

Это единственная функция (кроме тривиального unit :: Memo ()), которая может дать вам значение Memo a. Он использует ту же идею, что и на этой странице о мемоизации Haskell. В разделе 2 показана простейшая стратегия мемоизации с использованием списка, а в разделе 3 то же самое с использованием двоичного дерева натуральных чисел, аналогичного IntTree, используемому в мемокомбинаторах.

Основная идея - использовать конструкцию типа (map fib [0 ..] !!) или в случае мемокомбинаторов - IntTrie.apply (fmap f IntTrie.identity). Здесь следует отметить соответствие между IntTie.apply и !!, а также между IntTrie.identity и [0..].

Следующий шаг - запоминание функций с другими типами аргументов. Это делается с помощью функции wrap, которая использует изоморфизм между типами a и b для создания Memo b из Memo a. Например:

Memo.integral f
=>
wrap fromInteger toInteger bits f
=>
bits (f . fromInteger) . toInteger
=>
IntTrie.apply (fmap (f . fromInteger) IntTrie.identity) . toInteger
~> (semantically equivalent)
(map (f . fromInteger) [0..] !!) . toInteger

Остальная часть исходного кода имеет дело с такими типами, как List, Maybe, Either и запоминанием нескольких аргументов.

Часть работы выполняется IntTrie: http://hackage.haskell.org/package/data-inttrie-0.0.4

Библиотека Люка является разновидностью библиотеки Conal MemoTrie, которую он описал здесь: http://conal.net/blog/posts/elegant-memoization-with-functional-memo-tries/

Некоторое дальнейшее расширение - общее понятие функциональной мемоизации состоит в том, чтобы взять функцию из a -> b и сопоставить ее со структурой данных, проиндексированной всеми возможными значениями a и содержащей значения b. Такая структура данных должна быть ленивой по двум причинам - во-первых, она должна быть ленивой в значениях, которые она хранит. Во-вторых, он должен производиться лениво. Первый по умолчанию на нестрогом языке. Последнее достигается с помощью обобщенных попыток.

Различные подходы мемокомбинаторов, мемотри и т. Д. - все это просто способы создания композиций из частей попыток над отдельными типами структур данных, чтобы обеспечить простое построение попыток для все более сложных структур.

@luqui Мне непонятно одно: имеет ли он такое же рабочее поведение, как следующее:

fib :: [Int]
fib = map fib' [0..]
    where fib' 0 = 0
             fib' 1 = 1
             fib' n = fib!!(n-1) + fib!!(n-2)

Вышеупомянутое должно запоминать fib на верхнем уровне, и, следовательно, если вы определяете две функции:

f n = fib!!n + fib!!(n+1)

Если затем вычислить f 5, мы получим, что fib 5 не пересчитывается при вычислении fib 6. Мне неясно, имеют ли комбинаторы мемоизации такое же поведение (т.е. мемоизация верхнего уровня вместо запрета только на перерасчет «внутри» вычисления fib), и если да, то почему именно?