tree.scala

sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

object Tree {
  // 3.29, FP in Scala
  def identity[A](a: A): A = a // I combinator
  def constant[A,B](a: A)(b: B): A = a // K combinator

  def map[A,B](t: Tree[A])(f: A => B): Tree[B] =
    fold(t)(a => Leaf(f(a)): Tree[B])(Branch(_, _))

  def size[A](t: Tree[A]): Int =
    fold(t)(constant(1))(_ + _)

  def max(t: Tree[Int]): Int =
    fold(t)(identity)(_ max _)

  def depth(t: Tree[Int]): Int =
    fold(t)(constant(0))((l, r) => 1 + (l max r))

  def fold[A,B](t: Tree[A])(f: A => B)(g: (B, B) => B): B = t match {
    case Leaf(a) => f(a)
    case Branch(l, r) => g(fold(l)(f)(g), fold(r)(f)(g))
  }
}