Haskell中的两个参数memoization

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函数中的最大网格尺寸以便从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

下面是使用一个版本Data.MemoTrie从MemoTrie包memoize的功能:

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)