Depagination with loopM exploration [Scala]

depaginate.scala

import scala.concurrent.ExecutionContext.Implicits.global
import scala.concurrent.Future

object Depaginate extends App {

  trait Monad[F[_]] {
    def map[A, B](fa: F[A])(f: A => B): F[B]
    def pure[A](a: A): F[A]
    def flatMap[A, B](fa: F[A])(k: A => F[B]): F[B]
  }

  def loopM[A, B, M[_]](a: A)(fn: A => M[Either[A, B]])(implicit M: Monad[M]): M[B] =
    M.flatMap(fn(a)) {
      case Left(a) => loopM(a)(fn)
      case Right(b) => M.pure(b)
    }

  implicit val monadFuture: Monad[Future] = new Monad[Future] {
    override def map[A, B](fa: Future[A])(f: A => B): Future[B] = fa.map(f)
    override def pure[A](a: A): Future[A] = Future.successful(a)
    override def flatMap[A, B](fa: Future[A])(k: A => Future[B]): Future[B] = fa.flatMap(k)
  }

  case class Identity[A](runIdentity: A)

  implicit val monadIdentity: Monad[Identity] = new Monad[Identity] {
    override def map[A, B](fa: Identity[A])(f: A => B): Identity[B] = Identity(f(fa.runIdentity))
    override def pure[A](a: A): Identity[A] = Identity(a)
    override def flatMap[A, B](fa: Identity[A])(k: A => Identity[B]): Identity[B] = k(fa.runIdentity)
  }

  case class Pagination[K, R](nextPageKey: K, results: List[R])

  def depaginate[K, R, M[_]](fromPage: K)(getPage: K => M[Option[(K, R)]])(implicit M: Monad[M]): M[List[R]] =
    loopM(Pagination(fromPage, List[R]()))(key => M.map(getPage(key.nextPageKey)) {
      case None => Right(key.results.reverse)
      case Some((nextPage, result)) => Left(Pagination(nextPage, result :: key.results))
    })

  val pages = List(List(1, 2, 3), List(4, 5, 6), List(7, 8, 9))

  def getPage(page: Int): Future[Option[(Int, List[Int])]] =
    Future.successful(if (page >= pages.size) None else Some((page + 1, pages(page))))

  def getPageTest(page: Int): Identity[Option[(Int, List[Int])]] =
    Identity(if (page >= pages.size) None else Some((page + 1, pages(page))))

  val results = depaginate(0)(getPage)
  val resultsPure = depaginate(0)(getPageTest)
}