Optimize an Applicative Program with Tagless Final

TaglessOptimize.scala

trait KVStore[F[_]] {
  def get(key: String): F[Option[String]]
  def put(key: String, a: String): F[Unit]
}

class TestInterpreter() extends KVStore[IO] {
  def get(key: String): IO[Option[String]] = IO {
    println("Hit network!")

    Option(key + "!")
  }

  def put(key: String, a: String): IO[Unit] = IO {
    println("Put something")

    ()
  }
}



val analysis: KVStore[Const[Set[String], ?]] = new KVStore[Const[Set[String], ?]] {
  def get(key: String) = Const(Set(key))
  def put(key: String, a: String): Const[Set[String], Unit] = Const(Set.empty)
}



def program[F[_]: Apply](F: KVStore[F]): F[List[String]] =
  (F.get("Hello"), F.get("World"), F.put("What", "42"), F.get("Hello"))
    .mapN((f, s, _, t) => List(f, s, t).flatten)



trait Program[Alg[_[_]], Constraint[_[_]], A] {
  type Interpreter[F[_]] = Alg[F]
  def value[F[_]: Constraint](alg: Interpreter[F]) : F[A]
}



val p = new Program[KVStore, Applicative, List[String]] {
  def value[F[_]: Applicative](alg: KVStore[F]): F[List[String]] = program(alg)
}


def analyze[Alg[_[_]], F[_]: Monad, A, M: Monoid]
  (p: Program[Alg, Applicative, A])
  (extractInterp: Alg[Const[M, ?]])
  (optimize: M => F[Alg[F]]): F[A] = {

  val fin: Const[M, A] = p.value(extractInterp)

  optimize(fin.getConst).flatMap(algf => p.value(algf))
}

val test = analyze[KVStore, IO, List[String], Set[String]](p)(analysis) { set =>
  set.toList
    .traverse(key => new TestInterpreter().get(key).map(_.map(s => (key, s))))
    .map(_.collect { case Some(v) => v }.toMap)
    .map { m =>
      new TestInterpreter() {
        override def get(key: String) = m.get(key) match {
          case Some(a) => IO.pure(Option(a))
          case None => new testInterpreter().get(key)
        }
      }
    }

}

// scala> test
// res0: cats.effect.IO[List[String]] = IO$1584863313


// scala> res0.unsafeRunSync
// Hit network!
// Hit network!
// Put something
// res1: List[String] = List(Hello!, World!, Hello!)