An idea for an stack safe products with scala.

tailrecA.scala

object TailRecA {

  trait Applicative[F[_]] {
    def pure[A](a: A): F[A]
    def ap[A, B](a: F[A])(fn: F[A => B]): F[B]
    def product[A, B](fa: F[A], fb: F[B]): F[(A, B)] =
      ap(fa)(map(fb) { b =>
        { a: A => (a, b) }
      })

    def map[A, B](a: F[A])(fn: A => B): F[B] = ap(a)(pure(fn))
    def tailRecA[A, B, C](c: C, b: F[B], cons: ((A, B)) => B)(fn: C => (F[A], Option[C])): F[B] =
      fn(c) match {
        case (fa, None) => map(product[A, B](fa, b))(cons)
        case (fa, Some(c)) =>
          val newB = map(product[A, B](fa, b))(cons)
          tailRecA(c, newB, cons)(fn)
      }
  }
  trait Monad[F[_]] extends Applicative[F] {
    def flatMap[A, B](a: F[A])(fn: A => F[B]): F[B]

    def tailRecM[A, B](a: A)(fn: A => F[Either[A, B]]): F[B] =
      flatMap(fn(a)) {
        case Right(b) => pure(b)
        case Left(a) => tailRecM(a)(fn)
      }
  }

  def traverse[A, B, F[_]](ls: List[A])(fn: A => F[B])(implicit F: Applicative[F]): F[List[B]] = {
    def next(l: List[A]): (F[Option[B]], Option[List[A]]) = l match {
      case Nil => (F.pure(None), None)
      case h :: tail => (F.map(fn(h))(Some[B](_)), Some(tail))
    }
    val cons: ((Option[B], List[B])) => List[B] = {
      case (None, l) => l
      case (Some(b), l) => b :: l
    }
    F.map(F.tailRecA(ls, F.pure(List.empty[B]), cons)(next))(_.reverse)
  }

  def traverseM[A, B, F[_]](ls: List[A])(fn: A => F[B])(implicit F: Monad[F]): F[List[B]] = {
    def step(rest: (List[A], List[B])): F[Either[(List[A], List[B]), List[B]]] = rest match {
      case (Nil, bs) => F.pure(Right(bs))
      case (a :: as, bs) =>
        F.map(fn(a)) { b =>
          Left((as, b :: bs))
        }
    }
    val reversed = F.tailRecM((ls, List.empty[B]))(step)
    F.map(reversed)(_.reverse)
  }

  implicit val optionMonad: Monad[Option] = new Monad[Option] {
    def pure[A](a: A): Option[A] = Option(a)
    def flatMap[A, B](a: Option[A])(fn: A => Option[B]): Option[B] = a match {
      case None => None
      case Some(a) => fn(a)
    }
    def ap[A, B](a: Option[A])(fn: Option[A => B]): Option[B] = (a, fn) match {
      case (Some(a), Some(f)) => Some(f(a))
      case _ => None
    }
    @annotation.tailrec
    override def tailRecM[A, B](a: A)(fn: A => Option[Either[A, B]]): Option[B] =
      fn(a) match {
        case None => None
        case Some(Left(a)) => tailRecM(a)(fn)
        case Some(Right(b)) => Some(b)
      }
    @annotation.tailrec
    override def tailRecA[A, B, C](c: C, bb: Option[B], cons: ((A, B)) => B)(fn: C => (Option[A], Option[C])): Option[B] =
      bb match {
        case None => None
        case Some(b) =>
          fn(c) match {
            case (Some(a), Some(nextC)) => tailRecA(nextC, Some(cons((a, b))), cons)(fn)
            case (Some(a), None) => Some(cons((a, b)))
            case (None, _) => None
          }
      }
  }

  case class ReaderT[M[_], R, T](run: R => M[T])

  def readerTUnsafe[M[_], R](implicit m: Monad[M]): Monad[({type Rdr[T] = ReaderT[M, R, T]})#Rdr] = {
    type Rdr[T] = ReaderT[M, R, T]

    new Monad[Rdr] {
      def pure[A](a: A): Rdr[A] = ReaderT[M, R, A]{ _ => m.pure(a) }
      def flatMap[A, B](a: Rdr[A])(fn: A => Rdr[B]): Rdr[B] = ReaderT[M, R, B]({ r =>
        m.flatMap(a.run(r)) { aa => fn(aa).run(r) }
      })
      def ap[A, B](a: Rdr[A])(fn: Rdr[A => B]): Rdr[B] = ReaderT[M, R, B]({ r =>
        m.ap(a.run(r))(fn.run(r))
      })
    }
  }
  implicit def readerT[M[_], R](implicit m: Monad[M]): Monad[({type Rdr[T] = ReaderT[M, R, T]})#Rdr] = {
    type Rdr[T] = ReaderT[M, R, T]

    new Monad[Rdr] {
      def pure[A](a: A): Rdr[A] = ReaderT[M, R, A]{ _ => m.pure(a) }
      def flatMap[A, B](a: Rdr[A])(fn: A => Rdr[B]): Rdr[B] = ReaderT[M, R, B]({ r =>
        m.flatMap(a.run(r)) { aa => fn(aa).run(r) }
      })
      def ap[A, B](a: Rdr[A])(fn: Rdr[A => B]): Rdr[B] = ReaderT[M, R, B]({ r =>
        m.ap(a.run(r))(fn.run(r))
      })
      override def tailRecM[A, B](a: A)(fn: A => Rdr[Either[A, B]]): Rdr[B] = ReaderT[M, R, B]({ r=>
        def step(a: A): M[Either[A, B]] = fn(a).run(r)

        m.tailRecM(a)(step)
      })
      override def tailRecA[A, B, C](c: C, bb: Rdr[B], cons: ((A, B)) => B)(fn: C => (Rdr[A], Option[C])): Rdr[B] =
        ReaderT[M, R, B]({ r =>
          m.tailRecA(c, bb.run(r), cons)(fn.andThen { case (ra, oc) => (ra.run(r), oc) })
        })
    }
  }

  type ROptionInt[T] = ReaderT[Option, Int, T]
  def safe(): Unit = {
    val list = (1 to 500000).toList
    val r = traverse[Int, Int, ROptionInt](list) { i => ReaderT[Option, Int, Int]({ r => if (i > r) Some(i) else None }) }
    println(r.run(0))
    assert(r.run(0) == Some(list))
  }
  def unsafe(): Unit = {
    val list = (1 to 500000).toList
    val r = traverse[Int, Int, ROptionInt](list) { i => ReaderT[Option, Int, Int]({ r => if (i > r) Some(i) else None }) }(readerTUnsafe[Option, Int])
    assert(r.run(0) == Some(list))
  }
}