Free Alternative in Scala

FreeAlt.scala

// Attempted port from http://hackage.haskell.org/package/free-5.1.3/docs/Control-Alternative-Free.html
// Hopefully I did it right, but no guarantees
// DISCLAIMER: definitely not stack-safe in Scala
import cats.{Alternative, Applicative}
import cats.implicits._

sealed abstract class AltF[F[_], A] extends Serializable {
  import AltF._

  def map[B](f: A => B): AltF[F, B] = this match {
    case Pure(value) => Pure(f(value))
    case Ap(fi, fia) => Ap(fi, fia.map(_ andThen f))
  }
}

object AltF {
  final case class Pure[F[_], A](value: A) extends AltF[F, A]
  final case class Ap[F[_], I, A](fi: F[I], fia: Alt[F, I => A]) extends AltF[F, A] {
    type Init = I
  }

  implicit def altFApplicative[F[_]]: Applicative[AltF[F, ?]] = new Applicative[AltF[F, ?]] {
    override def map[A, B](fa: AltF[F, A])(f: A => B): AltF[F, B] = fa.map(f)

    def ap[A, B](ff: AltF[F, A => B])(fa: AltF[F, A]): AltF[F, B] =
      (ff, fa) match {
        case (Pure(ab), fa) => map(fa)(ab)
        case (ff, Pure(a)) => map(ff)(_.apply(a))
        case (x @ Ap(fi, altFi2a2b), altFa) =>
          val altA2i2b: Alt[F, A => x.Init => B] = altFi2a2b.map(f => a => i => f(i)(a))
          Ap[F, x.Init, B](fi, altA2i2b.ap(Alt(altFa :: Nil)))
      }

    def pure[A](x: A): AltF[F, A] = Pure[F, A](x)
  }
}

final case class Alt[F[_], A](alternatives: List[AltF[F, A]]) extends AnyVal {
  def map[B](f: A => B): Alt[F, B] = Alt(alternatives.map(_.map(f)))
}

object Alt {
  implicit def altAlternative[F[_]]: Alternative[Alt[F, ?]] = new Alternative[Alt[F, ?]] {
    def ap[A, B](ff: Alt[F, A => B])(fa: Alt[F, A]): Alt[F, B] = {
      val alternatives: List[AltF[F, B]] = ff.alternatives.flatMap{
        case AltF.Pure(a2b) => fa.map(a2b).alternatives
        case x @ AltF.Ap(fi, i2a2b) =>
          val a2i2b: Alt[F, A => x.Init => B] = i2a2b.map(f => a => i => f(i)(a))
          AltF.Ap[F, x.Init, B](fi, a2i2b.ap(fa)) :: Nil
      }
      Alt(alternatives)
    }

    def combineK[A](x: Alt[F, A], y: Alt[F, A]): Alt[F, A] = Alt(x.alternatives ::: y.alternatives)

    def pure[A](x: A): Alt[F, A] = Alt(AltF.Pure[F, A](x) :: Nil)

    def empty[A]: Alt[F, A] = Alt(Nil)

    override def map[A, B](fa: Alt[F, A])(f: A => B): Alt[F, B] = fa.map(f)
  }
}