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

如果我正确理解你的问题，你可以向函数添加一个额外的参数free-index，如下所示:

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 monad，你可以这样设计:

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