## Functional programming in Scala, Chapter 3, Tree implementation

object Example {

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]

def size(tree: Tree[_]): Int = {
tree match {
case _: Leaf[_] => 1
case x: Branch[_] => size(x.left) + size(x.right)
}
}
def size1[A](tree: Tree[A]): Int = {
fold[A, Int](tree)(a => 1)(_ + _)
}
def maximum(tree: Tree[Int]): Int = tree match {
case l: Leaf[_] => l.asInstanceOf[Leaf[Int]].value
case b: Branch[_] => maximum(b.left.asInstanceOf[Tree[Int]]) max maximum(b.right.asInstanceOf[Tree[Int]])
}
def maximum1(tree: Tree[Int]): Int = fold(tree)(a => a)(_ max _)

def depth(tree: Tree[_]): Int = tree match {
case _: Leaf[_] => 0
case b: Branch[_] => (depth(b.left) max depth(b.right)) + 1
}
def depth1(tree: Tree[_]): Int = {
// Leaf has level 0
fold(tree)(a => 0)((d1, d2) => 1 + (d1 max d2))
}

def map[A, B](tree: Tree[A])(f: A => B): Tree[B] = tree match {
case l: Leaf[_] => Leaf(f(l.asInstanceOf[Leaf[A]].value))
case b: Branch[_] => {
val b1 = b.asInstanceOf[Branch[A]]
Branch(map(b1.left)(f), map(b1.right)(f))
}
}

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

def fold[A, B](tree: Tree[A])(f: A => B)(g: (B, B) => B): B = tree match {
case Leaf(a) => f(a)
case Branch(b1, b2) => {
g(fold(b1)(f)(g), fold(b2)(f)(g))
}
}
}

object Test {

import Example._

val t = Branch(Leaf(1), Branch(Leaf(1), Leaf(13)))
size(t)
depth(t)
depth1(t)
maximum(t)
maximum1(t)
map(t)(x => x + 1)
map1(t)(x => x + 1)
}