Элементы маркировки Haskell в рекурсивной функции

Question

Я совершенно новый для Haskell и функционального программирования в целом, поэтому извините меня, если вопрос кажется простым или глупым.

У меня есть парсер для простого языка, который создает абстрактное синтаксическое дерево. Чтобы сгладить AST (поверните while и if statements в прыжки), мне нужно поместить метки в дерево. Проблема в том, что я не знаю, каким должен быть следующий ярлык (я все еще думаю императивно, потому что, если бы у меня было состояние, ничто из этого не было бы проблемой).

Функция, которую я до сих пор является следующее:

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) 

В своем нынешнем состоянии, функция «сглаживает» АСТ, но не пытается ставить правильные метки (он использует ту же строку для каждой конструкции).

В основном проблема заключается в том, что в случае последовательного оператора (и каждая программа является последовательным утверждением) я не могу придумать способ передать следующее значение, которое должно использоваться в метках.

Заранее спасибо.

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 

Но если вы знаете State монаду, вы можете создать так:

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