Verallgemeinern eines monadischen Ausdrucks über eine Liste von Elementen

Question

Ich habe eine monadische Funktion, die dabei hilft, Werte vom Typ Expr in Terms zu übersetzen. Die Signatur ist

fromDM :: (Name -> CompilerM Term) -> Expr -> CompilerM Term

Ich habe Probleme in einem Fall im Allgemeinen zu behandeln. Ich kann Implementierungen für jede individuelle Lösung aufschreiben

import Control.Monad.State 

type CompilerM = State Incr 

newtype Incr = Incr Int deriving (Show) 

generateNameM :: CompilerM Name 
generateNameM = state $ \i -> 
    let Incr y = i 
     j  = (+1) y 
    in (Name j, Incr j) 

data Expr = Tuple [Expr] 
data Name = Name Int 
data Term = Let Name [Name] Term 

fromDM :: (Name -> CompilerM Term) -> Expr -> CompilerM Term 
fromDM k expr = case expr of 
    Tuple [e1, e2]   -> do 
    x <- generateNameM 
    t' <- k x 
    fromDM (\z1 -> fromDM (\z2 -> pure $ Let x [z1, z2] t') e2) e1 

    Tuple [e1, e2, e3]  -> do 
    x <- generateNameM 
    t' <- k x 
    fromDM (\z1 -> fromDM (\z2 -> fromDM (\z3 -> pure $ Let x [z1, z2, z3] t') e3) e2) e1 

    Tuple [e1, e2, e3, e4] -> do 
    x <- generateNameM 
    t' <- k x 
    fromDM (\z1 -> fromDM (\z2 -> fromDM (\z3 -> fromDM (\z4 -> return $ Let x [z1, z2, z3, z4] t') e4) e3) e2) e1 

Jetzt möchte ich dies mit einer allgemeinen Regel ersetzen, das heißt Tuple es. Ich denke, dass dies entweder mit foldlM oder foldrM möglich sein sollte. Aber ich bleibe irgendwie dabei, wie ich das mache. Also, wie schreibe ich eine allgemeine Regel für diese Transformation, die auf einer beliebigen Liste von Ausdrücken funktioniert?

Answer 1

Okay, ich weiß nicht viel über Cont, also lassen Sie mich meinen Gedankengang skizzieren, als ich diese Frage ansprach. Das erste, was ich tun wollte, war nur die Bit-Code zu ziehen, die auf den Inhalt des Tuple abhängen, also:

fromDM k expr = case expr of 
    Tuple es -> do 
     x <- generateNameM 
     t' <- k x 
     letExprs x t' es 

letExprs x t' [e1, e2] = fromDM (\z1 -> fromDM (\z2 -> pure $ Let x [z1, z2] t') e2) e1 
-- etc. 

Wir abstrahieren letExprs möchten, so dass sie auf den Listen von beliebiger Länge arbeiten können . Jetzt, wo wir das Problem aufgeschrieben haben, ist der nächste Schritt im Feynman-Protokoll, sehr hart zu denken. Also starrte ich sehr hart auf die verschiedenen Fälle. Es sah für mich so aus, als ob jede Zelle in der Liste zu einem Anruf in fromDM wurde; und im Basisfall wurde Let auf eine variierende Liste angewendet. Wir können die wechselnde Liste in einem Akkumulator wie folgt kleben:

fromDM k expr = case expr of 
    Tuple es -> do 
     x <- generateNameM 
     t' <- k x 
     letExprs x t' [] es 

letExprs x t' vars [] = pure $ Let x (reverse vars) t' 
letExprs x t' vars (e:es) = fromDM (\z -> letExprs x t' (z:vars) es) e 

Das sieht schon ziemlich gut für mich aus. Wenn Sie es in eine Falte verwandeln wollen (was aus den üblichen Gründen angenehm ist: Sie können das Rekursionsmuster nicht versehentlich vermasseln, und die Leser wissen, dass Sie nichts Schwieriges tun), können wir es jetzt fast direkt ablesen:

fromDM k expr = case expr of 
    Tuple es -> do 
     x <- generateNameM 
     t' <- k x 
     foldr (\e k vars -> fromDM (\z -> k (z:vars)) e) 
       (\vars -> pure $ Let x (reverse vars) t') 
       es