你如何在Haskell中创建一个通用的memoize函数？

Question

我见过关于此问题的其他帖子 ，但在Haskell中有一种干净的方法吗？

作为第二部分，是否可以在不使函数monadic的情况下完成？

Answer 1

这主要遵循 http://www.haskell.org/haskellwiki/Memoization 。

您需要类型（a - ＆gt; 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))

当然，记忆版本是我们想要定义的内容。

但我们可以从创建一个缓存其输入的函数开始：

我们可以通过传入一个创建一个的函数来构造一个级别 缓存值的结构。除了我们需要创建f的版本 已经传入的缓存函数。

由于懒惰，这没问题：

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

然后我们只需要使用它：

exposed_f = memoize cacher_for_f f

本文给出了如何使用类型类选择的提示 输入函数来执行上述操作，而不是选择显式 缓存功能。这可能非常好 - 而不是明确 我们可以隐式地为每种输入类型组合构建一个缓存 将类型a和b的高速缓存组合到一个带有a和b的函数的高速缓存中。

最后一点需要注意：使用这种懒惰技术意味着缓存永远不会缩小， 它只会增长。如果你改为使用IO monad，你可以管理它，但是 明智地做到这一点取决于使用模式。

Answer 2

hackage上的包数据memocombinators提供了许多可重用的memoization例程。基本思路是：

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

即。它可以记忆任何功能。然后该模块提供一些原语（如 unit :: Memo（）和 integral :: Memo Int ），以及用于构建更复杂的备忘录表的组合器（如对） ::备忘录a - ＆gt;备忘录b - ＆gt;备忘录（a，b）和 list ::备忘录a - ＆gt;备忘录[a] ）。

Answer 3

您可以使用unsafePerformIO修改Jonathan＆＃180的解决方案，以创建一个“纯粹”的解决方案。记下你的功能版本。

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 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 上看到一些更高级的解决方案。