Combine state with IO actions

Use liftIO

You’re already very close! Your suggestion

newtype Op a = Op {runOp :: ST -> IO (ST, a)}

is excellent and the way to go.

To be able to execute getLine in an Op context, you need to ‘lift’ the IO operation into the Op monad. You can do this by writing a function liftIO:

liftIO :: IO a -> Op a
liftIO io = Op $ \st -> do
  x <- io
  return (st, x)

You can now write:

runOp (do x <- liftIO getLine; ...

Use class MonadIO

Now the pattern of lifting an IO action into a custom monad is so common that there is a standard type class for it:

import Control.Monad.Trans

class Monad m => MonadIO m where
  liftIO :: IO a -> m a

So that your version of liftIO becomes an instance of MonadIO instead:

instance MonadIO Op where
  liftIO = ...

Use StateT

You’ve currently written your own version of the state monad, specialised to state ST. Why don’t you use the standard state monad? It saves you from having to write your own Monad instance, which is always the same for the state monad.

type Op = StateT ST IO

StateT already has a Monad instance and a MonadIO instance, so you can use those immediately.

Monad transformers

StateT is a so-called monad transformer. You only want IO actions in your Op monad, so I’ve already specialized it with the IO monad for you (see the definition of type Op). But monad transformers allow you to stack arbitrary monads. This what intoverflow is talking about. You can read more about them here and here.