```
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
}
// https://docs.google.com/drawings/d/1Ap5Azj1Axy8bgWPnrkm_2XC8H_YJ4imRcU3VqXXjMSU/edit?usp=sharing
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)
}
```

## Saturday, October 24, 2015

Subscribe to:
Post Comments (Atom)

## 0 comments:

Post a Comment