用Monad.Memo記憶在Haskell中進行相互遞歸

Question

我正在用相互遞歸實現在Haskell中進行一些動態編程。

我決定使用memoization加快速度。

Monad.Memo爲這種情況提供了MemoT轉換器。但它使用Map作爲存儲值的內部表示。雖然這給了我數量級的速度提升，但還不夠。

儘管lib支持基於數組和基於矢量的實現作爲內部存儲，但它僅適用於簡單遞歸，並且我沒有發現任何像MemoT這樣的變換器將它用於相互遞歸。

使用基於高效矢量的內部表示（如果有）進行相互遞歸記憶的最佳方式是什麼？

我的下一個問題是關於記憶效應。所以我期望我的功能在第一次運行時需要更多的時間，而在連續運行時則少得多。但是我發現每次使用ghci的時間都是一樣的。所以第一次和第二次運行沒有區別。我測量時間如下：

timeit $ print $ dynamic (5,5) 

隨着動態是我的功能。

全面落實如下：

import Control.Monad.Memo 
import Control.Monad.Identity 

type Pos = (Int, Int) 

type MemoQ = MemoT (Int, Int, Int) [Int] 
type MemoV = MemoT (Int, Int, Int) Int 
type MemoQV = MemoQ (MemoV Identity) 

-- we are moving to (0,0) as we can always shift the world by substituting variables 
-- due to symmetry of cost function it is enougth to solve for only positive x and y 
dynamic :: Pos -> [Int] 
dynamic (x, y) = lastUnique $ map (evalQ x y) [1 ..] 
    where lastUnique (x0:x1:xs) | x0 == x1 = x0 
           | otherwise = lastUnique (x1:xs) 

evalQ :: Int -> Int -> Int -> [Int] 
evalQ x y n = startEvalMemo . startEvalMemoT $ fqmon x y n 

fqmon :: Int -> Int -> Int -> MemoQV [Int] 
fqmon _ _ 0 = return [0,0,0,0] 
fqmon x y n = do 
    let pts = neighbours (x, y) 
    let v = for3 memol1 fvmon n 
    let c = cost (x, y) 
    let q = fmap (c +) . uncurry v 
    traverse q pts 

fvmon :: Int -> Int -> Int -> MemoQV Int 
fvmon _ 0 0 = return 0 
fvmon 0 x y = return $ cost (x, y) 
fvmon n x y | limit  = return 1000000 
      | otherwise = liftM minimum $ for3 memol0 fqmon x' y' (n - 1) 
      where x' = abs x 
       y' = abs y 
       limit = x' > 25 || y' > 25 

cost :: Pos -> Int 
cost (x, y) = abs x + abs y 

neighbours :: Pos -> [Pos] 
neighbours (x, y) = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)] 

---

補充：

根據#liqui評論我試過memcombinators。

所以首先是非memoized初步實現：

type Pos = (Int, Int) 

dynamic :: Int -> Int -> [Int] 
dynamic x y = lastUnique $ map (fq x y) [1 ..] 
    where lastUnique (x0:x1:xs) | x0 == x1 = x0 
           | otherwise = lastUnique (x1:xs) 

fq :: Int -> Int -> Int -> [Int] 
fq _ _ 0 = [0, 0, 0, 0]   -- Q at 0 step is 0 in all directions 
fq x y n = (cost (x, y) +) . (uncurry $ fv n) <$> neighbours (x, y) 

fv :: Int -> Int -> Int -> Int 
fv _ 0 0 = 0    -- V at (0, 0) is 0 at any atep 
fv 0 x y = cost (x, y)  -- V at 0 step is a cost 
fv n x y = minimum $ fq x y (n - 1) 

cost :: Pos -> Int 
cost (x, y) = abs x + abs y 

neighbours :: Pos -> [Pos] 
neighbours (x, y) = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)] 

然後我試圖memization（只變更部分）：

dynamic :: Int -> Int -> [Int] 
dynamic x y = lastUnique $ map (fqmem x y) [1 ..] 
    where lastUnique (x0:x1:xs) | x0 == x1 = x0 
           | otherwise = lastUnique (x1:xs) 
-- memoizing version of fq 
fqmem :: Int -> Int -> Int -> [Int] 
fqmem x y n = fqmem' x y n 
    where fqmem' = memo3 integral integral integral fq 

-- memoizing version of fv 
fvmem :: Int -> Int -> Int -> Int 
fvmem n x y = fvmem' n x y 
    where fvmem' = memo3 integral integral integral fv 

fq :: Int -> Int -> Int -> [Int] 
fq _ _ 0 = [0, 0, 0, 0]   -- Q at 0 step is 0 in all directions 
fq x y n = (cost (x, y) +) . (uncurry $ fvmem n) <$> neighbours (x, y) 

fv :: Int -> Int -> Int -> Int 
fv _ 0 0 = 0    -- V at (0, 0) is 0 at any atep 
fv 0 x y = cost (x, y)  -- V at 0 step is a cost 
fv n x y = minimum $ fqmem x y (n - 1) 

結果有點矛盾的。它比非記憶遞歸實現慢3倍。僅記憶一個函數（即fq）而不觸摸fv會使結果慢兩倍。用memcombinators記憶越多，計算就越慢。第一次和第二次調用之間沒有區別。

也是最後一個問題。在Monad.Memo或memcombinators或MemotTrie之間進行選擇的理由是什麼？在評論中使用最後2點是有意義的。當Monad.Memo是更好的選擇時，情況如何？

Answer 1

最後MemoTrie完成了這項工作。 第一次調用它的工作速度（可能快得多）比Monad.Memo快，並且在連續的調用中幾乎不需要任何時間！

而在代碼THA變化是微不足道相比，一元的方式：

import Data.MemoTrie 

type Pos = (Int, Int) 

-- we are moving to (0,0) as we can always shift the world by substituting variables 
-- due to symmetry it is enougth to solve for only positive x and y 

dynamic :: Int -> Int -> [Int] 
dynamic x y = lastUnique $ map (fqmem x y) [1 ..] 
    where lastUnique (x0:x1:xs) | x0 == x1 = x0 
           | otherwise = lastUnique (x1:xs) 

fqmem = memo3 fq 
fvmem = memo3 fv 

fq :: Int -> Int -> Int -> [Int] 
fq _ _ 0 = [0, 0, 0, 0]   -- Q at 0 step is 0 in all directions 
fq x y n = (cost (x, y) +) . (uncurry $ fvmem n) <$> neighbours (x, y) 

fv :: Int -> Int -> Int -> Int 
fv _ 0 0 = 0    -- V at (0, 0) is 0 at any atep 
fv 0 x y = cost (x, y)  -- V at 0 step is a cost 
fv n x y = minimum $ fqmem x y (n - 1) 

cost :: Pos -> Int 
cost (x, y) = abs x + abs y 

neighbours :: Pos -> [Pos] 
neighbours (x, y) = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)] 

不過我想知道什麼是使用Monad.Memo的好處，什麼是用例是什麼？或者MemoTrie過時了嗎？

Memocombinators爲什麼沒有爲我工作？

在Monad.Memo，Memocombinators或MemoTrie之間進行選擇的經驗法則是什麼？