Created
August 26, 2012 11:06
-
-
Save robinp/3477576 to your computer and use it in GitHub Desktop.
n-ary tree zipper
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
sealed trait TreeData | |
// ... | |
// could be made generic in data | |
case class Node(data: TreeData, children: List[Node]) | |
sealed trait ZipCtx | |
case object Top extends ZipCtx | |
case class At(revLeft: List[Node], right: List[Node], ctx: ZipCtx, updata: TreeData) extends ZipCtx | |
// ZipTree(root, Top) is the start | |
case class ZipTree(n: Node, ctx: ZipCtx) { | |
private def toOption[A, B](a: A)(pf: PartialFunction[A, B]): Option[B] = | |
if (pf isDefinedAt a) Some(pf(a)) | |
else None | |
def left = toOption(ctx) { | |
case At(l :: xs, r, ctx, d) => ZipTree(l, At(xs, n :: r, ctx, d)) | |
} | |
def right = toOption(ctx) { | |
case At(l, r :: xs, ctx, d) => ZipTree(r, At(n :: l, xs, ctx, d)) | |
} | |
def down = toOption(n.children) { | |
case c :: cs => ZipTree(c, At(Nil, cs, ctx, n.data)) | |
} | |
def up = toOption(ctx) { | |
case At(l, r, upctx, d) => ZipTree(Node(d, (n :: l) reverse_::: r), upctx) | |
} | |
} | |
object ZipTree { | |
private def bindApply(f: ZipTree => Option[ZipTree])(loc: Option[ZipTree]) = loc flatMap f | |
val left = bindApply(_.left) _ | |
val right = bindApply(_.right) _ | |
def up = bindApply(_.up) _ | |
def down = bindApply(_.down) _ | |
def walk(start: Option[ZipTree])(path: Seq[Option[ZipTree] => Option[ZipTree]]) = | |
(start /: path) { | |
case (loc, f) => f(loc) | |
} | |
def rightOf(tree: ZipTree): Stream[ZipTree] = | |
tree.right map (r => Stream.cons(r, rightOf(r))) getOrElse Stream.empty | |
def children(zt: ZipTree): Stream[ZipTree] = zt.down map { | |
leftmost => | |
Stream.cons(leftmost, rightOf(leftmost)) | |
} getOrElse Stream.empty | |
def childrenKeyed(zt: ZipTree, s: String): Stream[ZipTree] = | |
children(zt) filter (_.n.data._1 == s) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment