Краткосрочная памятка в Хаскеле?

Question

На объектно-ориентированном языке, когда мне нужно кэшировать / запоминать результаты функции в течение известного времени жизни, я обычно буду следовать этой схеме:

1. Создать новый класс
2. Добавьте в класс элемент данных и метод для каждого результата функции, который я хочу кэшировать
3. Реализуйте метод, чтобы сначала проверить, был ли результат сохранен в элементе данных.Если это так, верните это значение;else вызовите функцию (с соответствующими аргументами) и сохраните возвращенный результат в элементе данных.
4. Объекты этого класса будут инициализированы со значениями, необходимыми для различных вызовов функций.

Этот объектно-ориентированный подход очень похож на описанный здесь шаблон запоминания функций: http://www.bardiak.com/2012/01/javascript-memoization-pattern.html

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

Какие хорошие способы реализации короткихвоспоминания в Хаскеле?И зависит ли ответ от того, являются ли кэшируемые функции чистыми или включают в себя IO?

Просто повторю - было бы неплохо увидеть решения для функций, которые включают IO.

Answer 1

Давайте использовать библиотеку заметок Люка Палмера: Data.MemoCombinators

import qualified Data.MemoCombinators as Memo
import Data.Function (fix) -- we'll need this too

Я собираюсь определить вещи, немного отличающиеся от того, как его библиотека, но в основном это то же самое (и, кроме того, совместимо). «Запоминающаяся» вещь берет себя в качестве входных данных и производит «настоящую» вещь.

type Memoizable a = a -> a

«Памятка» берет функцию и создает ее памятную версию.

type Memoizer a b = (a -> b) -> a -> b

Давайте напишем небольшую функцию, чтобы соединить эти две вещи. Учитывая Memoizable функцию и Memoizer, нам нужна результирующая запомненная функция.

runMemo :: Memoizer a b -> Memoizable (a -> b) -> a -> b
runMemo memo f = fix (f . memo)

Это немного волшебства с использованием комбинатора точек фиксирования (fix). Не бери в голову это; Вы можете погуглить, если вы заинтересованы.

Итак, давайте напишем Memoizable версию классического примера fib:

fib :: Memoizable (Integer -> Integer)
fib self = go
  where go 0 = 1
        go 1 = 1
        go n = self (n-1) + self (n-2)

Использование соглашения self делает код простым. Помните, что self - это то, что мы ожидаем, чтобы стать запомненной версией этой самой функции, поэтому рекурсивные вызовы должны быть на self. Теперь запустите GHCI.

ghci> let fib' = runMemo Memo.integral fib
ghci> fib' 10000
WALL OF NUMBERS CRANKED OUT RIDICULOUSLY FAST

Крутая вещь в runMemo заключается в том, что вы можете создать более одной только что запомненной версии одной и той же функции, и они будут не совместно использовать банки памяти. Это означает, что я могу написать функцию, которая локально создает и использует fib', но затем, как только fib' выходит из области видимости (или раньше, в зависимости от интеллекта компилятора), может собирать мусор . Не нужно запоминать на верхнем уровне . Это может или не может хорошо играть с техниками запоминания, которые основаны на unsafePerformIO. Data.MemoCombinators использует чистый ленивый Trie, который идеально подходит для runMemo. Вместо того, чтобы создавать объект, который по сути становится менеджером заметок, вы можете просто создавать заметки по запросу. Уловка в том, что если ваша функция рекурсивная, она должна быть записана как Memoizable. Хорошей новостью является то, что вы можете подключить любой Memoizer, который пожелаете. Вы можете даже использовать:

noMemo :: Memoizer a b
noMemo f = f

ghci> let fib' = runMemo noMemo fib
ghci> fib' 30 -- wait a while; it's computing stupidly
1346269

Answer 2

Программирование Lazy-Haskell - своего рода парадигма запоминания, доведенная до крайности. Кроме того, все, что вы делаете на императивном языке, возможно в Haskell, используя либо монаду ввода-вывода, монаду ST, преобразователи монад, стрелки или любое другое имя.

Единственная проблема заключается в том, что эти абстракционные устройства намного сложнее, чем упомянутый вами императивный эквивалент, и им нужно довольно глубокое переосмысление.

Answer 3

Я полагаю, что оба приведенных выше ответа сложнее, чем необходимо, хотя они могут быть более портативными, чем то, что я собираюсь описать.

Насколько я понимаю, в ghc есть правило, согласно которому каждое значение вычисляется ровно один раз, когда вводится его лямбда-выражение. Таким образом, вы можете создать точно ваш недолгий объект памятки следующим образом.

import qualified Data.Vector as V
indexerVector :: (t -> Int) -> V.Vector t -> Int -> [t]
indexerVector idx vec = \e -> tbl ! e
  where m = maximum $ map idx $ V.toList vec
        tbl = V.accumulate (flip (:)) (V.replicate m []) 
                 (V.map (\v -> (idx v, v)) vec)

Что это делает? Он группирует все элементы в Data.Vector t, передаваемые в качестве второго аргумента vec, в соответствии с целым числом, вычисленным по его первому аргументу idx, сохраняя их группировку как Data.Vector [t]. Он возвращает функцию типа Int -> [t], которая ищет эту группировку по этому предварительно вычисленному значению индекса.

Наш компилятор ghc пообещал, что tbl будет прогреметь только один раз, когда мы вызовем indexerVector. Поэтому мы можем присвоить лямбда-выражение \e -> tbl ! e, возвращаемое indexVector, другому значению, которое мы можем использовать многократно, не опасаясь, что tbl когда-нибудь будет пересчитано. Вы можете проверить это, вставив trace в tbl.

Короче говоря, ваш кеширующий объект является именно этим лямбда-выражением.

Я обнаружил, что почти все, что вы можете сделать с помощью краткосрочного объекта, можно лучше выполнить, возвращая лямбда-выражение, подобное этому.

Answer 4

Вы можете использовать тот же шаблон в haskell.Ленивая оценка позаботится о проверке того, оценивается ли уже значение.Это уже упоминалось несколько раз, но пример кода может быть полезен.В приведенном ниже примере memoedValue будет рассчитываться только один раз, когда это требуется.

data Memoed = Memoed
  { value       :: Int
  , memoedValue :: Int
  }

memo :: Int -> Memoed
memo i = Memoed
  { value       = i
  , memoedValue = expensiveComputation i
  }

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

data Memoed = Memoed
  { value        :: Int
  , memoedValue1 :: Int
  , memoedValue2 :: Int
  }

memo :: Int -> Memoed
memo i = r
  where
  r = Memoed
    { value        = i
    , memoedValue1 = expensiveComputation i
    , memoedValue2 = anotherComputation (memoedValue1 r)
    }