Haskell:递归回忆录

Question

如果我有以下功能：

go xxs t i
  | t == 0         = 1
  | t < 0          = 0
  | i < 0          = 0
  | t < (xxs !! i) = go xxs t (i-1)
  | otherwise      = go xxs (t - (xxs !! i)) (i-1) + go xxs t (i-1)

回忆结果的最好方法是什么？我似乎无法理解如何存储一组动态元组，并同时更新和返回值。

与我在python中所做的相同的是：

def go(xxs, t , i, m):
  k = (t,i)
  if  k in m:      # check if value for this pair is already in dictionary 
      return m[k]
  if t == 0:
      return 1
  elif t < 0:
      return 0
  elif i < 0:
      return 0
  elif t < xxs[i]:
      val = go(xxs, t, i-1,m)  
  else:
      val = (go(xxs, total - xxs[i]), i-1,m) + go(xxs, t, i-1,m)
  m[k] = val  # store the new value in dictionary before returning it
  return val

编辑:我认为这与this answer有些不同。所讨论的函数有一个线性级数，您可以用list [1..]索引结果。在这种情况下，我的密钥(t,i)不一定是有序的或增量的。例如，我可能会得到一组密钥，这些密钥是

[(9,1),(8,2),(7,4),(6,4),(5,5),(4,6),(3,6),(2,7),(1,8),(0,10)]

Answer 1

有没有更容易的方式来翻阅你自己的回忆录？

比什么容易？一个单一的状态是非常容易的，如果你习惯于不择手段地思考，那么它也应该是直观的。

使用向量而不是列表的完整内联版本如下：

{-# LANGUAGE MultiWayIf #-}
import Control.Monad.Trans.State as S
import Data.Vector as V
import Data.Map.Strict as M

goGood :: [Int] -> Int -> Int -> Int
goGood xs t0 i0 =
    let v = V.fromList xs
    in evalState (explicitMemo v t0 i0) mempty
 where
 explicitMemo :: Vector Int -> Int -> Int -> State (Map (Int,Int) Int) Int
 explicitMemo v t i = do
    m <- M.lookup (t,i) <$> get
    case m of
        Nothing ->
         do res <- if | t == 0          -> pure 1
                      | t < 0           -> pure 0
                      | i < 0           -> pure 0
                      | t < (v V.! i)   -> explicitMemo v t (i-1)
                      | otherwise       -> (+) <$> explicitMemo v (t - (v V.! i)) (i-1) <*> explicitMemo v t
 (i-1)
            S.modify (M.insert (t,i) res)
            pure res
        Just r  -> pure r

也就是说，如果我们已经计算了结果，我们就在地图中查找。如果是，则返回结果。如果没有，则在返回结果之前计算和存储结果。

我们只需要几个助手函数就可以清理这一切：

prettyMemo :: Vector Int -> Int -> Int -> State (Map (Int,Int) Int) Int
prettyMemo v t i = cachedReturn =<< cachedEval (
            if | t == 0          -> pure 1
               | t < 0           -> pure 0
               | i < 0           -> pure 0
               | t < (v V.! i)   -> prettyMemo v t (i-1)
               | otherwise       ->
                   (+) <$> prettyMemo v (t - (v V.! i)) (i-1)
                       <*> prettyMemo v t (i-1)
            )
 where
 key = (t,i)
 -- Lookup value in cache and return it
 cachedReturn res = S.modify (M.insert key res) >> pure res

 -- Use cached value or run the operation
 cachedEval oper = maybe oper pure =<< (M.lookup key <$> get)

现在，我们的地图查找和地图更新是在一些简单的(对经验丰富的Haskell开发人员)帮助函数中完成的，这些函数包装了整个计算。这里的一个小区别是，我们更新了地图，而不管计算是否缓存在一些较小的计算成本上。

我们可以通过删除monad (参见链接相关的问题)来使其更加清晰。有一个流行的包(MemoTrie)为您处理内脏：

memoTrieVersion :: [Int] -> Int -> Int -> Int
memoTrieVersion xs = go
 where
 v = V.fromList xs
 go t i | t == 0 = 1
        | t < 0  = 0
        | i < 0  = 0
        | t < v V.! i = memo2 go t (i-1)
        | otherwise   = memo2 go (t - (v V.! i)) (i-1) + memo2 go t (i-1)

如果您喜欢一元风格，您可以始终使用monad-memo包。

编辑:将Python代码直接翻译到Haskell显示了一个重要的区别，那就是变量的不可变性。在otherwise (或else)情况下，您使用go两次，隐式地，一次调用将更新第二个调用所使用的缓存(m)，从而以回忆录的方式节省计算。在Haskell中，如果您要避免单变量和延迟计算来递归地定义一个向量(它可能非常强大)，那么最简单的解决方案是显式地传递您的映射(字典)：

import Data.Vector as V
import Data.Map as M

goWrapped :: Vector Int -> Int -> Int -> Int
goWrapped xxs t i = fst $ goPythonVersion xxs t i mempty

goPythonVersion :: Vector Int -> Int -> Int -> Map (Int,Int) Int -> (Int,Map (Int,Int) Int)
goPythonVersion xxs t i m =
  let k = (t,i)
  in case M.lookup k m of -- if  k in m:
    Just r -> (r,m)       --     return m[k]
    Nothing ->
      let (res,m') | t == 0 = (1,m)
                   | t  < 0 = (0,m)
                   | i  < 0 = (0,m)
                   | t  < xxs V.! i = goPythonVersion xxs t (i-1) m
                   | otherwise  =
                      let (r1,m1) = goPythonVersion xxs (t - (xxs V.! i)) (i-1) m
                          (r2,m2) = goPythonVersion xxs t (i-1) m1
                      in (r1 + r2, m2)
      in (res, M.insert k res m')

虽然这个版本是Python的一个不错的翻译，但我更希望看到一个更地道的解决方案，如下所示。注意，我们将一个变量绑定到结果的计算( Int和更新的映射称为“计算”)，但是由于延迟评估，除非缓存没有产生结果，否则不会做太多的工作。

{-# LANGUAGE ViewPatterns #-}
{-# LANGUAGE TupleSections #-}
goMoreIdiomatic:: Vector Int -> Int -> Int -> Map (Int,Int) Int -> (Int,Map (Int,Int) Int)
goMoreIdiomatic xxs t i m =
  let cached = M.lookup (t,i) m
      ~(comp, M.insert (t,i) comp -> m')
        | t == 0 = (1,m)
        | t  < 0 = (0,m)
        | i  < 0 = (0,m)
        | t  < xxs V.! i = goPythonVersion xxs t (i-1) m
        | otherwise  =
           let (r1,m1) = goPythonVersion xxs (t - (xxs V.! i)) (i-1) m
               (r2,m2) = goPythonVersion xxs t (i-1) m1
           in (r1 + r2, m2)
    in maybe (comp,m') (,m) cached