Haskell在遞歸函數中標記項目

Question

對於Haskell和函數式編程，我一般都很新，所以如果問題看起來很簡單或很愚蠢，請原諒。

我有一個解析器，用於生成抽象語法樹的簡單語言。爲了扁平化AST（將while和if語句變成跳轉），我需要在樹中放置標籤。問題是，我不知道下一個標籤應該是什麼（我仍然認爲是必要的，因爲如果我有狀態，這些都不會成爲問題）。

是我到目前爲止的功能如下：

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) 

在當前狀態下，該功能「變平」的AST，但並不試圖把正確的標籤（它使用相同的字符串爲每個構造）。

基本上問題是，在順序語句（並且每個程序都是順序語句）的情況下，我無法想到一種方法來傳遞應該在標籤中使用的下一個值。

預先感謝您。

Answer 1

如果我理解正確的話您的問題，您可以添加到功能的額外的參數自由指數這樣的：

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 

但是，如果你知道國家單子，你可以設計這樣的：

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