List zipper in Scala

March 12, 2016

Given a List data structure:

sealed trait List[+A] {
  def concat[B >: A](xs: List[B]): List[B] =
    this match {
      case Nil => xs
      case Cons(h, t) => Cons(h, t.concat(xs))
    }
  def reverse: List[A] =
    this match {
      case Nil => Nil
      case Cons(h, t) => t.reverse.concat(Cons(h, Nil))
    }
}
case class Cons[A](head: A, tail: List[A]) extends List[A]
case object Nil extends List[Nothing]

Implement ListZipper:

case class ListZipper[A](next: List[A], prev: List[A] = Nil) {
  def left: ListZipper[A] = ???
  def right: ListZipper[A] = ???
  def get: Option[A] = ???
  def set(x: A): ListZipper[A] = ???
  def toList: List[A] = ???
}

Such that:

val myList: List[Int] = Cons(1, Cons(2, Cons(3, Cons(4, Cons(5, Nil)))))
val myListZipper: ListZipper[Int] = ListZipper(myList)

myListZipper.left.get
// Some(1)

myListZipper.get
// Some(1)

myListZipper.right.right.get
// Some(3)

myListZipper.right.right.right.right.get
// Some(5)

myListZipper.right.right.right.right.right.get
// None

myListZipper.right.right.right.right.right.left.left.get
// Some(4)

myListZipper.right.right.set(42).toList
// Cons(1,Cons(2,Cons(42,Cons(4,Cons(5,Nil)))))