我看到了关于这个问题的其他帖子,但是在Haskell中有没有一种简洁的方法来做到这一点?
作为第二部分,能否在不将函数变为monadic的情况下完成?
我看到了关于这个问题的其他帖子,但是在Haskell中有没有一种简洁的方法来做到这一点?
作为第二部分,能否在不将函数变为monadic的情况下完成?
在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]
)。
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))
unsafePerformIO
。相同的代码可以在 ST monad 中执行。 - uhbif19(a -> b)
保持不变)。 - luqui您需要一个类型为(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
memo f = let values = map f [0..]
in \n -> values !! n
然而,这并不能真正帮助您解决堆栈溢出问题,并且它也无法处理递归调用。您可以在http://www.haskell.org/haskellwiki/Memoization中看到一些更高级的解决方案。