Kombinieren Monad.Memo mit Umgebung durch Reader in Haskell

Question

Ich mache open source library für POMDP. Es verwendet Dynamic Programming unter der Haube, um andere 2D-Raum mit einigen Kostenfunktion zu suchen.

DP-Implementierung in master Zweig basiert auf MemoTrie für DP Memorization, die Haskell Lazy Evaluation verwendet. Und ich muss Kostenfunktion haben, um abstimmbar zu sein. Ich glaube, das wird nicht gut mit MemoTries faulen Ansätzen funktionieren. Ich machte eine naive try, aber wie erwartet dauert es Stunden, um alle Tests statt Sekunden zu durchlaufen.

Ich entschied, monadischen Ansatz mit Monad.Memo ist ein Weg zu gehen. Here is ein erster Versuch, der zwar funktioniert, aber keinen Reader-Kontext verwendet. Aber jetzt habe ich Probleme damit, den Leserkontext für diese Berechnung einzuführen.

Diese try Ich verwendete Einschränkungen, um MonadReader einzuführen. Zur gleichen Zeit war ich nicht in der Lage, die gegenseitige Wiederholung für fq und fv als Einschränkung zu beschreiben, ich versuchte nur, fq zu beschreiben. Aber selbst dann, wenn die MonodReader-Klassenimplementierung von MonadMemo den Leserkontext als Teil des Schlüssels verwendet, und mein Kontext eine Funktion ist, könnte er kaum ein (Teil-) Schlüssel für das Mapping sein. Ich war nur in der Lage Zeug Writer Monade auszupacken up:

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

Und war nicht in der Lage, weiter zu gehen als auch den Reader auszupacken.

Letzter Versuch versuchte ich use ReaderT. Aber das ist nicht geben compiles Sachen wie

• 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 in Haskell produktiv sein Ich bin zu kämpfen, aber wie ich lerne es Fragen wie diese nehmen Sie mich lange Zeit. Würde mich freuen, irgendeinen Rat von Ihnen zu hören!

Answer 1

In der Version ReaderT hat Ihre Dynamic Monade eine weitere Schicht um MemoQV.

In pseudo-Haskell, mit:

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

Der Typ sah vor, wie

L1 (L2 Identity) 
-- 0 1 

wo wir die Transformatoren aus dem "top", ausgehend von 0. Im Gegensatz dazu Dynamic nun Zählen nummerierten sieht aus wie

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

Da Sie sich verlieben Nachdem die Transformatoren R an der Spitze waren, wurden die Cache-Transformatoren tiefer verschoben.

Dies ist wichtig, um memol0, memol1 und memol2 combinators: memolN memoizes eine Berechnung unter Verwendung der N ten Schicht (die somit eine passende Art zu erwarten ist), so dass Sie Ihren Code entsprechend aktualisieren müssen, wenn diese Schichten bewegen.

Sie verwenden memol1 here und memol0 here. Die Datei wird kompiliert, wenn Sie sie auf memol2 bzw. memol1 verschieben.