16

我正在尝试记住以下功能：

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

4

4 回答 4

19

您可以使用列表列表来记忆两个参数的函数结果：

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
于 2011-04-05T14:19:48.777 回答
9

使用来自 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))
于 2011-04-05T15:06:51.980 回答
5

Here is a version using Data.MemoTrie from the MemoTrie package to memoize the function:

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)
于 2011-04-05T15:12:35.693 回答
3

If you want maximum generality, you can memoize a memoizing function.

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

This technique will work with functions that have any number of arguments.

Edit: thanks to Philip K. for pointing out a bug in the original code. Originally memo had a "Bounded" constraint instead of "Num" and began the enumeration at minBound, which would only be valid for natural numbers.

Lists aren't a good data structure for memoizing, though, because they have linear lookup complexity. You might be better off with a Map or IntMap. Or look on Hackage.

Note that this particular code does rely on laziness, so if you wanted to switch to using a Map you would need to take a bounded amount of elements from the list, as in:

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

I think ghc may be stupid about sharing in this case, you may need to lift out the x and y parameters, like this:

gwByMap maxX maxY = \x y -> fromMaybe (gw x y) $ M.lookup (x,y) memomap
于 2011-04-05T14:46:18.490 回答