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

StackOverflow https://stackoverflow.com/questions/4980102

Вопрос

Я искал источник для Data.MemoCombinators но я не могу понять, в чем тут суть.

Пожалуйста, объясните мне, какая логика стоит за всеми этими комбинаторами и механика о том, как они на самом деле ускоряют вашу программу в реальном программировании.

Я ищу конкретику для этот реализация и, при необходимости, сравнение/контраст с другими подходами Haskell к мемоизации.Я понимаю, что такое мемоизация, и занимаюсь этим нет ищу описание как это работает в целом.

Это было полезно?

Решение

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

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, библиотека MemoTrie от Conal использует ту же базовую технику, но вместо представления комбинатора использует представление класса типов.Мы выпустили наши библиотеки независимо одновременно (действительно, в течение пары часов!).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, Once и запоминанию нескольких аргументов.

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

Библиотека Люка — это вариант библиотеки 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), и если так, почему именно?

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top