Заметки на основе ключа

Question

В последнее время я играл с пакетами MemoCombinators и MemoTrie и пытался запоминать функцию, которая принимала дерево (которое на самом деле было замаскированным DAG, так как несколько узлов были общими). В форме:

data Tree k a = Branch (Tree k a) (k, a) (Tree k a) | Leaf (k, a)

Итак, я хочу запомнить функцию типа (в зависимости от ее ключа):

Tree k a -> b

Теперь у меня есть смутное понимание, что эти комбинаторы запоминания используются для превращения вашей функции f :: a -> a в структуру ленивых (неоцененных) значений a, так что когда вы извлекаете одно из них, оно уже оценивается. Так что это не будет проблемой для моего дерева - каким-то образом мне нужно будет превратить его в структуру значений, индексированных по k.

Я не мог понять, как это сделать с библиотеками комбинатора. Один из простых способов - создать функцию k -> a, которая индексирует карту, которая отлично вписывается, но выглядит немного неуклюже.

Я ошибся в этой цели или упустил что-то очевидное?

Я легко вижу, как написать эту функцию с таким стилем, явно пропуская мою "таблицу" через все вычисления:

f :: Tree Int Int -> Map Int Int -> (Int, Map Int Int)
f (Branch l (k, x) r) m | (Just r) <- lookup k m = r
                        | otherwise = (max rl rr, m'')
     where 
       (rl, m') = (f l m) 
       (rr, m'') = (f r m') 

Но это не так приятно.

Answer 1

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

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

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

Это довольно просто реализовать вручную:

module Temp where
import Prelude hiding (lookup)
import Control.Arrow ((&&&))
import Data.Map (fromList, lookup)

data Tree k a = Branch (Tree k a) (k, a) (Tree k a) | Leaf (k, a)

key :: Tree k a -> k
key (Leaf (k, _)) = k
key (Branch _ (k,_) _) = k

-- memoize a given function over the given trees
memoFor :: Ord k => [Tree k a] -> (Tree k a -> b) -> Tree k a -> b
memoFor ts f = f'
  where f' t = maybe (f t) id $ lookup (key t) m
        m = fromList $ map (key &&& f) ts

Что пытаются сделать пакеты MemoCombinators и MemoTriedo - сделать коллекцию входных данных неявной (используя функции и классы типов, репрезентативно).Если можно перечислить все возможные входные данные, то мы можем использовать это перечисление для построения нашей структуры данных.

В вашем случае, поскольку вы хотите помнить только key ваших деревьев, самый простой способ можетиспользовать функцию wrap из пакета MemoCombinators:

wrap :: (a -> b) -> (b -> a) -> Memo a -> Memo b

Учитывая памятник для a и изоморфизм между a и b, создайте памятник для b.

Итак, если ваши значения key имеют соответствующее значение Memo (например, type Key = Int), и у вас есть биекция от Key с до Tree Key Val, тогда выможно использовать эту биекцию для создания памятки для ваших Tree Key Val функций:

memoize :: (Tree Key Val -> b) -> (Tree Key Val -> b)
memoize = wrap keyToTree treeToKey memoForKey

---

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

{-# LANGUAGE FlexibleContexts #-}
-- ... 

import Control.Monad.State (MonadState, gets, modify)
import Data.Map (Map, insert)
-- ... 

memoM :: (Ord k, MonadState (Map k b) m) => (Tree k a -> m b) -> (Tree k a -> m b)
memoM f = f'
  where f' t = do
        let k = key t
        v <- gets $ lookup k
        case v of
          Just b -> return b
          Nothing -> do
            b <- f t
            modify $ insert k b
            return b

-- example of use
sumM :: (Ord k, MonadState (Map k Int) m) => Tree k Int -> m Int
sumM = memoM $ \t -> case t of
        Leaf (_,b) -> return b
        Branch l (_,b) r -> do
          lsum <- sumM l
          rsum <- sumM r
          return $ lsum + b + rsum