Recursion Scheme for GADT examples

TypedQuery.scala

// Recursive GADT

sealed trait Query[A]
case object QueryString extends Query[String]
case object QueryBool extends Query[Boolean]
case class QueryPath[A](path: String, next: Query[A]) extends Query[A]

// sample data

// {
//   "oh": {
//     "my": "zsh"
//   }
// }

// expression to query _.oh.my from JSON above

val expression = QueryPath("oh", QueryPath("my", QueryString))

// new GADT without direct recursion
sealed trait QueryF[+F[_], A]
case object QueryStringF extends QueryF[Nothing, String]
case object QueryBoolF extends QueryF[Nothing, Boolean]
case class QueryPathF[F[_], A](path: String, next: F[A]) extends QueryF[F, A]

// compiles with `-Ypartial-unification` compiler flag
val expressionF = QueryPathF("oh", QueryPathF("my", QueryStringF))

// Fix for higher kinded type
case class HFix[F[_[_], _], A](unfix: F[HFix[F, ?], A])

// helpers to create query wrapped in HFix
def queryString = HFix(QueryStringF: QueryF[HFix[QueryF,?], String])
def queryBool = HFix(QueryBoolF: QueryF[HFix[QueryF,?], Boolean])
def queryPath[A](p: String, next: HFix[QueryF, A]) = HFix(QueryPathF(p, next))

val nestedQuery = queryPath("oh", queryPath("my", queryString))

// Functor like structure to work on type with shape (* -> *) -> * -> *
import cats.~>
trait HFunctor[F[_[_], _]] {
  def hmap[I[_], J[_]](nt: I ~> J): F[I, ?] ~> F[J, ?]
}

// HFunctor instance for QueryF
implicit val queryFHFunctor: HFunctor[QueryF] = new HFunctor[QueryF] {
    def hmap[I[_], J[_]](nt: I ~> J): QueryF[I, ?] ~> QueryF[J, ?] = {
      new (QueryF[I, ?] ~> QueryF[J, ?]) {
        def apply[A](a: QueryF[I, A]): QueryF[J, A] = {
          a match {
            case QueryStringF            => QueryStringF
            case QueryBoolF              => QueryBoolF
            case query: QueryPathF[I, A] => QueryPathF(query.path, nt(query.next))
          }
        }
      }
    }
}

// type alias for the fold algebra
type HAlgebra[F[_[_], _], G[_]] = F[G, ?] ~> G

// catamorphism adapted to our type structure
def hCata[F[_[_], _], G[_], I](alg: HAlgebra[F, G],hfix: HFix[F, I])(implicit F: HFunctor[F]): G[I] = {
  val inner = hfix.unfix
  val nt = F.hmap(
    new (HFix[F, ?] ~> G) {
      def apply[A](fa: HFix[F, A]): G[A] = hCata(alg, fa)
    }
  )(inner)
  alg(nt)
}

// example: Create a string for arbitarily nested query

// a trick to fold into String, this is interesting as it shows that
// generalized type constructor is super powerful, it can be changed into a
// more specialized type easily

type JustString[A] = String

// important part: convert each layer of query into a string
val print: HAlgebra[QueryF, JustString] = new HAlgebra[QueryF, JustString] {
  override def apply[A](fa: QueryF[JustString, A]): JustString[A] = {
    fa match {
      case QueryStringF                 => "as[String]"
      case QueryBoolF                   => "as[Bool]"
      case q: QueryPathF[JustString, A] => s"${q.path}.${q.next}"
    }
  }
}

hCata(print, nestedQuery) // result: "oh.my.as[String]"

import io.circe.Decoder

val toDecoder: HAlgebra[QueryF, Decoder] = new HAlgebra[QueryF, Decoder] {
  override def apply[A](fa: QueryF[Decoder, A]): Decoder[A] = fa match {
    case QueryBoolF   => Decoder.decodeBoolean
    case QueryStringF => Decoder.decodeString
    case q: QueryPathF[Decoder, A] =>
      Decoder.instance { cursor =>
        cursor.get(q.path)(q.next)
      }
  }
}

val decoder = hCata(toDecoder, nestedQuery)

val json = parse("""
    {
      "oh": {
        "my": "20202"
      }
    }
""").right.get

decoder.decode(json) // successfully decode into Right("20202")