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

Question

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

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

Answer 1

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

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

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.

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

Answer 2

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

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

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

Answer 3

Вы можете изменить решение Jonathans с помощью 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 :: String -> [Int] -> Float
f ...

f_memo = curry (memoize (uncurry f))

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

Но это как-то неудовлетворительно.Также, Данные.Карта ограничивает параметр, чтобы он был экземпляром Ord.

Answer 5

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

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

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