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

我已经看过关于这个的另一篇文章了,但是在Haskell有一个干净的方法吗？

作为第二部分,还可以在不使功能monadic的情况下完成吗？

hackage上的数据包memocombinators提供了大量可重用的memoization例程.基本思路是:

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

即它可以记忆任何功能.然后,该模块提供一些原语(如unit :: Memo ()和integral :: Memo Int),以及用于构建更复杂的备忘录表(如pair :: Memo a -> Memo b -> Memo (a,b)和list :: Memo a -> Memo [a])的组合器.

您可以使用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))

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

所以,假设它是递归的.然后你需要它不是自己调用,而是记忆版本,所以你传递它:

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,你可以管理它,但明智地做它取决于使用模式.