読者です 読者をやめる 読者になる 読者になる

kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

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

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です。

  • Leafcase 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)
  }
}