在Haskell中的双参数记忆化

Question

我正在尝试对以下函数进行记忆化：

gridwalk x y
    | x == 0 = 1
    | y == 0 = 1
    | otherwise = (gridwalk (x - 1) y) + (gridwalk x (y - 1))

看了这个，我想到了以下解决方案：

gw :: (Int -> Int -> Int) -> Int -> Int -> Int
gw f x y
    | x == 0 = 1
    | y == 0 = 1
    | otherwise = (f (x - 1) y) + (f x (y - 1))

gwlist :: [Int]
gwlist = map (\i -> gw fastgw (i `mod` 20) (i `div` 20)) [0..]

fastgw :: Int -> Int -> Int
fastgw x y = gwlist !! (x + y * 20)

然后我可以这样调用：

gw fastgw 20 20

有没有更简单、更简洁、更通用的方法（注意，我不得不在 gwlist 函数中硬编码最大网格维度，以便将二维转换为一维空间，以便我可以访问记忆化列表）来记忆化Haskell中具有多个参数的函数？

- Philip Kamenarsky

Answer 1

您可以使用一个嵌套列表来对两个参数的函数结果进行记忆化：

memo :: (Int -> Int -> a) -> [[a]]
memo f = map (\x -> map (f x) [0..]) [0..]


gw :: Int -> Int -> Int
gw 0 _ = 1
gw _ 0 = 1
gw x y = (fastgw (x - 1) y) + (fastgw x (y - 1))

gwstore :: [[Int]]
gwstore = memo gw

fastgw :: Int -> Int -> Int
fastgw x y = gwstore !! x !! y

- sth

---

这应该放得更高一些。虽然不像其他答案那么简单，但这绝对是最有见地的答案。 - marcusklaas

Answer 2

使用来自Hackage的data-memocombinators包。它提供了易于使用的记忆化技术，并提供了一种简单而简洁的使用方法：

import Data.MemoCombinators (memo2,integral)

gridwalk = memo2 integral integral gridwalk' where
  gridwalk' x y
    | x == 0 = 1
    | y == 0 = 1
    | otherwise = (gridwalk (x - 1) y) + (gridwalk x (y - 1))

- fuz

---

网格遍历应该回调到gridwalkMemo而不是自身，对吗？ - HaskellElephant

我选择这个答案是因为它简洁明了且得票数较高，但是sth和John的回答都帮助我更好地理解Haskell中的记忆化技术，谢谢！ - Philip Kamenarsky

你可能需要执行 cabal install data-memocombinators。 - Sergey Orshanskiy

Answer 3

这里是使用MemoTrie包中的Data.MemoTrie来进行函数记忆化的版本：

import Data.MemoTrie(memo2)

gridwalk :: Int -> Int -> Int
gridwalk = memo2 gw
  where
    gw 0 _ = 1
    gw _ 0 = 1
    gw x y = gridwalk (x - 1) y + gridwalk x (y - 1)

- HaskellElephant

Answer 4

如果您想要最大的通用性，您可以对一个备忘函数进行备忘。

memo :: (Num a, Enum a) => (a -> b) -> [b]
memo f = map f (enumFrom 0)

gwvals = fmap memo (memo gw)

fastgw :: Int -> Int -> Int
fastgw x y = gwvals !! x !! y

这个技巧适用于具有任意数量参数的函数。

编辑：感谢 Philip K. 指出原始代码中的错误。原始的 memo 约束为“Bounded”，并从 minBound 开始枚举，这只对自然数有效。

列表不是一个很好的用于记忆化的数据结构，因为它们具有线性查找复杂度。您可能更适合使用 Map 或 IntMap。或者参考 Hackage 上的 MemoTrie、monad-memo 和 data-memocombinators。

请注意，这个特定的代码确实依赖于惰性计算，因此如果您想切换到使用 Map，您需要从列表中获取有限数量的元素，例如：

gwByMap :: Int -> Int -> Int -> Int -> Int
gwByMap maxX maxY x y = fromMaybe (gw x y) $ M.lookup (x,y) memomap
 where
  memomap = M.fromList $ concat [[((x',y'),z) | (y',z) <- zip [0..maxY] ys]
                                              | (x',ys) <- zip [0..maxX] gwvals]

fastgw2 :: Int -> Int -> Int
fastgw2 = gwByMap 20 20

在这种情况下，我认为ghc可能会对共享存在问题，您可能需要将x和y参数提取出来，如下所示：

gwByMap maxX maxY = \x y -> fromMaybe (gw x y) $ M.lookup (x,y) memomap

- John L

---

еҪ“memoжңҹжңӣдёҖдёӘзұ»еһӢдёә(a -> b)зҡ„еҮҪж•°пјҢдҪҶжҳҜgwжҳҜ(Int -> Int -> Int)ж—¶пјҢдҪ еҰӮдҪ•е°Ҷgwдј йҖ’з»ҷmemoпјҹжӯӨеӨ–пјҢеҪ“еә”з”ЁдәҺIntзұ»еһӢзҡ„жҹҗдәӣеҶ…е®№ж—¶пјҢminBoundдёҚдјҡдә§з”ҹиҙҹзҙўеј•еҗ—пјҹ - Philip Kamenarsky

@Philip K - a->b 中的类型 b 与 Int -> Int 合并是完全可以将函数生成器进行记忆化。不过负索引的问题是一个 bug，我会编辑我的回答。 - John L