Haskell 在递归函数中标记项目 [英] Haskell labelling items in recursive function

问题描述

总的来说，我对 Haskell 和函数式编程很陌生，所以如果问题看起来很简单或很愚蠢，请原谅我.

I am quite new to Haskell and functional programming in general, so excuse me if the question seems straightforward or silly.

我有一个用于生成抽象语法树的简单语言的解析器.为了展平 AST(将 while 和 if 语句转换为跳转)，我需要在树中放置标签.问题是我不知道下一个标签应该是什么(我还在急切地思考，因为如果我有状态，这一切都不是问题).

I have a parser for a simple language that produces an abstract syntax tree. In order to flatten the AST (turn while and if statements into jumps) I need to put labels in the tree. The problem is that I do not know what the next label should be (I am still thinking imperatively, because if I had state, none of this would be a problem).

到目前为止，我拥有的功能如下:

The function that I have so far is the following:

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，但不会尝试放置正确的标签(它对每个构造使用相同的字符串).

In its current state, the function "flattens" the AST, but does not attempt to put the correct labels (it uses the same string for every construct).

基本上问题在于，在顺序语句的情况下(并且每个程序都是顺序语句)，我想不出一种方法来传递应该在标签中使用的下一个值.

Basically the problem is that in the case of a sequential statement (and every program is a sequential statement) I cannot think of a way to pass the next value that should be used in the labels.

提前致谢.

推荐答案

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

If I understand correctly your problem, you can add to the function an extra parameter free-index like this:

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

But if you known State monad, you can design like this:

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

这篇关于Haskell 在递归函数中标记项目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！