ハスケルでMonad.Memoと環境をリーダーと結合する

Question

POMDPのためにopen source libraryをやっています。これはフードの下でDynamic Programmingを使用して、あるコスト関数で他の2D空間を検索します。

DPインプリメンテーションmasterブランチは、Haskellのレイジー評価を使用するDPメモ化の場合はMemoTrieに基づいています。そして私は調整可能であるために費用関数を持つ必要があります。 MemoTrieの怠惰なアプローチではこれがうまくいきません。私は純粋なtryをしましたが、期待どおり、秒の代わりにすべてのテストを完了するのに数時間かかります。

私はMonad.Memoでモナドのアプローチを決めました。 Here is Readerのコンテキストを使用しないで動作します。しかし、今私は、この計算のためのReaderのコンテキストを導入するための適切な方法で苦労しています。

このtry私はMonadReaderを導入するために制約を使用しました。同時に、私は制約としてfqとfvの相互再帰を記述することができず、fqだけをメモしようとしました。しかしMonadMemoのMonadReader型クラス実装でさえ、Readerコンテキストをキーの一部として配置し、コンテキストは関数であるため、マッピングのキーの一部になることはほとんどありません。私はライターのモナドだけを包み込むことができました：

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

さらに、リーダーをアンラップすることもできませんでした。

最後に試してみましたuse ReaderTです。しかし、だから私はHaskellの中に生産的に苦労していますが、私はそれをこのような質問を学んでいるよう

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

ようなものを与えてこれはないコンパイルは私に長い時間がかかります。あなたからのアドバイスを聞いてうれしいですね。

Answer 1

ReaderTを使用しているバージョンでは、Dynamicのモナドには、さらに1つのレイヤーがMemoQVになります。

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

前に、我々は今、 "上部" 対照的に0 から開始からカウントトランス、Dynamicを番号

L1 (L2 Identity) 
-- 0 1 

ように見えたタイプ：を有する擬似Haskellで

、外見は

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

です上部に変圧器Rを置くと、キャッシュ変圧器はより深くシフトした。

これはmemol0、memol1とmemol2コンビネータに重要：memolNは（したがって、マッチングのタイプを持つことが期待されている）N番目の層を使用して計算をmemoizesので、あなたは、これらの層が移動したときにそれに応じてコードを更新する必要があります。

memol1 hereとmemol0 hereを使用します。 memol2とmemol1にそれぞれシフトすると、ファイルがコンパイルされます。