Haskell, die Elemente in rekursiver Funktion beschriftet

Question

Ich bin ziemlich neu zu Haskell und funktionale Programmierung im Allgemeinen, also entschuldigen Sie mich, wenn die Frage aufrichtig oder dumm scheint.

Ich habe einen Parser für eine einfache Sprache, die einen abstrakten Syntaxbaum erzeugt. Um den AST zu reduzieren (drehen Sie while und if-Anweisungen in Sprünge) muss ich Etiketten in den Baum setzen. Das Problem ist, dass ich nicht weiß, was das nächste Etikett sein soll (ich denke immer noch zwingend, denn wenn ich einen Zustand hätte, wäre das alles kein Problem).

Die Funktion, die ich bisher habe, ist der folgenden:

transform :: Stmt -> FStmt 
transform (Seq stmt) = FSeq (map transform stmt) 
transform (Assign var val) = FAssign var val 
transform (While cond stmt) = FWhile "label1" (Jumpf cond "label2") (transform stmt) (Jump "label1") "label2" 
transform (If cond stmt1 stmt2) = FIf (Jumpf cond "label") (transform stmt1) "label" (transform stmt2) 

In seinem aktuellen Zustand, die Funktion des AST „verflacht“, aber nicht versuchen, die richtigen Etiketten zu setzen (es die gleiche Zeichenfolge verwendet für jedes Konstrukt).

Grundsätzlich ist das Problem, dass im Falle einer sequentiellen Anweisung (und jedes Programm ist eine sequenzielle Anweisung) Ich kann nicht eine Möglichkeit, den nächsten Wert übergeben, der in den Etiketten verwendet werden sollte.

Vielen Dank im Voraus.

Answer 1

Wenn ich das richtig das Problem zu verstehen, können Sie auf die Funktion einen zusätzlichen Parameter frei Index wie folgt hinzu:

transform :: Stmt -> FStmt 
transform = snd . transform' 0 

transform' :: Int -> Stmt -> (Int, FStmt) 
transform' freeIdx (Seq stmt) = (freeIdx', FSeq stmt') 
    where 
    (freeIdx', stmt') = mapAccumL transform' freeIdx stmt 
transform' freeIdx (Assign var val) = (freeIdx, FAssign var val) 
transform' freeIdx (While cond stmt) = 
    (freeIdx', FWhile label1 (Jumpf cond label2) stmt' (Jump label1) label2) 
    where 
    label1 = "label" ++ show freeIdx 
    label2 = "label" ++ show (freeIdx + 1) 
    (freeIdx', stmt') = transform' (freeIdx + 2) stmt 
transform' freeIdx (If cond stmt1 stmt2) = 
    (freeIdx'', FIf (Jumpf cond label) stmt1' label stmt2') 
    where 
    label = "label" ++ show freeIdx 
    (freeIdx', stmt1') = transform' (freeIdx + 1) stmt1 
    (freeIdx'', stmt2') = transform' freeIdx' stmt2 

Aber wenn man Staat Monade bekannt ist, können Sie dieses Design:

transform :: Stmt -> FStmt 
transform = flip evalState 0 . transform' 

transform' :: Stmt -> State Int FStmt 
transform' (Seq stmt) = FSeq <$> mapM transform stmt 
transform' (Assign var val) = return $ FAssign var val 
transform' (While cond stmt) = do 
    label1 <- freeLabel 
    label2 <- freeLabel 
    stmt' <- transform' stmt 
    return $ FWhile label1 (Jumpf cond label2) stmt' (Jump label1) label2 
transform' (If cond stmt1 stmt2) = do 
    label <- freeLabel 
    stmt1' <- transform' stmt1 
    stmt2' <- transform' stmt2 
    return $ FIf (Jumpf cond label) stmt1' label stmt2' 

freeLabel :: State Int String 
freeLabel = do 
    i <- get 
    put $ i + 1 
    return $ "label" ++ show i