Trampolining the state monad via applicative combinator appears to work

trampolined-state.scala

import scalaz._, Scalaz._
 
def setS(i: Int): State[List[Int], Unit] = modify(i :: _)
 
val s = (1 to 10000).foldLeft(state[List[Int], Unit](()).lift[Free.Trampoline]) {
  case (st, i) => st *> setS(i).lift[Free.Trampoline]
}
 
s(Nil).run

// Purposely choosing not to traverse here for demonstration purposes
val s2 = (1 to 10000).foldLeft(state[List[Int], List[Unit]](List.empty).lift[Free.Trampoline]) {
  case (st, i) => (st |@| setS(i).lift[Free.Trampoline])((xs, x) => x :: xs)
}

s2(Nil).run

val s3 = (1 to 10000).toList.traverseU {
  i => setS(i).lift[Free.Trampoline]
}

s3(Nil).run

For some reason the applicative works