Zipper in Scala

yharaさんのRubyでZipperを実装してみたを見て、ScalaでもZipperを実装してみたくなったので、書いてみた。

実装は、基本的には
k.inabaさんのZipperの解説エントリに書かれていたのをほぼそのままScalaに移植しただけのもの。

ただ、それだけだと何なので、Scalaっぽい書き方ができるように、色々メソッドを付け足してみた。また、Scalaのコレクションとしても振舞えるように、trait Seqを継承している。さらに、Zipperはimmutableなデータ構造であり、安全にcovariantにできるため、covariantにするアノテーション(+)も付加してある。

ちょっと悩んだのが、map,flatMap,filterなどの高階関数の実装で、Zipperをイテレータの一種として見ると、現在のカーソルより後ろの部分にのみ、引数で渡された関数を適用するのが良い気がするのだが、mapやflatMapについては、そのような実装にすると、実質的に使い物にならない(たとえば、Intを要素とするZipperに対するmapの呼び出しで、Int => Stringの関数を渡すようなケースとか)。そのため、mapやflatMapについては、全要素に対して関数を適用するという中途半端な実装になっている。

final class Zipper[+A](visit: List[A], rest: List[A]) extends Seq[A] {
  private val content: (List[A], List[A]) = (visit, rest)
  def this(src: Iterable[A]) {
    this(Nil, src.toList)
  }
  def this(src: List[A]) {
    this(Nil, src)
  }
  def this(src: A*) {
    this(Nil, src.toList)
  }
  /* 基本的なメソッド群 */
  def isBegin: Boolean = content match { 
    case (Nil, _) => true case _ => false
  }
  def isEnd: Boolean = content match {
    case (_, Nil) => true case _ => false
  }
  def next: Zipper[A] = content match {
    case (l, e::r) => new Zipper(e::l, r) case _ => error("isEnd")
  }
  def prev: Zipper[A] = content match {
    case (e::l, r) => new Zipper(l, e::r) case _ => error("isBegin")
  }
  def get: A = content match {
    case (_, e::r) => e case _ => error("isEnd")
  }
  def set[B >: A](element: B): Zipper[B] = content match {
    case (l, e::r) => new Zipper(l, element::r) case _ => error("isEnd")
  }
  def insert[B >: A](element: B): Zipper[B] = content match {
    case (l, r) => new Zipper(l, element::r)
  }
  def remove: Zipper[A] = content match {
    case (l, _::r) => new Zipper(l, r) case _ => error("isEnd")
  }
  /* 短く書くためのメソッド群。実際に必要になる場面があるかどうかは知らん */
  // zipper.next.next.... == zipper + count
  def +(count: Int): Zipper[A] = {
    if(count == 0) this else this.next + (count - 1)
  }
  // zipper.prev.prev.... == zipper - count
  def -(count: Int): Zipper[A] = {
    if(count == 0) this else this.prev - (count - 1)
  }
  // zipper() == zipper.get
  def apply(): A = get
  // zipper() = element == zipper.set(element)
  def update[B >: A](element: B): Zipper[B] = set(element)
  // zipper.prev.prev....(isBeginになるまで) == zipper.reset
  def reset: Zipper[A] = {
    var z = this
    while(!z.isBegin) z = z.prev
    z
  }
  /* Seq[A] として振舞わせるために必要なメソッドの実装 */
  def apply(index: Int): A = rest(index)
  def elements: Iterator[A] = rest.elements
  def length: Int = rest.length

  /* Seq[A]として振舞わせるために必ずしも必要ではないけど、
     オーバーライドしておくと便利なメソッド群 */
  override def ++[B >: A](that: Iterable[B]): Zipper[B] = {
    new Zipper(visit, rest ++ that)
  }
  override def concat[B >: A](that: Iterable[B]): Zipper[B] = this ++ that
  override def drop(n: Int): Zipper[A] = new Zipper(visit, rest.drop(n))
  override def dropWhile(p: A => Boolean): Zipper[A] = {
    new Zipper(visit, rest.dropWhile(p))
  }
  override def map[B](f: A => B): Zipper[B] = {
    new Zipper(visit.map(f), rest.map(f))
  }
  override def filter(f: A => Boolean): Zipper[A] = {
    new Zipper(visit, rest.filter(f))
  }
  override def flatMap[B](f: A => Iterable[B]): Zipper[B] = {
    new Zipper(visit.flatMap(f), rest.flatMap(f))
  }
  override def isEmpty: Boolean = rest.isEmpty
  override def take(n: Int): Zipper[A] = {
    new Zipper(visit, rest.take(n))
  }
  override def takeWhile(p: A => Boolean): Zipper[A] = {
    new Zipper(visit, rest.takeWhile(p))
  }
  override def toString(): String = {
    val builder = new StringBuilder
    import builder._
    append("Zipper[")
    append(visit.reverse mkString ", ")
    append(if(visit.isEmpty) "^ " else if(rest.isEmpty) " ^" else ",^ ")
    append(rest mkString ", ")
    append("]")
    builder.toString
  }
}

var zipper: Zipper[Any] = new Zipper("A", "B", "C", "D", "E") // Zipper[Any] >: Zipper[String]が成り立つ。
println(zipper.next.set("NEW-B"))
println((zipper + 2).set("NEW-C"))
println((zipper + 3 - 3).set("NEW-A"))
println(zipper() = "NEW-A")
println(zipper())
println(zipper.next.map("NEW-" + _).next.next)

実行結果。

Zipper[A,^ NEW-B, C, D, E]
Zipper[A, B,^ NEW-C, D, E]
Zipper[^ NEW-A, B, C, D, E]
Zipper[^ NEW-A, B, C, D, E]
A
Zipper[NEW-A, NEW-B, NEW-C,^ NEW-D, NEW-E]

8/13追記：
Zipper#removeの定義を忘れてたので、追加。