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

Ответ 1

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

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 и возвращает memoized версию той же функции. Любая функция, которая семантически идентична и имеет этот тип, называется "memoizer для Int" (даже id, которая не memoize). Мы обобщаем эту абстракцию:

type Memo a = forall r. (a -> r) -> (a -> r)

Итак, Memo a, memoizer для a, принимает функцию от a ко всему и возвращает семантически идентичную функцию, которая была memoized (или нет).

Идея различных memoizers заключается в том, чтобы найти способ перечислить домен с помощью структуры данных, сопоставить функцию над ними и затем индексировать структуру данных. 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 - это аналогичная история, но теперь нам нужно знать, как memoize a для случая Just. Таким образом, memoizer для Maybe принимает memoizer для 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 использует один и тот же базовый метод, но вместо представления combinator использует презентацию typeclass. Одновременно мы выпускали наши библиотеки (действительно, через пару часов!). Conal проще в использовании в простых случаях (существует только одна функция memo, и она будет определять структуру 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 и т.д. Но это боль в попке для использования, а также ограничивает строгость функции для запоминания (например, без бесконечной левой рекурсии). Я не верю, что есть библиотеки, которые реализуют эту технику.

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

Ответ 2

Сердце - это функция 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 показана простейшая стратегия memoization, использующая список, а раздел 3 делает то же самое, используя двоичное дерево naturals, аналогичное IntTree, используемому в memocombinators.

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

Следующий шаг - это memoizing функции с другими типами аргументов. Это делается с помощью функции wrap, которая использует изоморфизм между типами a и b для построения a Memo b из a 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, Либо и memoizing несколько аргументов.

Ответ 3

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

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

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

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

Ответ 4

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

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

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

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

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