Out-of-order list iteration in Haskell

Question

I'm implementing a (toy) stack machine in Haskell. I've defined a step function, step :: State -> Instruction -> State, which applies the result of a given instruction to a given state and returns the resultant state of the machine. Obviously, I'd like to have a function, run :: State -> Program -> State (where Program :: [Instruction]) that essentially calls step as many times as needed in order to execute the given input program.

My initial, naive solution was to foldl, like so:

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

Obviously, this can't support jumps, which would modify where abouts in the list I need to be. All this implementation does is iterate left-to-right through the program. For additional context, the program's state, State, is as follows:

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

and instructions are as follows:

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)

How do I iterate through the list in an arbitrary order (and potentially forever, of course) so that I can support jumps?

Answer 1

I guess your step function will need to report whether it's time to halt or not. For example, let's suppose you modify its type to step :: State -> Instruction -> Maybe State. Then you can implement run just by shipping out to it:

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

(You can avoid the fromIntegral by making your pc have type Int instead of Word.)

Note that (!!) is O(2ⁿ)^* (fight me in the comments ;-). You should consider switching from [Instruction] to Array Word Instruction so that you can use (!) instead, which is O(n).

^* Okay, to be precise, (!!) is technically O(1) because Int has a fixed size -- but, ohhhh, that constant factor! So let's say, a suitable generalization of (!!) to Integer is O(2ⁿ). Similar quibbles apply to (!).