haskell - 在 Haskell 中编写汇编程序 - 带状态的 mapM？

Question

我在 Haskell 中编写了一个非常简单的两遍汇编程序，我遇到了一个我还没有经验来解决的场景。我认为解决方案很可能涉及单子(monad)变压器，我不太了解。

汇编器将汇编代码解析为 Statement 的列表。 s，它们是指令或标签。一些 Statement s 可以指标签。汇编器需要转换 Statement转入 Instruction s，这涉及消除标签并用适当的值替换标签引用。

我已经编写了汇编程序的第一遍，它产生了 [(String, Int)]表示从标签到地址的 map 。我还编写了以下函数来翻译 Statement进入 Instruction :

stmtToInstruction :: Int -> [(String, Int)] -> Statement -> Either String [I.Instruction]
stmtToInstruction addr labels stmt = case stmt of
    ADD d s1 s2     -> Right [I.ADD d s1 s2]
    BEQL s1 s2 l    -> case do label <- find (\e -> fst e == l) labels
                               let labelAddr = snd label
                               let relativeAddr = I.ImmS $ fromIntegral (labelAddr - addr)
                               return (I.BEQ s1 s2 relativeAddr) of
                        Just i -> Right [i]
                        Nothing -> Left $ "Label " ++ l ++ " not defined"
    LABEL _         -> Right []

为简洁起见，我省略了几个案例，但您可以在此处查看所有可能的结果:

ADD总是成功并产生一条指令

BEQL可能成功或失败，取决于是否找到标签

LABEL总是成功，即使它没有产生实际的指令

这按预期工作。我现在遇到的问题是编写这个函数:

replaceLabels :: [Statement] -> Either String [I.Instruction]

replaceLabels获取语​​句列表，然后运行 ​​ stmtToInstruction在每一个上。 addr stmtToInstruction 的参数必须是 [Instruction] 的长度累积至今。输出可能是 Left String , 如果标签引用之一无效，或 Right [I.Instruction] ，如果没有错误。
mapM :: Monad m => (a -> m b) -> [a] -> m [b]为我们提供了一些方法，但无法将当前地址注入(inject) (a -> m b)功能。我该如何进行这项工作？

Answer 1

你是对的:StateT monad 转换器可以解决问题:

imapM :: (Traversable t, Monad m)
          => (Int -> a -> m b) -> t a -> m (t b)
imapM f = flip runStateT 0 .
  mapM (\a ->
    do
      count <- get
      put $! count + 1
      f count a)

但是为列表编写专门的版本可能会更好:

itraverse :: Applicative f
          => (Int -> a -> f b) -> [a] -> f [b]
itraverse f = go 0 where
  go !_ [] = pure []
  go !count (x:xs) = (:) <$> f count x <*> go (count + 1) xs