Haskell 中的两个参数记忆

Question

我正在尝试记住以下函数：

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

看着 this 我想出了以下解决方案

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 函数中对最大网格尺寸进行硬编码，以便从 2D 空间转换为 1D 空间，所以我可以访问记忆列表）来记忆Haskell中具有多个参数的函数吗？

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

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))

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)

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”约束而不是“Num”，并从 minBound 开始枚举，这仅对自然数有效。

不过，列表并不是一种很好的记忆数据结构，因为它们具有线性查找复杂性。使用 Map 或 IntMap 可能会更好。或者查看 黑客。

请注意，此特定代码确实依赖于惰性，因此如果您想切换到使用 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