21

我看过另一篇关于这个的帖子，但是在 Haskell 中有没有一种干净的方法呢？

作为第二部分，它也可以在不使函数单子化的情况下完成吗？

4

5 回答 5

15

hackage 上的包 data-memocombinators 提供了许多可重用的记忆例程。基本思想是：

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]）。

于 2008-11-21T12:20:03.430 回答
12

您可以使用 unsafePerformIO 修​​改 Jonathan 的解决方案，以创建函数的“纯”记忆版本。

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))
于 2010-11-21T03:27:01.357 回答
9

这主要遵循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

所以，假设它是递归的。然后你需要它不是调用它自己，而是调用 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，您可以管理它，但明智地使用它取决于使用模式。

于 2008-10-03T21:48:27.673 回答
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的一个实例。

于 2008-09-26T22:06:16.237 回答
1

如果你的论点是自然数，你可以简单地做：

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

但是，这并不能真正帮助您解决堆栈溢出问题，并且它不适用于递归调用。您可以在http://www.haskell.org/haskellwiki/Memoization看到一些更高级的解决方案。

于 2008-09-26T22:03:49.143 回答