Treeのfoldと、それを用いた各種関数実装

TreeFold.scala

trait Tree[A]
case class Leaf[A](v: A) extends Tree[A]
case class Branch[A](l: Tree[A], r: Tree[A]) extends Tree[A]


def fold[A, B](t: Tree[A])(map: A => B, construct: (B, B) => B): B = t match {
  case Leaf(v) => map(v)
  case Branch(l, r) => construct(fold(l)(map, construct), fold(r)(map, construct))
}

def size[A](t: Tree[A]): Int = fold[A, Int](t)(_ => 1, _ + _)
def maximum(t: Tree[Int]): Int = fold[Int, Int](t)(a => a, _ max _)
def depth[A](t: Tree[A]): Int = fold[A, Int](t)(_ => 1, (l, r) => (l max r) + 1)
def map[A, B](t: Tree[A])(f: A => B): Tree[B] = fold[A, Tree[B]](t)(v => Leaf(f(v)), Branch(_, _))



val tTree = Branch(Leaf(1), Branch(Leaf(2), Branch(Branch(Leaf(3), Leaf(5)), Leaf(4))))
size(tTree)
maximum(tTree)
depth(tTree)
depth(Leaf(1))
map(tTree)(_ * 2)
maximum(map(tTree)(_ * 2))