Как сделать в Haskell универсальную функцию memoize?

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

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

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

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

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.

Это во многом следует за 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

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

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.

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

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

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

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

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

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))