Запоминание двух параметров в Haskell - PullRequest
Новая
       5

Запоминание двух параметров в Haskell

14 голосов
/ 05 апреля 2011

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

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 ]

14 голосов
/ 05 апреля 2011

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

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
9 голосов
/ 05 апреля 2011

Используйте пакет data-memocombinators от hackage. Он предоставляет простые в использовании методы запоминания и предоставляет простой и краткий способ их использования: 

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))
5 голосов
/ 05 апреля 2011

Вот версия, использующая 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)
3 голосов
/ 05 апреля 2011

Если вам нужна максимальная универсальность, вы можете запомнить функцию запоминания. 

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, что было бы допустимо только для натуральных чисел.

Списки не являются хорошей структурой данных для запоминания,хотя, потому что они имеют линейную сложность поиска.Вам может быть лучше с картой или IntMap.Или посмотрите на 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
...