Как создать универсальную функцию запоминания в Haskell?
-
02-07-2019 - |
Вопрос
Я видел другой пост об этом, но есть ли чистый способ сделать это в Haskell?
Как 2-я часть, можно ли это также сделать, не делая функцию монадической?
Решение
Это в значительной степени следует 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.
И последнее предостережение:использование этого ленивого метода означает, что кэш никогда не уменьшается, он только растет.Если вы вместо этого используете монаду ввода-вывода, вы можете управлять этим, но выполнение этого с умом зависит от шаблонов использования.
Другие советы
Пакет 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]
).
Вы можете изменить решение 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))
Делая прямой перевод с более императивных языков, я пришел к следующему.
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.
Если ваши аргументы будут натуральными числами, вы можете сделать просто:
memo f = let values = map f [0..]
in \n -> values !! n
Однако это на самом деле не поможет вам с переполнением стека, и это не работает с рекурсивными вызовами.Вы можете ознакомиться с некоторыми более оригинальными решениями на сайте http://www.haskell.org/haskellwiki/Memoization.