Four different strategies for calculating tree depth. a tail recursive version, a continuation passing version and a recursion schema version

tree.sc

#!/usr/bin/amm

import $ivy.`org.scalaz::scalaz-core:7.2.18`
import $ivy.`com.slamdata::matryoshka-core:0.18.3`

import scala.annotation.tailrec

sealed trait Tree[+A]

object Tree {
  case class Node[A] (left: Tree[A], value: A, right: Tree[A]) extends Tree[A]
  case object Empty extends Tree[Nothing]

  def height1[A](tree: Tree[A]): Int = tree match {
    case Empty => 0
    case Node(l, _, r) => 1 + math.max(height1(l), height1(r))
  }

  def height2[A](tree: Tree[A]): Int = {
    def list(l: List[Tree[A]], acc: Int) = l.map(inner(_, acc)).max
    @tailrec
    def inner(tree: Tree[A], acc: Int): Int = tree match {
      case Empty => acc
      case Node(l, _, Empty) => inner(l, acc + 1)
      case Node(Empty, _, r) => inner(r, acc + 1)
      case Node(l, _, r) => list(l :: r :: Nil, acc + 1)
    }
    inner(tree, 0)
  }

  def height3[A](tree: Tree[A]): Int = tree match {
    case Empty => 0
    case Node(left, _, right) => {
      def l(leftHeight: => Int): Int = {
        def r(rightHeight: => Int): Int = {
          1 + math.max(leftHeight, rightHeight)
        }
        r(height3(right))
      }
      l(height3(left))
    }
  }


}

import Tree._

val a: Tree[Int] = Node(Empty, 0, Empty)
val b: Tree[Int] = Node(a, 1, Empty)
val c: Tree[Int] = Node(b, 2, a)
val d: Tree[Int] = Node(c, 3, b)
val e: Tree[Int] = Node(Empty, 4, c)
val f: Tree[Int] = Node(d, 5, Empty)
val g: Tree[Int] = Node(e, 6, f)

val trees = List(a, b, c, d, e, f, g)

trees.foreach(t => println(s"Height1: ${height1(t)} Height2: ${height2(t)} Height3: ${height3(t)}"))


sealed trait Tree2[A, T]

object Tree2 {

  import scalaz.Functor
  import matryoshka._, matryoshka.implicits._

  case class System[A]() {
    type Tree[T] = Tree2[A, T]
    case class Node[T] (left: T, value: A, right: T) extends Tree[T]
    case class Empty[T]() extends Tree[T]

    implicit val TreeFunction = new Functor[Tree] {
      def map[T, V](fa: Tree[T])(f: T => V): Tree[V] = fa match {
        case Empty() => Empty[V]()
        case Node(l, v, r) => Node(f(l), v, f(r))
      }
    }

    val height: Algebra[Tree, Int] = {
      case Empty() => 0
      case Node(l, _, r) => 1 + math.max(l, r)
    }
  }

}

val s = new Tree2.System[Int]() {
  import matryoshka._, matryoshka.implicits._
  import data.Mu

  implicit def tree1[T](implicit T: Corecursive.Aux[T, Tree]): T =
    Node(Empty[T]().embed, 0, Empty[T]().embed).embed
  implicit def tree2[T](implicit T: Corecursive.Aux[T, Tree]): T =
    Node(tree1, 1, Empty[T]().embed).embed
  implicit def tree3[T](implicit T: Corecursive.Aux[T, Tree]): T =
    Node(tree2, 2, tree1).embed

  println(s"recursive schema height: ${tree3[Mu[Tree]].cata(height)}")
}