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)))))
case class ListZipper[A](next: List[A], prev: List[A] = Nil) {
def left: ListZipper[A] =
match {
prev case Nil => this
case Cons(h, t) => ListZipper(Cons(h, next), t)
}
def right: ListZipper[A] =
match {
next case Nil => this
case Cons(h, t) => ListZipper(t, Cons(h, prev))
}
def get: Option[A] =
match {
next case Nil => None
case Cons(h, _) => Some(h)
}
def set(x: A): ListZipper[A] =
match {
next case Nil => ListZipper(Cons(x, Nil), prev)
case Cons(_, t) => ListZipper(Cons(x, t), prev)
}
def toList: List[A] =
.reverse.concat(next)
prev}
This file is literate Scala, and can be run using Codedown:
$ curl https://earldouglas.com/posts/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)))))