如何改进 Haskell 中返回状态的纯函数的 API？

Question

我正在尝试编写一个函数，该函数以某种方式f记忆某些函数f，在定义g = memoize f之后，g x所有后续的参数g调用x都会返回缓存的结果。

但是，我正在努力想出一种改进的实现，该实现改进了以下所需的显式状态传递：

memoize :: Ord t => (t -> a) -> Map t a -> t -> Map t a
memoize f m a = case Map.lookup a m of
    Just _  -> m
    Nothing -> Map.insert a (f a) m

用一个人为的例子来展示它的用法：

main :: IO ()
main = do
  let memoPlusOne = memoize (+ 1) in
    let m = memoPlusOne Map.empty 1
      in let mm = memoPlusOne m 1
        in print mm

我知道在 Haskell 中还有其他更好的方法来记忆函数，但我的问题更关心改进将状态传递给函数的一般模式，以避免任何状态突变，否则这些突变会像其他语言一样被封装，例如就像 Ocaml 中的这个例子一样：

let memo_rec f =
  let h = Hashtbl.create 16 in
  let rec g x =
    try Hashtbl.find h x
    with Not_found ->
      let y = f g x in
      (* update h in place *)
      Hashtbl.add h x y;
      y
  in
  g

Answer 1

Haskell 有一个安全、纯粹的用于突变的 API：在惰性求值中，thunk 在第一次输入时就地修改。所以！如果您想要一个执行突变的纯 API，您必须找到一种方法来使用惰性求值突变来满足您想要执行的任何其他突变的需求。

因此，这里的基本思想是，我们想要做的事情是让Map每个输入都可以作为键使用，但输出是等待评估的 thunk。理想情况下，我们没有调用该函数的输入也位于等待扩展的 thunk 中，这样我们就不会一开始Map内存就大得离谱。

不幸的是，Map它是严格的。这意味着我们无法合理地完成后一点（可变地扩展数据结构）；对于无限大的类型，我们不能做前一点（让每个键都可用）。所以我们必须自己做。我们将把弄清楚如何延迟枚举基于 new 的所有键的困难部分留给Tree类型Map类。

data Tree a = Tree a (Tree a) (Tree a) deriving Functor

class ToBits a where
    allValues :: Tree a
    toBits :: a -> [Bool]

我们需要一种方法来索引这些树。

index :: Tree a -> [Bool] -> a
index (Tree a _ _) [] = a
index (Tree _ f _) (False:path) = index f path
index (Tree _ _ t) (True :path) = index t path

我们将要求实例符合法律index allValues (toBits a) == a。通过这个类，我们可以快速编写我们的记忆功能：

memo :: ToBits a => (a -> b) -> (a -> b)
memo f = index (f <$> allValues) . toBits

例如，对于Integer，我们可以这样写：

instance ToBits Integer where
    allValues = Tree 0 (negate <$> go 1 0) (go 1 0) where
        go pow n = Tree (pow + n) (go (2*pow) n) (go (2*pow) (pow+n))
    toBits n = case compare n 0 of
        LT -> False:go (-n)
        EQ -> []
        GT -> True:go n
        where
        go 1 = []
        go n = let (q, r) = n `quotRem` 2 in (r==1) : go q

我们可以尝试一下。传统的事情是fib：

fib :: Integer -> Integer
fib n = if n < 2
    then n
    else fib (n-1) + fib (n-2)

mfib :: Integer -> Integer
mfib = memo fib

在 ghci 中：

> mfib 30
832040
(1.05 secs, 519,591,368 bytes)
> mfib 30
832040
(0.00 secs, 75,120 bytes)

好的。除了...传统上，记忆版本fib对于真正大的输入来说工作得非常快，而这个...则不然。这是怎么回事？

好吧，我们已经记住了fib——也就是说，如果我们调用mfib，fib只有当我们传递了一个它以前从未见过的新号码时，它才会调度到 。但其本身的实现fib并未使用记忆版本。对此我们可以做很多事情。库中的标准技巧是公开 -alikefix而不是memo如此处所示。但只要我们要求用户更改他们想要记忆的递归函数的定义，我们就可以内联进行。所以另一种选择是：

mfib' :: Integer -> Integer
mfib' = memo $ \n -> if n < 2
    then n
    else mfib' (n-1) + mfib' (n-2)

现在，我们的 memoized 的定义根据需要fib称为 memoized 。fib而且，正如所希望的那样，现在即使在第一次调用时速度也快得多。它仍然在做记忆的事情，我们只需要尝试更大的输入就能注意到。

> mfib' 30
832040
(0.00 secs, 248,096 bytes)
> mfib' 10000
<a truly enormous number>
(0.33 secs, 167,152,008 bytes)
> mfib' 10000
<a truly enormous number>
(0.01 secs, 1,650,816 bytes)