ok_recursion_schemes.scala

object RecursionSchemes extends App {
  import PropertyTreeX._

  sealed trait PropertyTreeX[+K, +V, +A]

  object PropertyTreeX {

    final case object EmptyX extends PropertyTreeX[Nothing, Nothing, Nothing]

    final case class LeafX[+V](value: V) extends PropertyTreeX[Nothing, V, Nothing]

    final case class RecordX[K, +A](value: Map[K, A]) extends PropertyTreeX[K, Nothing, A]
  }

  final case class Fix[F[_]](unfix: F[Fix[F]])

  def cata[F[_], A](f: F[A] => A)(implicit F: Functor[F]): Fix[F] => A =
    fix => f(F.map(fix.unfix)(cata(f)))

  trait Functor[F[_]] {
    def map[A, B](fa: F[A])(f: A => B): F[B]
  }

  object Functor {
    implicit def functorInstance[K, V]: Functor[PropertyTreeX[K, V, ?]] = new Functor[PropertyTreeX[K, V, ?]] {
      override def map[A, B](sa: PropertyTreeX[K, V, A])(f: A => B): PropertyTreeX[K, V, B] =
        sa match {
          case EmptyX         => EmptyX
          case LeafX(v)       => LeafX(v)
          case RecordX(value) => RecordX(value.view.mapValues(f).toMap)
        }
    }
  }

  def empty(): Fix[PropertyTreeX[Nothing, Nothing, ?]] =
    Fix[PropertyTreeX[Nothing, Nothing, ?]](EmptyX)

  def record[K, V](value: Map[K, Fix[PropertyTreeX[K, V, ?]]]): Fix[PropertyTreeX[K, V, ?]] =
    Fix[PropertyTreeX[K, V, ?]](RecordX(value))

  def leaf[K, V](value: V): Fix[PropertyTreeX[K, V, ?]] =
    Fix[PropertyTreeX[K, V, ?]](LeafX(value))

  // Quite a simple recursion that doesn't worry about the structure of V, however, V itself is PropertyTree
  def propertyAccumulator[K, V](zero: V)(f: (V, V) => V): PropertyTreeX[K, V, V] => V = {
    case EmptyX       => zero
    case LeafX(value) => value
    case RecordX(map) => map.view.values.fold(zero)(f)
  }

  val result =
    cata(propertyAccumulator[String, String]("")(_ + _))

  val property: Fix[PropertyTreeX[String, String, ?]] =
    record(
      Map(
        "string" ->
          record(
            Map("string2" -> record(Map("string3" -> leaf("value"))))
          ),
        "anotherstring" ->
          record(
            Map("string2" -> record(Map("string3" -> leaf("value2"))))
          )
      )
    )

  // Converting property tree to its fixed type is easy.
  val res = result(property)

  println(res)
  // convert a Map[Vector[K], V] to PropertyTree[K, V, A]
  // Convert a PropertyTree[K, V, A] to Map[Vector[K], V, A]

}