@Potato44: \f xs -> sequence $ map f xs is the same as mapM and equivalently with sequence_ and mapM_. So you could just use interpret' = mapM_ step ;)
And do you really dislike syntactic sugar or is there another reason you use StateT $ \tape -> return ((), f tape) over modify f?
Apart from the Control.Monad.State implementation itself I don't think I've ever seen this notation being used.