Как сделать общую функцию памятки в Haskell?

Question

Я видел другой пост об этом , но есть ли чистый способ сделать это в Haskell?

Как 2-я часть, это также может быть сделано без монадической функции?

Answer 1

Пакет data-memocombinators для хакерства предоставляет множество подпрограмм многократного использования. Основная идея:

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

Answer 2

Вы можете изменить решение Джонатана с 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))

Answer 3

Это в значительной степени следует 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.

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

Answer 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 .

Answer 5

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

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

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