Combine Monad.Memo with environment through Reader in Haskell

Question

I'm doing open source library for POMDP. It uses Dynamic Programming under the hood to search other 2D space with some cost function.

DP implementation in 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 but as expected it takes hours to get through all tests instead of seconds.

I decided monadic approach with Monad.Memo is a way to go. Here is a first try that works though don't use any Reader context. But now I'm struggling with proper way to introduce Reader context for this computation.

This try I used constraints to introduce MonadReader. At the same time I was not able to describe mutual recurrence for fq and fv as a constraint, just tried to memoize only fq. But even then MonadReader type class implementation of MonadMemo puts Reader context as part of key and as my context is a function it hardly could be a (part of) key for mapping. I was only able to unwrap stuff up to Writer monad:

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

And was not able to go further to unwrap the Reader as well.

Last try I tried to use ReaderT. But this not compiles giving stuff like

• 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)

So I'm struggling to be productive in Haskell but as I'm learning it questions like this take me long time. Would be happy to hear any advise from you!

Answer 1

In the version using ReaderT, your Dynamic monad has one more layer around MemoQV.

In pseudo-haskell, with:

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

The type before looked like

   L1 (L2 Identity)
-- 0   1

where we numbered transformers counting from the "top" starting from 0. In contrast, Dynamic now looks like

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

Since you inserted the transformers R at the top, the cache transformers were shifted deeper.

This matters to memol0, memol1 and memol2 combinators: memolN memoizes a computation using the Nth layer (which is thus expected to have a matching type), so you need to update your code accordingly when these layers move.

You use memol1 here and memol0 here. The file compiles when you shift them up to memol2 and memol1 respectively.