# 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)))))