如何改进 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