ST and State implemented in terms of each other.

ST-via-state.hs

import GHC.Exts (Any)
import Unsafe.Coerce (unsafeCoerce)

import Control.Monad.State
import Data.IntMap (IntMap)
import qualified Data.IntMap (IntMap)

-- Don't export /any/ of these constructors!

type role ST' nominal representative
newtype ST' s a = ST' (State STRefMap a)
  deriving newtype (Functor, Applicative, Monad)

type role STRef' nominal representative
newtype STRef' s a = STRef' Int

data STRefMap = STRefMap !Int (IntMap Any)

newSTRef' :: a -> ST' s (STRef' s a)
newSTRef' a = ST' $ do
  STRefMap next refs <- get
  let newRefs = IntMap.insert next (unsafeCoerce a)
  put (STRefMap (next+1) newRefs)
  pure (STRef' next)

readSTRef' :: STRef' s a -> ST' s a
readSTRef' (STRef' i) = ST' $ do
  STRefMap _ refs <- get
  pure (unsafeCoerce (refs IntMap.! i))

writeSTRef' :: STRef' s a -> a -> ST' s ()
writeSTRef' (STRef' i) a = ST' $ do
  STRefMap next refs <- get
  let newRefs = IntMap.insert i (unsafeCoerce a)
  put (STRef next newRefs)

state-via-ST.hs

import Control.Monad.ST
import Data.STRef

import Control.Monad.State.Class

newtype State' s a = State' { unState' :: forall x. STRef x s -> ST x a }

instance Functor (State' s) where
  fmap f (State' k) = State' (fmap f . k)

instance Applicative (State' s) where
  pure a = State' (const . pure a)
  (<*>) = ap

instance Monad (State' s) where
  State' k >>= f = State' $ \ref -> do
    a <- k ref
    unState' (f a) ref

instance MonadState s (State' s) where
  get = State' readSTRef
  put = State' writeSTRef

runState' :: State' s a -> s -> (s, a)
runState' (State' k) s = runST $ do
  ref <- newSTRef s
  a <- k ref
  s' <- readSTRef ref
  pure (s', a)