Tree.scala

// data Tree a = Leaf | Branch a (Tree a) (Tree a) deriving Show
//
// isEmpty :: Tree a -> Bool
// isEmpty Leaf = True
// isEmpty _    = False
//
// insert :: Ord a => a -> Tree a -> Tree a
// insert e Leaf = Branch e Leaf Leaf
// insert e b@(Branch e' l r)
//   | e < e'    = Branch e' (insert e l) r
//   | e == e'   = b
//   | otherwise = Branch e' l (insert e r)

  
sealed abstract class Tree[+T] {
  def isEmpty: Boolean
  def insert[A >: T <% Ordered[A]](elem: A): Tree[A]
}

case object Leaf extends Tree[Nothing] {
  def isEmpty = true
  def insert[T <% Ordered[T]](elem: T): Tree[T] = Branch(elem, Leaf, Leaf)
}

case class Branch[+T](elem: T, left: Tree[T], right: Tree[T]) extends Tree[T] {
  def isEmpty = false
  def insert[A >: T <% Ordered[A]](newElem: A): Tree[A] =
    if (newElem < elem)  // elem > newElemだとtype mismatch
      Branch(elem, left.insert(newElem), right)
    else if (elem == newElem)
      Branch(elem, left, right)
    else
      Branch(elem, left, right.insert(newElem))
}

object TreeExample extends Application {
  println(Leaf.insert(1).insert(10).insert(5))
}

// => Branch(1,Leaf,Branch(10,Branch(5,Leaf,Leaf),Leaf))