tree-depth-hylo.scala

case class RoseF[V, A](root: V, children: List[A])

object RoseF {
  type Fixed[V] = Fix[RoseF[V, ?]]

  implicit def traverse[V]: Traverse[RoseF[V, ?]] =
    new DefaultTraverse[RoseF[V, ?]] {
      def traverse[G[_]: Applicative, A, B](
          fa: RoseF[V, A]
      )(f: A => G[B]): G[RoseF[V, B]] =
        fa match {
          case RoseF(root, children) => children.traverse(f).map(RoseF(root, _))
        }
    }

  def inc[V] = CoalgebraM[State[Int, ?], RoseF[V, ?], Fixed[V]] {
    case Fix(RoseF(root, children)) =>
      for {
        _ <- State.modify[Int](_ + 1)
      } yield RoseF(root, children)
  }
  def dec[V] = AlgebraM[State[Int, ?], RoseF[V, ?], Fixed[(V, Int)]] {
    case RoseF(root, children) =>
      for {
        d <- State.get[Int]
        _ <- State.modify[Int](_ - 1)
      } yield RoseF(root -> d, children).fix
  }
  def h[V] = scheme.hyloM(dec[V], inc[V])
}

/*
Unannotated: (∧, (⊤, (∨, (⊥, A))))
  Annotated: ((∧,1), ((⊤,2), ((∨,2), ((⊥,3), (A,3)))))
*/