数列圧縮変形版

2008-09-26で提案されている変形版をsumimさんがSqueakを使って華麗に解いていたので、Scalaでマネしてみた。

abstract class Compact {
  def ::(l: Compact): Compact =CompactList(l,this)
  def ::(l: Int): Compact
}

case class CompactList(car: Compact, cdr: Compact) extends Compact {
  def ::(l: Int) = (l::car)::cdr
  override def toString = car+" , "+cdr
}

case class Interval(s:Int, e:Int, step:Int) extends Compact{
  def ::(l: Int): Compact = if(l==s-step) Interval(l,e,step) else notMatch(l)
  def notMatch(l: Int) = N(l)::this
}

case class Pair(e1: Int, e2: Int) extends Interval(e1,e2,e2-e1) {
  override def notMatch(l: Int) = Pair(l,s)::N(e)
  override def toString = e1+" , "+e2
}

case class N(n: Int) extends Interval(n,n,0) {
  override def ::(l: Int): Compact = Pair(l,n)
  override def toString = n.toString
}

object N extends N(0) {
  override def ::(l: Int): Compact = N(l)
}
実行結果
  >println(1::4::6::8::9::10::11::12::15::N)
  1 , 4 , 6 , Interval(8,12,1) , 15

Squeak版と違って既存クラスをうまく使えてないねー><。Implicit Conversionとか使えばうまくいくのかなー。
さすが動的言語は拡張性が高いねぇ。

あと::演算子が左結合なせいでSqueak版と違う答えが返ってくる。何通りか答えあるのね。