Scalaで集合(Set)

30分プログラム、その391。Programming in Scala, Third Editionが型パラメータのとこに入ったので、コンテナっぽいクラスが作ってみたくなった。なので、集合クラスを作ってみた。

ポイントは、

class MySet[T <: Ordered[T]]

としてるので、Ordered traitを持ってるやつしか、属性として持てないところ。

ただ、残念ながらIntとかStringはOrdered traitを持ってないので、このSetクラスには格納できない。RichIntとかはOrdered traitを持ってるけど、暗黙の型変換は行なわれないみたいだし・・。

# はてなのシンタックスハイライト、Scalaに対応しないかなぁ

使い方

// 集合を作る
scala> val set1 = MySet(MyInt(1),MyInt(2))
set1: MySet[MyInt] = List(1, 2)

// 追加する
scala> val set2 = set1 + MyInt(10)
set2: MySet[MyInt] = List(1, 2, 10)

// 重複する要素は無視される
scala> val set3 = set2 + MyInt(1)
set3: MySet[MyInt] = List(1, 2, 10)

ソースコード

class MySet[T <: Ordered[T]](xs : List[T]) {
  def this() = 
    this(List())

  def +(x : T) : MySet[T] = 
    new MySet(insert(x,xs))

  private def insert(x : T, xs : List[T]) : List[T] = {
    xs  match {
      case Nil =>
	List(x)
      case y::ys =>
	if(x < y)
	  x::xs
	else if(x > y)
	  y::insert(x,ys)
	else
	  xs
    }
  }

  override def toString() =
    this.xs.toString()
}

object MySet{
  def apply[T <: Ordered[T]](xs : T*) = 
    xs.foldLeft(new MySet[T]())(_ + _)
}


class MyInt(val x : Int) extends Ordered[MyInt] {
  def compare(that : MyInt) =
    this.x - that.x

  override def toString() =
    x.toString

  def equals(that : MyInt) = 
    this.x equals that.x
}

object MyInt{
  def apply(x : Int) =
    new MyInt(x)
}

参考

• 過去の30分プログラム
• Programming in Scala, Third Edition