Pretty cool! I was having trouble understanding the relationship between monoids and deterministic finite automata, but once I worked out an example by hand I was able to implement that transformation in Haskell:

    data MonoidMachine monoid input = Monoid monoid =>  MonoidMachine
      (input  -> monoid)
      (monoid -> Bool)

    -- From the proof of Theorem 1 in the paper.
    translate :: DFA state input -> MonoidMachine (Endo state) input
    translate (DFA _ _ delta initial accepting) = 
    MonoidMachine f g where
      f a = Endo (\q -> delta q a)
      g (Endo h) = h initial `member` accepting

    runMonoidMachine :: MonoidMachine monoid input -> [input] -> Bool
    runMonoidMachine (MonoidMachine f g) = g . mconcat . map f

The rest is here: https://gist.github.com/newjam/428613f083d289b83de0ddfeedf4e...