我已经看过另一篇有关此的文章，但是在Haskell中有没有一种干净的方法可以做到这一点？

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

解决方案

如果参数将是自然数，则可以执行以下操作：

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

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

我从更命令性的语言中直接翻译而成，我想到了这一点。

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的实例。

这很大程度上遵循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，则可以进行管理，但是
明智地执行此操作取决于使用模式。

关于黑客的软件包数据备忘录提供了许多可重用的记忆例程。基本思想是：

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

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

我们可以使用unsafePerformIO修改Jonathans解决方案，以创建函数的"纯"备注版本。

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

尽管此示例是一个带有一个整数参数的函数，但是备忘录的类型告诉我们它可以与任何具有可比较类型的函数一起使用。如果函数具有多个参数，则在应用备忘录之前将它们分组为一个元组。 F.i .：

f :: String -> [Int] -> Float
f ...

f_memo = curry (memoize (uncurry f))