_Fun.scala

final class Compose1[T1, R] private (val fs: Vector[(Any => Any, Int)]) extends (T1 => R) {

  val MAX_DEPTH = 1000

  private def append(gs: Vector[(Any => Any, Int)], fd: (Any => Any, Int)) = {
    val (fl, dl) = gs.last
    val (f, d) = fd
    if(d + dl > MAX_DEPTH) {
      fd +: gs
    } else {
      val nf = (a: Any) => f(fl(a))
      gs.init :+ ((nf, d + dl))
    }
  }

  private def prepend(fd: (Any => Any, Int), gs: Vector[(Any => Any, Int)]) = {
    val (fl, dl) = gs.head
    val (f, d) = fd
    if(d + dl > MAX_DEPTH) {
      gs :+ fd
    } else {
      val nf = (a: Any) => fl(f(a))
      ((nf, d + dl)) +: gs.init
    }
  }

  private def concat(hs: Vector[(Any => Any, Int)], ts: Vector[(Any => Any, Int)]) =
    hs.init ++ prepend(hs.last, ts)

  @inline private def build = (i0: T1) => {
    var i = i0.asInstanceOf[Any]
    var j = fs.length - 1
    while(j >= 0) {
      val (f, _) = fs(j)
      i = f(i)
      j -= 1
    }
    i.asInstanceOf[R]
  }

  override def compose[A](g: A => T1): A => R =
    g match {
      case Compose1(gfs) =>
        new Compose1(concat(gfs, fs))
      case _ =>
        val fd = (g.asInstanceOf[Any => Any], 1)
        new Compose1(prepend(fd, fs))
    }

  override def andThen[A](g: R => A): T1 => A =
    g match {
      case Compose1(gfs) =>
        new Compose1(concat(fs, gfs))
      case _ =>
        val fd = (g.asInstanceOf[Any => Any], 1)
        new Compose1(append(fs, fd))
    }

  def apply(a: T1): R = build(a)
}

object Compose1 {
  def apply[T1, R](f0: T1 => R): T1 => R =
    f0 match {
      case Compose1(_) => f0
      case f => new Compose1(Vector((f.asInstanceOf[Any => Any], 1)))
    }

  def unapply[T1, R](c: Compose1[T1, R]) =
    Option(c.fs)
}

demo.scala

@ val f0 = (1 to 100000).foldLeft(identity[Int] _){ (f, _) =>  f.andThen(_ + 1) }
f0: Int => Int = <function1>
@ f0(0)
// $'[31mjava.lang.StackOverflowError
// scala.Function1$$anonfun$andThen$1.apply(Function1.scala:52)
// scala.Function1$$anonfun$andThen$1.apply(Function1.scala:52)
// scala.Function1$$anonfun$andThen$1.apply(Function1.scala:52)
// scala.Function1$$anonfun$andThen$1.apply(Function1.scala:52)
// scala.Function1$$anonfun$andThen$1.apply(Function1.scala:52)
// scala.Function1$$anonfun$andThen$1.apply(Function1.scala:52)
   
@ val f1 = (1 to 100000).foldLeft(Compose1(identity[Int])){ (f, _) =>  f.andThen(_ + 1) }
f1: Int => Int = <function1>
@ f1(0)
res4: Int = 100000
   
@ val f2 = (1 to 10000000).foldLeft(Compose1(identity[Int])){ (f, _) =>  f.andThen(_ + 1) }
f2: Int => Int = <function1>
@ f2(0)
res6: Int = 10000000

@ val f3 = (1 to 10000000).foldLeft(Compose1(identity[Int])){ (f, _) =>  f.compose(_ + 1) }
f3: Int => Int = <function1>
@ f3(0)
res8: Int = 10000000

@ Compose1(toS).andThen(yolo)(3)
res11: String = "3 yolo"
                           
@ Compose1(yolo).compose(toS)(3)
res12: String = "3 yolo"