Red-black tree Scala版についてちょっと気になった点

(追記)Scalaでの実装。

  abstract class Node
  case class Leaf() extends Node
  case class R(left: Node, key: int, right: Node) extends Node
  case class B(left: Node, key: int, right: Node) extends Node

  def balance(left: Node, key: int, right: Node) = {
    (left, key, right) match {
      case (R(a, x, b), y, R(c, z, d)) => new R(new B(a, x, b), y, new B(c, z, d))
      case (R(R(a, x, b), y, c), z, d) => new R(new B(a, x, b), y, new B(c, z, d))
      case (R(a, x, R(b, y, c)), z, d) => new R(new B(a, x, b), y, new B(c, z, d))
      case (a, x, R(b, y, R(c, z, d))) => new R(new B(a, x, b), y, new B(c, z, d))
      case (a, x, R(R(b, y, c), z, d)) => new R(new B(a, x, b), y, new B(c, z, d))
      case _ => new B(left, key, right)
    }
  }

http://shuns.sblo.jp/article/28490553.html

Scalaでの実装としては、普通の書き方でそれほどツッコミどころは無いですが、いくつかか気になった点をば。

• case classとして宣言されたclassのオブジェクトの生成はnew不要

つまり、R(B(a, x, b), y, B(c, z, d))のように書けばOKです。

• Leafはcase object Leaf extends Nodeとして宣言できる。

case objectとして宣言した場合、Leafごとに別のメモリ領域を取らなくて済むので、メモリ領域の節約になります。

• intは非推奨

intはIntの別名ですが、現在、intの方は非推奨になってます。

• Haskell版と比較した場合、Nodeおよびbalanceの定義が多相的になってない。

多相的に定義する場合、以下のような感じになります(Haskell版と比較して、必要な型注釈が増える分冗長になりますが)。型パラメータに対する注釈である+は無くても良いですが、より汎用的にするために付けてみました。

abstract class Node[+A]
case object Leaf extends Node[Nothing]
case class R[+A](left: Node[A], key: A, right: Node[A]) extends Node[A]
case class B[+A](left: Node[A], key: A, right: Node[A]) extends Node[A]

def balance[A](left: Node[A], key: A, right: Node[A]) = {
  (left, key, right) match {
    case (R(a, x, b), y, R(c, z, d)) => R(B(a, x, b), y, B(c, z, d))
    case (R(R(a, x, b), y, c), z, d) => R(B(a, x, b), y, B(c, z, d))
    case (R(a, x, R(b, y, c)), z, d) => R(B(a, x, b), y, B(c, z, d))
    case (a, x, R(b, y, R(c, z, d))) => R(B(a, x, b), y, B(c, z, d))
    case (a, x, R(R(b, y, c), z, d)) => R(B(a, x, b), y, B(c, z, d))
    case _ => B(left, key, right)
  }
}