Scalaツリー遊び（Scala関数型デザインより）

リスト秋田県。 ツリーで遊ぶ。 2分木ツリーだよ。

package 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]

object Tree {

  def size[A](t: Tree[A]): Int = t match {
    case Leaf(_) => 1
    case Branch(l,r) => 1 + size(l) + size(r)
  }

  def maximum(t: Tree[Int]): Int = t match {
    case Leaf(i) => i
    case Branch(l,r) => maximum(l) max maximum(r)
  }

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

  def main(args: Array[String]): Unit = {
    val tree = Branch(Leaf(1), Branch(Leaf(2), Leaf(3)))
    val n = size(tree)
    println(s"n:${n}")
  }
}

• sizeメソッド：Treeのノード数を返す
  matchの形を覚える。
• maximum：Treeの値の最大値を返す 再帰の戻り値で、最大値を返すようにしていく。
• map:Treeに対して、mapする Leafの場合は、Leafの中身にfを適用して、Leafでつつむ。
  Branchの場合は、lとr、それぞれに適用して、Branchでやさしく、つつむ。