Type-aligned, stack-safe lists.

TLists.scala

import scala.annotation.tailrec

/**
 * A Type-aligned list is a list of functions which can be
 * chained together. They are "type-aligned" because their
 * types all line. For example, suppose you have the following
 * functions:
 *
 *   val foo: Int => String = i => i.toString
 *   val bar: String => Char = s => s.head
 *   val baz: Char => Byte = c => c.toByte
 *
 * You could imagine a big list chaining them together:
 *
 *   (Int => (String) => (Char) => Byte)
 *
 * A type-aligned list is a data-structure that does this. It's
 * type-safe in the sense that it won't let you add to this list
 * unless the types match up, and you're guaranteed that if you
 * were to traverse this list, the types will match up by construction.
 *
 * A type-aligned list is useful for stack-safe programming in scala,
 * though I have not seen them used in the wild. It could be that,
 * generally, when making data structures stack-safe, you need
 * slightly more complicated structures than what a simple type-aligned
 * list can provide (for example, to support stack-safe .flatMap
 * implementations). 
 *
 * :D
 *
 * PS - this will only compile on Scala v2.12.4. Otherwise, the @tailrec
 * annotations will fail.
 */

object TList {

  /**
   * Type-aligned, stack-safe list of functions which can be chained
   * together. For the "cons" variant, the "head" represents
   * the first function to apply.
   */
  sealed trait TConsList[-X,+Y] extends Function1[X,Y] {
    def apply(x: X): Y = this match {
      case TCFunc(f) => f(x)
      case TCons(f, tail) => TConsList.loop(f(x),tail)
    }

    override def compose[Z](g: Z => X): TConsList[Z,Y] = TCons(g, this)

    // O(n)
    override def andThen[Z](g: Y => Z): TSnocList[X,Z] = TSnoc(reverse(this), g)
  }
  final case class TCFunc[X,Y](f:X => Y) extends TConsList[X,Y]
  final case class TCons[X,Y,Z](head: X => Y, tail: TConsList[Y,Z]) extends TConsList[X,Z]
  object TConsList {
    @tailrec private def loop[A,B](curr: A, next: TConsList[A,B]): B = next match {
      case TCFunc(f) => f(curr)
      case TCons(f, tail) => loop(f(curr), tail)
    }
  }

  /**
   * Type-aligned, stack-safe list of functions which can be chained
   * together. For the "snoc" variant, the "head" represents
   * the last function to apply.
   */
  sealed trait TSnocList[-X,+Y] extends Function1[X,Y] {

    // O(2*n) owing to the reversal
    def apply(x: X): Y = reverse(this)(x)

    // O(n)
    override def compose[Z](g: Z => X): TConsList[Z,Y] = TCons(g, reverse(this))

    override def andThen[Z](g: Y => Z): TSnocList[X,Z] = TSnoc(this, g)
  }
  final case class TSFunc[X,Y](f: X => Y) extends TSnocList[X,Y]
  final case class TSnoc[X,Y,Z](init: TSnocList[X,Y], f: Y => Z) extends TSnocList[X,Z]

  @tailrec
  def reverse[A,B,C](list: TSnocList[A,B], acc: TConsList[B,C]): TConsList[A,C] = list match {
    case TSFunc(f) => TCons(f, acc)
    case TSnoc(init, f) => reverse(init, TCons(f, acc))
  }

  @tailrec
  def reverse[A,B,C](list: TConsList[B,C], acc: TSnocList[A,B]): TSnocList[A,C] = list match {
    case TCFunc(f) => TSnoc(acc, f)
    case TCons(f, tail) => reverse(tail, TSnoc(acc, f))
  }

  def reverse[A,B](list: TSnocList[A,B]): TConsList[A,B] = list match {
    case TSFunc(f) => TCFunc(f)
    case TSnoc(init, f) => reverse(init, TCFunc(f)) // uses stack-safe reverse
  }

  def reverse[A,B](list: TConsList[A,B]): TSnocList[A,B] = list match {
    case TCFunc(f) => TSFunc(f)
    case TCons(f, tail) => reverse(tail, TSFunc(f)) // uses stack-safe reverse
  }

  val foo: Int    => String = i => i.toString
  val bar: String => Char   = s => s.head
  val baz: Char   => Byte   = c => c.toByte

  val foos: TConsList[Int,Byte] = TCons(foo, TCons(bar, TCFunc(baz)))
  val bars: TSnocList[Int,Byte] = TSnoc(TSnoc(TSFunc(foo), bar), baz)
}

oops, I lied. .reverse as implemented is not stack-safe so not all these operations are stack safe. whoops.

Fixed! Now everything should be stack safe.

Most stack-safe code resorts to unsafe casting and pushing functions
onto the heap in the form of List[Any => Any].

Prior to Scala 2.12.4 (namely scala/scala#6065), that had to be done for performance reasons, because there was no tailcall elimination for calls with varying type arguments (such as your loop method).

@TomasMikula ah, I knew that and was wondering how my @tailrec calls were working in the first place! I guess it's time to clean up some cats code! :)