Как вы делаете общую функцию memoize в Haskell?

Ответ 1

Это в значительной степени следует http://www.haskell.org/haskellwiki/Memoization.

Вам нужна функция типа (a → b). Если он не называет себя, то вы можете просто написать простую оболочку, которая кэширует возвращаемые значения. лучший способ сохранить это отображение зависит от того, какие свойства вы можете эксплуатируют. Заказ в значительной степени является минимальным. С целыми числами вы можете построить бесконечный ленивый список или дерево, содержащее значения.

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

positive_list_cacher :: Cacher Int b
positive_list_cacher f n = (map f [0..]) !! n

или

integer_list_cacher :: Cacher Int b
integer_list_cacher f n = (map f (interleave [0..] [-1, -2, ..]) !!
    index n where
        index n | n < 0  = 2*abs(n) - 1
        index n | n >= 0 = 2 * n

Итак, пусть это рекурсивный. Тогда вам нужно это, чтобы назвать не себя, но memoized версии, поэтому вы передаете это вместо:

f_with_memo :: (a -> b) -> a -> b
f_with_memo memoed base = base_answer
f_with_memo memoed arg  = calc (memoed (simpler arg))

Памятная версия - это, конечно же, то, что мы пытаемся определить.

Но мы можем начать с создания функции, которая кэширует свои входы:

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

Благодаря лень, это не проблема:

memoize cacher f = cached where
         cached = cacher (f cached)

тогда нам нужно всего лишь использовать его:

exposed_f = memoize cacher_for_f f

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

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

Ответ 2

Данные пакета-мемокомбинаторы при взломе предоставляют множество многократно используемых процедур memoization. Основная идея:

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

т.е. он может memoize любую функцию из. Затем модуль предоставляет некоторые примитивы (например, unit :: Memo () и integral :: Memo Int) и комбинаторы для построения более сложных таблиц memo (например, pair :: Memo a -> Memo b -> Memo (a,b) и list :: Memo a -> Memo [a]).

Ответ 3

Вы можете изменить решение Джонатана с помощью небезопасногоPerformIO, чтобы создать "чистую" memoizing версию вашей функции.

import qualified Data.Map as Map
import Data.IORef
import System.IO.Unsafe

memoize :: Ord a => (a -> b) -> (a -> b)
memoize f = unsafePerformIO $ do 
    r <- newIORef Map.empty
    return $ \ x -> unsafePerformIO $ do 
        m <- readIORef r
        case Map.lookup x m of
            Just y  -> return y
            Nothing -> do 
                    let y = f x
                    writeIORef r (Map.insert x y m)
                    return y

Это будет работать с рекурсивными функциями:

fib :: Int -> Integer
fib 0 = 1
fib 1 = 1
fib n = fib_memo (n-1) + fib_memo (n-2)

fib_memo :: Int -> Integer
fib_memo = memoize fib

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

f :: String -> [Int] -> Float
f ...

f_memo = curry (memoize (uncurry f))

Ответ 4

Выполняя прямой перевод с более императивных языков, я придумал это.

memoize :: Ord a => (a -> IO b) -> IO (a -> IO b)
memoize f =
  do r <- newIORef Map.empty
     return $ \x -> do m <- readIORef r
                       case Map.lookup x m of
                            Just y  -> return y
                            Nothing -> do y <- f x
                                          writeIORef r (Map.insert x y m)
                                          return y

Но это как-то неудовлетворительно. Кроме того, Data.Map ограничивает параметр как экземпляр Ord.

Ответ 5

Если ваши аргументы будут натуральными числами, вы можете сделать это просто:

memo f = let values = map f [0..]
     in \n -> values !! n

Однако это не поможет вам с переполнением стека и не работает с рекурсивными вызовами. Вы можете увидеть некоторые более благоприятные решения в http://www.haskell.org/haskellwiki/Memoization.