ðŸŽ‰ Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io ðŸŽ‰

# jseol073's solution

## to Zipper in the Scala Track

Published at May 02 2020 · 0 comments
Instructions
Test suite
Solution

Creating a zipper for a binary tree.

Zippers are a purely functional way of navigating within a data structure and manipulating it. They essentially contain a data structure and a pointer into that data structure (called the focus).

For example given a rose tree (where each node contains a value and a list of child nodes) a zipper might support these operations:

• `from_tree` (get a zipper out of a rose tree, the focus is on the root node)
• `to_tree` (get the rose tree out of the zipper)
• `value` (get the value of the focus node)
• `prev` (move the focus to the previous child of the same parent, returns a new zipper)
• `next` (move the focus to the next child of the same parent, returns a new zipper)
• `up` (move the focus to the parent, returns a new zipper)
• `set_value` (set the value of the focus node, returns a new zipper)
• `insert_before` (insert a new subtree before the focus node, it becomes the `prev` of the focus node, returns a new zipper)
• `insert_after` (insert a new subtree after the focus node, it becomes the `next` of the focus node, returns a new zipper)
• `delete` (removes the focus node and all subtrees, focus moves to the `next` node if possible otherwise to the `prev` node if possible, otherwise to the parent node, returns a new zipper)

The Scala exercises assume an SBT project scheme. The exercise solution source should be placed within the exercise directory/src/main/scala. The exercise unit tests can be found within the exercise directory/src/test/scala.

To run the tests simply run the command `sbt test` in the exercise directory.

Please see the learning and installation pages if you need any help.

## Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

### ZipperTest.scala

``````import org.scalatest.{FunSuite, Matchers}

/** @version created manually **/
class ZipperTest extends FunSuite with Matchers {
def empty[A]: Option[BinTree[A]] = None

def bt[A](v: A, l: Option[BinTree[A]], r: Option[BinTree[A]]): Option[BinTree[A]] =
Some(BinTree(v, l, r))

def leaf[A](v: A): Option[BinTree[A]] =
Some(BinTree(v, None, None))

val t1: BinTree[Int] = BinTree(1, bt(2, empty,   leaf(3)), leaf(4))
val t2: BinTree[Int] = BinTree(1, bt(5, empty,   leaf(3)), leaf(4))
val t3: BinTree[Int] = BinTree(1, bt(2, leaf(5), leaf(3)), leaf(4))
val t4: BinTree[Int] = BinTree(1, leaf(2),                 leaf(4))

def fromSome[T](o: Option[T]) = o.get

val z = Zipper

test("data is retained") {
z.toTree(z.fromTree(t1)) should be (t1)
}

test("left, right and value") {
pending
z.value(fromSome(z.right(fromSome(z.left(z.fromTree(t1)))))) should be (3)
}

pending
(z.left(fromSome(z.left(z.fromTree(t1))))) should be (None)
}

test("tree from deep focus") {
pending
z.toTree(fromSome(z.right(fromSome(z.left(z.fromTree(t1)))))) should be (t1)
}

test("setValue") {
pending
z.toTree(z.setValue(5, (fromSome(z.left(z.fromTree(t1)))))) should be (t2)
}

test("setLeft with Some") {
pending
z.toTree(z.setLeft(Some(BinTree(5, None, None)),
(fromSome(z.left(z.fromTree(t1)))))) should be (t3)
}

test("setRight with None") {
pending
z.toTree(z.setRight(None, (fromSome(z.left(z.fromTree(t1)))))) should be (t4)
}

test("different paths to same zipper") {
pending
z.right(fromSome(z.up(fromSome(z.left(z.fromTree(t1)))))) should be
(z.right(z.fromTree(t1)))
}
}``````
``````import scala.collection.immutable.Nil
trait FootPrint[A]
case class LFootPrint[A](value: A, remTree: Option[BinTree[A]]) extends FootPrint[A]
case class RFootPrint[A](value: A, remTree: Option[BinTree[A]]) extends FootPrint[A]
case class Zipper[A](value: A, left: Option[BinTree[A]], right: Option[BinTree[A]], path: List[FootPrint[A]])

// A binary tree.
case class BinTree[A](value: A, left: Option[BinTree[A]], right: Option[BinTree[A]])

object Zipper {
// A zipper for a binary tree.]

// Get a zipper focussed on the root node.
def fromTree[A](bt: BinTree[A]): Zipper[A] = {
Zipper[A](bt.value, bt.left, bt.right, Nil)
}

// Get the complete tree from a zipper.
def toTree[A](zipper: Zipper[A]): BinTree[A] = {
def _expand(currTree: BinTree[A], path: List[FootPrint[A]]): BinTree[A] = {
path match {
case Nil => currTree
case (LFootPrint(nVal, rightTree)::rest) => _expand(BinTree[A](nVal, Some(currTree), rightTree), rest)
case (RFootPrint(nVal, leftTree)::rest) => _expand(BinTree[A](nVal, leftTree, Some(currTree)), rest)
}
}
val t: BinTree[A] = BinTree[A](zipper.value, zipper.left, zipper.right)
_expand(t, zipper.path)
}

// Get the value of the focus node.
def value[A](zipper: Zipper[A]): A = zipper.value

// Get the left child of the focus node, if any.
def left[A](zipper: Zipper[A]): Option[Zipper[A]] = {
zipper.left.flatMap { t =>
fromTree(t).copy(path = LFootPrint[A](zipper.value, zipper.right) :: zipper.path)
}
}

// Get the right child of the focus node, if any.
def right[A](zipper: Zipper[A]): Option[Zipper[A]] = {
zipper.right.flatMap { t =>
fromTree(t).copy(path = RFootPrint[A](zipper.value, zipper.left) :: zipper.path)
}
}

// Get the parent of the focus node, if any.
def up[A](zipper: Zipper[A]): Option[Zipper[A]] = {
zipper.path match {
case Nil => None
case LFootPrint(nVal, remTree) :: rest => {
Some(Zipper[A](nVal, remTree, Some(BinTree[A](zipper.value, zipper.left, zipper.right)), rest))
}
case RFootPrint(nVal, remTree) :: rest => {
Some(Zipper[A](nVal, Some(BinTree[A](zipper.value, zipper.left, zipper.right)), remTree, rest))
}
}
}

// Set the value of the focus node.
def setValue[A](v: A, zipper: Zipper[A]): Zipper[A] = zipper.copy(value = v)

// Replace a left child tree.
def setLeft[A](l: Option[BinTree[A]], zipper: Zipper[A]): Zipper[A] = zipper.copy(left = l)

// Replace a right child tree.
def setRight[A](r: Option[BinTree[A]], zipper: Zipper[A]): Zipper[A] = zipper.copy(right = r)
}``````