A different State encoding (solution here https://gist.github.com/YoEight/0541aa293effbfff8d02)

State.hs

{-# LANGUAGE RankNTypes #-}

newtype State s a = State { runState :: forall r. s -> (a -> s -> r) -> r }

stateReturn :: a -> State s a
stateReturn = undefined

stateMap :: (a -> b) -> State s a -> State s b
stateMap = undefined

stateBind :: (a -> State s b) -> State s a -> State s b
stateBind = undefined

stateGet :: State s s
stateGet = undefined

statePut :: s -> State s ()
statePut = undefined

stateModify  :: (s -> s) -> State s ()
stateModify = undefined

execState :: s -> State s a -> s
execState = undefined

evalState :: s -> State s a -> a
evalState = undefined

I ran this through Google Translate to convert it to Scala:

case class State[S,A](run: (S => (A => S => R) => R) forSome { type R }) {

  def map[B](f: A => B): State[S,B] = State.map(f)(this)

  def flatMap[B](f: A => State[S,B]): State[S,B] = State.bind(f)(this)

}

object State {

  def pure[S,A]: A => State[S,A] = ???

  def map[S,A,B]: (A => B) => State[S,A] => State[S,B] = ???

  def bind[S,A,B]: (A => State[S,B]) => State[S,A] => State[S,B] = ???

  def get[S]: State[S,S] = ???

  def put[S]: S => State[S,Unit] = ???

  def modify[S]: (S => S) => State[S,Unit] = ???

  def exec[S,A]: State[S,A] => S = ???

  def eval[S,A]: State[S,A] => A = ???

}

Types for execState and evalState are wrong: both need to take an initial seed, otherwise there is no possible non-bottom implementation!

Oops... It's fixed now. Thanks