I hadn't realized (maybe the original paper mentioned) but tailRecM + map is enough to do flatMap (and of course logically flatMap + pure are enough to do tailRecM).

flatMapFromTailRec.scala

object Monad {
  trait Monad[F[_]] {
    def pure[A](a: A): F[A]

    /**
     * We can have a default implementation in terms of tailRecM
     * and map
     */
    def flatMap[A, B](fa: F[A])(fn: A => F[B]): F[B] = {
      def step(first: Option[A]): F[Either[Option[A], B]] =
        first match {
          case None => map(fa) {  a => Left(Some(a)) }
          case Some(a) => map(fn(a))(Right(_))
        }

      tailRecM(Option.empty[A])(step(_))
    }

    def map[A, B](a: F[A])(fn: A => B): F[B] =
      flatMap(a)(fn.andThen(pure(_)))

    /**
     * This is logically correct, but not stack safe unless
     * F[_] is trampolined
     */
    def tailRecM[A, B](a: A)(fn: A => F[Either[A, B]]): F[B] =
      flatMap(fn(a)) {
        case Left(a) => tailRecM(a)(fn)
        case Right(b) => pure(b)
      }
  }
}