Simple DFA using the State Monad
Use traverse instead of foldM + accumulate

In a fold, you usually use a function that reduces (or folds) your input into a single result. You, on the other hand, use fold mapEmissions to create a list from an input list. Both lists will have the same number of elements. That's not a fold. That's a map.

So first of all, let's use traverse instead of foldM:

evaluate :: [Input] -&gt; Output
evaluate inputs = evalState (traverse emit inputs) (False, True)


Next, let's figure out how emit should look like:

emit :: Input -&gt; State (Negated, Enabled) Emission
emit input = do
    (negated, enabled) &lt;- get
    let (negated', enabled', emission) = step (negated, enabled, input)
    put (negated', enabled')
    return emission


Almost the same as mapEmission, and we can use emit to implement mapEmission:

mapEmission accum input = (accum ++) &lt;$&gt; emit input


Therefore, we should really replace the foldM by traverse.

Consider already existing interfaces

step can be rewritten with another interface that fits the state interface:

type MMState = (Negated, Enabled) --  Mealy Machine State

step :: Input -&gt; MMState -&gt; (MMState, Emission)
step ToggleNegate  (n, e)     = ((not n, e    ), 0)
step ToggleEnabled (n, e)     = ((    n, not e), 0)
step _             (n, False) = ((n,     False), 0)
step Plus          (n, e)     = ((n,     e    ), if n then -1 else  1)
step Minus         (n, e)     = ((n,     e    ), if n then  1 else -1)


This makes emit even easier:

emit :: Input -&gt; State MMState Emission
emit input = state (step input)


Note that MMState makes it easier to change the other types, as there is less repetition.

It's completely up to you to write step like this, though.

Encapsulate possible errors in the type (if possible)

In toInput consider Maybe Input or Either String Input instead of error:

toInput :: Char -&gt; Either String Input
toInput '+' = pure Plus
toInput '-' = pure Minus
toInput 'n' = pure ToggleNegate
toInput 'e' = pure ToggleEnabled
toInput  c  = Left $ "Unrecognised character: " ++ [c]


Use Int instead of Integer if the values are small

Instead of Integer we should use Int as Emission. Integer can be arbitrarily large, but your output values are either -1, 0 or 1. Int is much more suitable for that.

Other comments

Other than that, well done. You followed good practice by including type signatures, and your code is easy to read and to follow. The only real hurdle was foldM instead of traverse.

However, your single instruction type is called Input, whereas your complete output type is called Output. That naming is somewhat unbalanced.



Overall, we end up with:

import Control.Monad.Trans.State.Lazy

data Input = Plus | Minus | ToggleNegate | ToggleEnabled
type Emission = Int
type Output = [Emission]
type Negated = Bool
type Enabled = Bool
type MMState = (Negated, Enabled) --  Mealy Machine State

toInput :: Char -&gt; Either String Input
toInput '+' = pure Plus
toInput '-' = pure Minus
toInput 'n' = pure ToggleNegate
toInput 'e' = pure ToggleEnabled
toInput  c  = Left $ "Unrecognised character: " ++ [c]

step :: Input -&gt; MMState -&gt; (MMState, Emission)
step ToggleNegate  (n, e)     = ((not n, e),     0)
step ToggleEnabled (n, e)     = ((    n, not e), 0)
step _             (n, False) = ((n,     False), 0)
step Plus          (n, e)     = ((n,     e),     if n then -1 else  1)
step Minus         (n, e)     = ((n,     e),     if n then  1 else -1)

emit :: Input -&gt; State MMState Emission
emit input = state (step input)

evaluate :: [Input] -&gt; Output
evaluate inputs = evalState (traverse emit inputs) (False, True)


By the way, we can now use emit on any traversable, so we could relax evaluate's type to

evaluate :: Traversable t =&gt; t Input -&gt; t Emission
evaluate inputs = evalState (traverse emit inputs) (False, True)


But that's up to you.