通过 Reader 在 Haskell 中将 Monad.Memo 与环境相结合

Question

我正在做 open source library for POMDP. It uses Dynamic Programming 搜索其他具有成本函数的 2D space。

DP 在 master branch is based on MemoTrie for DP memoization which uses Haskell's lazy evaluation. And I need to have cost function to be tunable. I believe this will not play nicely with MemoTrie's lazy approach. I did a naive try 中实施，但正如预期的那样，完成所有测试需要数小时而不是数秒。

我决定使用 Monad.Memo is a way to go. Here is 的 monadic 方法进行第一次尝试，尽管不使用任何 Reader 上下文。但是现在我正在努力寻找正确的方法来为这个计算引入 Reader 上下文。

这个try我用约束引入了MonadReader。同时，我无法将 fq 和 fv 的相互递归描述为约束，只是试图仅记忆 fq。但即便如此，MonadReader 类型 class MonadMemo 的实现将 Reader 上下文作为键的一部分，并且由于我的上下文是一个函数，它几乎不可能是映射键的（一部分）。我只能解开 Writer monad 的内容：

:t fst . startEvalMemo . runWriterT $ fq 1 1 1

也无法进一步解开 Reader。

上次尝试 use ReaderT。但这不能编译给出像

这样的东西

• Occurs check: cannot construct the infinite type: v ~ [v]
    arising from a functional dependency between:
      constraint ‘MapLike
                    (containers-0.5.7.1:Data.Map.Base.Map (n, n, n) [v]) (n, n, n) v’
        arising from a use of ‘memol1’
      instance ‘MapLike (containers-0.5.7.1:Data.Map.Base.Map k v1) k v1’
        at <no location info>
• In the first argument of ‘for3’, namely ‘memol1’
  In the expression: for3 memol1 fv n
  In an equation for ‘v’: v = for3 memol1 fv n
• Relevant bindings include
    v :: n -> n -> ReaderT (DynamicEnv n v) (MemoQV n v) v
      (bound at src/Dynamic.hs:136:9)

所以我在 Haskell 中努力提高生产力，但在我学习它的过程中，像这样的问题花了我很长时间。很高兴听到您的任何建议！

Answer 1

在使用 ReaderT 的版本中，您的 Dynamic monad 在 MemoQV 周围多了一层。

在伪haskell中，有：

type R = ReaderT (DynamicEnv n r)
type L1 = MemoQ n r
type L2 = MemoV n r

之前的类型看起来像

   L1 (L2 Identity)
-- 0   1

我们从 "top" 开始对变压器进行编号，从 0 开始。相比之下，Dynamic 现在看起来像

   R (L1 (L2 Identity))
-- 0  1   2

由于您在顶部插入了转换器 R，缓存转换器被移得更深。

这对 memol0、memol1 和 memol2 组合器很重要：memolN 使用第 N 层（因此预计具有匹配的类型），因此您需要在这些图层移动时相应地更新您的代码。

您使用memol1 here and memol0 here。当您分别将它们移动到 memol2 和 memol1 时，文件会编译。

通过 Reader 在 Haskell 中将 Monad.Memo 与环境相结合

Combine Monad.Memo with environment through Reader in Haskell

monads

haskell

memoization

monad-transformers