Запоминание дешевых побочных эффектов - PullRequest
Новая
       6

Запоминание дешевых побочных эффектов

2 голосов
/ 26 февраля 2012

Я бы хотел запомнить функцию с типом, скажем, 

f :: Int -> Integer

Что я мог бы легко сделать, например, используя пакет MemoCombinators , как таковой: 

f_ = Memo.integral f

Однако, когда дана пара (x, f x), есть много других точек, для которых легко вычислить f, учитывая f x: 

freebies :: (Int, Integer) -> [(Int, Integer)]

Но, учитывая точку x', вычислить немного x, для которого elem x' . map fst $ freebies (x, f x), не дешево. Поэтому я хотел бы сохранить эти дополнительные пары (x', y') по мере их появления, чтобы впоследствии можно было эффективно рассчитать f x'.

У меня такой вопрос, как можно запомнить такую ​​функцию?

1 Ответ

2 голосов
/ 26 февраля 2012

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

Предположим, что у вас есть: 

-- Representative k finds a k', where it is easy to calculate
-- k from (k')'s value (this calculation is the Value -> Value
-- function)
-- There should be multiple (k')'s per k; and representative k' 
-- on one of those should return (k', const v), where v is the
-- value.
representative :: Key -> (Key, Value -> Value)

Тогда вы можете запомнить: 

table = memoKey go
    where
    go k = let (k', vf) = representative k in
           vf (table k')

где memoKey - это памятка для Key.

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

Если вы не можете инвертировать freebies в форму representative, то я думаю, что вам не повезло с pure стратегиями запоминания.Это потому, что если вы сделаете это так, как вы предлагаете, значение в таблице халявы будет зависеть от того, что было оценено first , и это просто нет в чистом Haskell.(Даже если вы знаете, что значения будут одинаковыми, стратегия чистого запоминания не сможет даже зависеть от порядка оценки)

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

...