Haskell 中的无序列表迭代

Question

我正在 Haskell 中实现（玩具）堆叠机。我定义了一个阶跃函数 step :: State -> Instruction -> State，它将给定指令的结果应用到给定状态，returns 应用到机器的结果状态。显然，我想要一个函数 run :: State -> Program -> State（其中 Program :: [Instruction]），它实质上会根据需要多次调用 step 以执行给定的输入程序。

我最初的天真解决方案是 foldl，像这样：

run :: State -> Program -> State
run st prog = foldl (step) st prog

显然，这不支持跳转，这会修改我需要在列表中的位置。这个实现所做的就是从左到右遍历程序。对于其他上下文，程序的状态 State 如下：

data State = State {
    pc :: Word,
    reg :: Word,
    stack :: [Word],
    memory :: [Word]
}
    deriving (Show, Eq)

说明如下：

data Opcode = Add | Sub | Mul | Div | Mod | Jump | Push | Pop | Load | Store | Set | Call | Ret | Pos | Dup | Swap | Halt | Nop
    deriving (Enum, Show, Eq)

data Instruction = Instruction {
    opcode :: Opcode,
    arg :: Maybe Word
}
    deriving (Show, Eq)

如何以任意顺序（当然可能永远）遍历列表，以便我可以支持跳转？

Answer 1

我想您的 step 函数需要报告是否到了停止时间。例如，假设您将其类型修改为 step :: State -> Instruction -> Maybe State。然后你可以通过发送给它来实现 run:

run :: State -> Program -> State
run state prog = case step state (prog !! fromIntegral (pc state)) of
    Nothing -> state
    Just state' -> run state' prog

（您可以通过让您的 pc 具有类型 Int 而不是 Word 来避免 fromIntegral。）

请注意，(!!) 是 O(2ⁿ)^*（在评论中打我 ;-)。您应该考虑从 [Instruction] 切换到 Array Word Instruction 以便您可以使用 (!) 代替，即 O(n).

^* 好吧，准确地说，(!!) 在技术上是 O(1) 因为 Int 有一个固定的大小——但是，哦，那个常数因子！因此，假设 (!!) 到 Integer 的合适泛化是 O(2ⁿ)。类似的狡辩适用于 (!).

Answer 2

使用数组可能是一个不错的方法，但还有一种方法可以通过完全取消程序计数器来单步执行程序，这有点像折叠。

程序计数器只是指向程序中您接下来要运行的指令的指针。因此，我们可以直接将运行 next 指令放入状态，而不是使用程序计数器。考虑 State:

的替代实现

data State = State
  { reg     :: Word
  , stack   :: [Word]
  , memory  :: [Word]
  , program :: Program
  } deriving (Show, Eq)

现在我们必须重新考虑step。特别是，每次我们 step 时，我们并不是在增加（或任意修改）pc，而是将程序更改为运行。此外，我们不需要将指令作为参数，因为 State 已经知道运行是什么。因此，我们有类似的东西：

step :: State -> State
step st = case program st of
  []          -> st
  HALT : _    -> st {program = []}
  ADD  : rest -> st {program = rest, ...} -- Do whatever you do for add too
  ...

但是，我们为 JUMP 做了什么？当程序消失在我们身上时，我们如何才能跳转到程序中的任意位置运行呢？一种选择是另外跟踪原始程序。我们可以把它作为另一个字段放在 State 中，但为了多样性，我将把它作为附加参数传递给 step，如：

step :: Program -> State -> State
step originalProgram st = case program st of
  []         -> st
  HALT : _   -> st {program = []}
  JUMP n : _ -> st {program = drop n originalProgram}
  ...

（请注意，这里我假设你的 JUMP 是绝对的而不是相对的。如果你有相对跳转，那么你需要跟踪“已经executed" 程序的一部分，可能是倒序的指令列表。也就是说，每次执行一条指令时，都会将其从 program 列表中弹出，然后将其推入 executed 列表中. 当你点击一个向后 n 指令的 JUMP 时，你只会从已执行的指令中弹出 n 并将它们推回到程序列表中。）

现在剩下的就是运行整个程序：

run :: State -> Program -> State
run startState originalProgram = go (startState {program = originalProgram})
  where
    go st = case program st of
      [] -> st
      _  -> go $ step originalProgram st

就性能而言，这肯定比使用数组差；大多数步骤会很快，但 JUMPS 可能需要更长的时间。另一方面，你可以用这种方式运行无限长的程序，而且你不必担心索引越界。

Haskell 中的无序列表迭代

Out-of-order list iteration in Haskell

list

haskell

functional-programming

iteration

fold