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)

println(myListZipper.left.get)
// Some(1)

println(myListZipper.get)
// Some(1)

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

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

println(myListZipper.right.right.right.right.right.get)
// None

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

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

Solution

Here is one possible solution. 
case class ListZipper[A](next: List[A], prev: List[A] = Nil) {

  def left: ListZipper[A] =
    prev match {
      case Nil => this
      case Cons(h, t) => ListZipper(Cons(h, next), t)
    }

  def right: ListZipper[A] =
    next match {
      case Nil => this
      case Cons(h, t) => ListZipper(t, Cons(h, prev))
    }

  def get: Option[A] =
    next match {
      case Nil => None
      case Cons(h, _) => Some(h)
    }

  def set(x: A): ListZipper[A] =
    next match {
      case Nil => ListZipper(Cons(x, Nil), prev)
      case Cons(_, t) => ListZipper(Cons(x, t), prev)
    }

  def toList: List[A] =
    prev.reverse.concat(next)
}

Demo

This file is literate Scala, and can be run using Codedown:

$ curl https://earldouglas.com/exercises/scala-list-zipper.md |
  codedown scala |
  xargs -0 scala -nc -e
Some(1)
Some(1)
Some(3)
Some(5)
None
Some(4)
Cons(1,Cons(2,Cons(42,Cons(4,Cons(5,Nil)))))