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

Question

Я видел the other post about this, но есть ли чистый способ сделать это в Haskell?

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

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

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

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

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

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

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

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

exposed_f = memoize cacher_for_f f 

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

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

Answer 2

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

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

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

Answer 3

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

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 4

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

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

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

Answer 5

Вы можете изменить решение Jonathan с помощью 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 

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

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

f_memo = curry (memoize (uncurry f))