Два параметра memoization в Haskell

Я пытаюсь memoize следующую функцию:

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 в одномерное пространство, чтобы я мог получить доступ к списку memoizing) для memoize-функций с несколькими параметрами в Haskell?

Ответы

Ответ 1

Используйте пакет 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))

Ответ 2

Вы можете использовать список списков для memoize результата функции для обоих параметров:

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

Ответ 3

Вот версия, использующая Data.MemoTrie из пакета 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)

Ответ 4

Если вам нужна максимальная общность, вы можете memoize функцию memoizing.

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

Этот метод будет работать с функциями, имеющими любое количество аргументов.

Редактировать: спасибо Филиппу К. за указание на ошибку в исходном коде. Первоначально memo имел ограничение "Ограниченный" вместо "Num" и начинал перечисление в minBound, что было бы справедливо только для натуральных чисел.

Списки не являются хорошей структурой данных для memoizing, хотя, поскольку они имеют сложность линейного поиска. Возможно, вам будет лучше с помощью Map или IntMap. Или посмотреть on Hackage.

Обратите внимание, что этот конкретный код полагается на лень, поэтому, если вы хотите переключиться на использование Карты, вам нужно будет взять ограниченное количество элементов из списка, например:

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