如何改进Haskell中返回状态的纯函数API？以memoize实现为例

问题描述 #

我想实现一个memoize函数，给定函数f后定义g = memoize f，调用g x后，后续以x为参数调用g时直接返回缓存结果。但当前实现需要显式传递缓存状态，写法繁琐：

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
      (* 原地更新h *)
      Hashtbl.add h x y;
      y
  in
  g

解决方案：用State Monad封装缓存状态 #

利用Control.Monad.State的State monad，可以把缓存的Map封装起来，彻底避免手动传递状态，同时保持纯函数特性（无原地突变，状态变化通过生成新Map实现）：

import qualified Data.Map as Map
import Control.Monad.State

memoize :: Ord t => (t -> a) -> t -> State (Map t a) a
memoize f x = do
  cache <- get
  case Map.lookup x cache of
    Just val -> return val
    Nothing -> do
      let val = f x
      put $ Map.insert x val cache
      return val

使用示例 #

main :: IO ()
main = do
  let memoPlusOne = memoize (+1)
      -- 首次调用：初始缓存为空，返回结果并生成新缓存
      (res1, cache1) = runState (memoPlusOne 1) Map.empty
      -- 二次调用：复用已缓存的结果，生成新缓存（与原缓存内容一致）
      (res2, cache2) = runState (memoPlusOne 1) cache1
  print res1  -- 输出 2
  print res2  -- 输出 2
  print cache2 -- 输出 fromList [(1,2)]

这里State monad自动处理了缓存的传递与更新逻辑，无需手动显式传递Map；同时所有状态变化都是显式生成新的Map，完全符合纯函数式编程的要求，和OCaml的原地突变实现有本质区别。

内容的提问来源于stack exchange，提问作者jtanza