logo标签列表

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

haskellmonadsmemoization
21

我看到了关于这个问题的其他帖子，但是在Haskell中有没有一种简洁的方法来做到这一点？

作为第二部分，能否在不将函数变为monadic的情况下完成？

我几乎不会拼写Haskell :), 但我不认为这个问题存在。据我所知，记忆化包含着纯函数式语言所不允许的那种静态状态。当然，使用单子可能会使其可行，我想。但你的第二部分有点表明你已经知道了。 - Mike G.
@Mike：我可能也会这么想，但实际上函数式语言可以很好地进行记忆化，正如答案所示。它们只需要通过函数参数传递状态即可。 - LarsH
5个回答
16

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

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))
1
这很好。如果您还能显示所需的导入语句，对于新手来说可能也会有所帮助。 - Thomas Ahle
不需要使用 unsafePerformIO。相同的代码可以在 ST monad 中执行。 - uhbif19
@uhbif19 是这样吗？我向你发起挑战，让你写出来（最终纯净的(a -> b)保持不变）。 - luqui
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

假设这是一个递归函数。那么你需要调用的不是它本身，而是记忆化后的版本，因此你要将其传递进去：

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模拟器，可以管理它，但明智地使用取决于使用模式。
我读了这个链接。我猜你需要创建一个新的类型类并实现它的接口，以便为您想要进行记忆化的任何类型进行记忆化处理。是否有办法在Memoize模块中编写代码，以节省该模块的用户的工作量？ - Jonathan Tran
你可以编写常见类型的缓存代码，并制定一些组合规则。如果它们使用了你未定义的类型，他们需要自己创建实例。 - wnoise
您还可以基于类型类（如Ord或Bound）创建实例，但每个实例应该放在单独的模块中--它们可能需要不同的缓存方案，因此需要选择不使用这些方案。 - wnoise
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的实例。

2
当然，无论是隐式的还是显式的，都无法避免某种形式的约束。例如，您如何记忆类型为（整数->布尔）->布尔的函数？ - luqui
1
如果您的参数将是自然数，您可以简单地执行以下操作：

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

然而，这并不能真正帮助您解决堆栈溢出问题，并且它也无法处理递归调用。您可以在http://www.haskell.org/haskellwiki/Memoization中看到一些更高级的解决方案。

这很有帮助，但我仍然觉得可能还有更普遍的东西。 - Jonathan Tran
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接