ListZipper.scala

case class ListZipper[A](lefts: List[A], focus: A, rights: List[A]) {
  def map[B](f: A => B): ListZipper[B] =
    ListZipper(lefts map f, f(focus), rights map f)

  def ap[B](f: ListZipper[A => B]): ListZipper[B] =
    ListZipper(
      f.lefts.zip(lefts).map { case (ff, aa) => ff(aa) }
    , f.focus(focus)
    , f.rights.zip(rights).map { case (ff, aa) => ff(aa) }
    )

  def moveLeft: Option[ListZipper[A]] =
    lefts match {
      case Nil =>
        None
      case h::t =>
        Some(ListZipper(focus::lefts, h, t))
    }

  def moveRight: Option[ListZipper[A]] =
    rights match {
      case Nil =>
        None
      case h::t =>
        Some(ListZipper(t, h, focus::rights))
    }

  def moveStart: ListZipper[A] =
    moveLeft match {
      case None =>
        this
      case Some(x) =>
        x.moveStart
    }

  def moveLeftLoop: ListZipper[A] =
    moveLeft getOrElse moveEnd

  def moveRightLoop: ListZipper[A] =
    moveRight getOrElse moveStart

  def moveEnd: ListZipper[A] =
    moveRight match {
      case None =>
        this
      case Some(x) =>
        x.moveEnd
    }

  def insertStepLeft(a: A): ListZipper[A] =
    ListZipper(focus::lefts, a, rights)

  def insertStepRight(a: A): ListZipper[A] =
    ListZipper(lefts, a, focus::rights)

  def deleteStepLeft: Option[ListZipper[A]] =
    lefts match {
      case Nil =>
        None
      case _::t =>
        Some(ListZipper(t, focus, rights))
    }

  def deleteStepRight: Option[ListZipper[A]] =
    rights match {
      case Nil =>
        None
      case _::t =>
        Some(ListZipper(lefts, focus, t))
    }

  def duplicate: ListZipper[ListZipper[A]] = {
    def dup[X]: X => (X, X) =
      x => (x, x)
    ListZipper(
      List.unfold(this)(_.moveLeft.map(dup))
    , this
    , List.unfold(this)(_.moveRight.map(dup))
    )
  }

  def atStart: Boolean =
    lefts.isEmpty

  def atEnd: Boolean =
    rights.isEmpty

  def modifyFocus[B](f: A => A): ListZipper[A] =
    ListZipper(lefts, f(focus), rights)

  def modifyLefts[B](f: List[A] => List[A]): ListZipper[A] =
    ListZipper(f(lefts), focus, rights)

  def modifyRights[B](f: List[A] => List[A]): ListZipper[A] =
    ListZipper(lefts, focus, f(rights))

  def findLeft(f: A => Boolean): Option[ListZipper[A]] = {
    val x = moveLeft
    if(x.exists(c => f(c.focus)))
      x
    else
      x.flatMap(_.findLeft(f))
  }

  def findRight(f: A => Boolean): Option[ListZipper[A]] = {
    val x = moveRight
    if(x.exists(c => f(c.focus)))
      x
    else
      x.flatMap(_.findRight(f))
  }

  def moveLeftN(n: Int): Option[ListZipper[A]] = {
    if(n < 0)
      moveRightN(n.abs)
    else
      moveLeft.flatMap(_.moveLeftN(n - 1))
  }

  def moveRightN(n: Int): Option[ListZipper[A]] = {
    if(n < 0)
      moveLeftN(n.abs)
    else
      moveRight.flatMap(_.moveRightN(n - 1))
  }

  def zip[B](x: ListZipper[B]): ListZipper[(A, B)] =
    ListZipper(lefts.zip(x.lefts), (focus, x.focus), rights.zip(x.rights))

  def reverse: ListZipper[A] =
    ListZipper(rights.reverse, focus, lefts.reverse)

  def toList: List[A] =
    lefts.reverse ::: focus :: rights
}

object ListZipper {
  def fromList[A](x: List[A]): Option[ListZipper[A]] =
    x match {
      case Nil =>
        None
      case h::t =>
        Some(fromNonEmptyList(h, t))
    }

  def fromNonEmptyList[A](h: A, t: List[A]): ListZipper[A] =
    ListZipper(Nil, h, t)

}

case class ListZipperOp[A, B](run: ListZipper[A] => Option[(ListZipper[A], B)]) {
  def map[C](f: B => C): ListZipperOp[A, C] =
    ListZipperOp((z: ListZipper[A]) => run(z).map {
      case (zz, b) => (zz, f(b))
    })

  def flatMap[C](f: B => ListZipperOp[A, C]): ListZipperOp[A, C] =
    ListZipperOp((z: ListZipper[A]) => run(z).flatMap {
      case (zz, b) =>
        f(b).run(zz)
    })

  def orElse(x: ListZipperOp[A, B]): ListZipperOp[A, B] =
    ListZipperOp(z => run(z) orElse x.run(z))

  def exec(z: ListZipper[A]): Option[ListZipper[A]] =
    run(z).map(_._1)

  def eval(z: ListZipper[A]): Option[B] =
    run(z).map(_._2)

  def stepWith[C](f: A => Option[C]): ListZipperOp[A, C] =
    ListZipperOp(z => {
      def go(zz: ListZipper[A]): Option[(ListZipper[A], C)] = {
        val x = zz.focus
        f(x) match {
          case None =>
            exec(zz).flatMap(zzz => go(zzz))
          case Some(w) =>
            Some(zz, w)
        }
      }

      go(z)
    })
}

object ListZipperOp {
  type ListZipperOp_[A] =
    ListZipperOp[A, Unit]

  def point[A, B](b: B): ListZipperOp[A, B] =
    ListZipperOp(z => Some((z, b)))

  def optionListZipperOp[A, B](f: ListZipper[A] => Option[B]): ListZipperOp[A, B] =
    ListZipperOp(z => f(z).map(b => (z, b)))

  def liftOption[A, B](x: => Option[B]): ListZipperOp[A, B] =
    ListZipperOp(z => x.map(b => (z, b)))

  def get[A]: ListZipperOp[A, ListZipper[A]] =
    ListZipperOp(z => Some(z, z))

  def getFocus[A]: ListZipperOp[A, A] =
    get.map(_.focus)

  def getLefts[A]: ListZipperOp[A, List[A]] =
    get.map(_.lefts)

  def getRights[A]: ListZipperOp[A, List[A]] =
    get.map(_.rights)

  def listZipperOp_[A](f: ListZipper[A] => Option[ListZipper[A]]): ListZipperOp_[A] =
    ListZipperOp(z => f(z).map(zz => (zz, ())))

  def run_[A](o: ListZipperOp_[A], z: ListZipper[A]): Option[ListZipper[A]] =
    o.run(z).map(_._1)

  def always[A, B](f: ListZipper[A] => (ListZipper[A], B)): ListZipperOp[A, B] =
    ListZipperOp(z => Some(f(z)))

  def always_[A](f: ListZipper[A] => ListZipper[A]): ListZipperOp_[A] =
    listZipperOp_(z => Some(f(z)))

  def never[A, B]: ListZipperOp[A, B] =
    ListZipperOp(_ => None)

  def moveLeft[A]: ListZipperOp_[A] =
    listZipperOp_(_.moveLeft)

  def moveRight[A]: ListZipperOp_[A] =
    listZipperOp_(_.moveRight)

  def moveLeftLoop[A]: ListZipperOp_[A] =
    always_(_.moveLeftLoop)

  def moveRightLoop[A]: ListZipperOp_[A] =
    always_(_.moveRightLoop)

  def moveStart[A]: ListZipperOp_[A] =
    always_(_.moveStart)

  def moveEnd[A]: ListZipperOp_[A] =
    always_(_.moveEnd)

  def insertStepLeft[A](a: A): ListZipperOp_[A] =
    always_(_.insertStepLeft(a))

  def insertStepRight[A](a: A): ListZipperOp_[A] =
    always_(_.insertStepRight(a))

  def deleteStepLeft[A]: ListZipperOp_[A] =
    listZipperOp_(_.deleteStepLeft)

  def deleteStepRight[A]: ListZipperOp_[A] =
    listZipperOp_(_.deleteStepRight)

  def modifyFocus[A](f: A => A): ListZipperOp_[A] =
    always_(_.modifyFocus(f))

  def modifyLefts[A](f: List[A] => List[A]): ListZipperOp_[A] =
    always_(_.modifyLefts(f))

  def modifyRights[A](f: List[A] => List[A]): ListZipperOp_[A] =
    always_(_.modifyRights(f))

  def findLeft[A](f: A => Boolean): ListZipperOp_[A] =
    listZipperOp_(_.findLeft(f))

  def findRight[A](f: A => Boolean): ListZipperOp_[A] =
    listZipperOp_(_.findRight(f))

  def moveLeftN[A](n: Int): ListZipperOp_[A] =
    listZipperOp_(_.moveLeftN(n))

  def moveRightN[A](n: Int): ListZipperOp_[A] =
    listZipperOp_(_.moveRightN(n))
}