# Scalaz（23）－ 泛函数据结构： Zipper-游标定位

`final case class Zipper[+A](lefts: Stream[A], focus: A, rights: Stream[A])`

```final case class Zipper[+A](
lefts: Stream[A],
focus: A,
rights: Stream[A])```

scalaz提供了Zipper构建函数可以直接用Stream生成一个Zipper:

```trait StreamFunctions {
...
final def toZipper[A](as: Stream[A]): Option[Zipper[A]] = as match {
case Empty   => None
case h #:: t => Some(Zipper.zipper(empty, h, t))
}

final def zipperEnd[A](as: Stream[A]): Option[Zipper[A]] = as match {
case Empty => None
case _     =>
val x = as.reverse
}
...```

zipperEnd生成倒排序的Zipper:

```1   Stream(1,2,3).toZipper                          //> res2: Option[scalaz.Zipper[Int]] = Some(Zipper(<lefts>, 1, <rights>))
2   Stream("A","B","C").toZipper                    //> res3: Option[scalaz.Zipper[String]] = Some(Zipper(<lefts>, A, <rights>))
3   Stream(Stream(1,2),Stream(3,4)).toZipper        //> res4: Option[scalaz.Zipper[scala.collection.immutable.Stream[Int]]] = Some(Z
4                                                   //| ipper(<lefts>, Stream(1, ?), <rights>))
5   Stream(1,2,3).zipperEnd                         //> res5: Option[scalaz.Zipper[Int]] = Some(Zipper(<lefts>, 3, <rights>))```

scalaz也为List，NonEmptyList提供了Zipper构建函数：

```trait ListFunctions {
...
final def toZipper[A](as: List[A]): Option[Zipper[A]] =
stream.toZipper(as.toStream)

final def zipperEnd[A](as: List[A]): Option[Zipper[A]] =
stream.zipperEnd(as.toStream)
...

final class NonEmptyList[+A] private[scalaz](val head: A, val tail: List[A]) {
...
def toZipper: Zipper[A] = zipper(Stream.Empty, head, tail.toStream)

def zipperEnd: Zipper[A] = {
import Stream._
tail.reverse match {
case Nil     => zipper(empty, head, empty)
case t :: ts => zipper(ts.toStream :+ head, t, empty)
}
}
...```

```trait ZipperFunctions {
def zipper[A](ls: Stream[A], a: A, rs: Stream[A]): Zipper[A] =
Zipper(ls, a, rs)
}```

```1 List(1,2,3,4).toZipper                          //> res0: Option[scalaz.Zipper[Int]] = Some(Zipper(<lefts>, 1, <rights>))
2   List(List(1,2),List(2,3)).toZipper              //> res1: Option[scalaz.Zipper[List[Int]]] = Some(Zipper(<lefts>, List(1, 2), <r
3                                                   //| ights>))
4   NonEmptyList("A","C","E").toZipper              //> res2: scalaz.Zipper[String] = Zipper(<lefts>, A, <rights>)
5   NonEmptyList(1,2,3).zipperEnd                   //> res3: scalaz.Zipper[Int] = Zipper(<lefts>, 3, <rights>)
6  ```

```final case class Zipper[+A](lefts: Stream[A], focus: A, rights: Stream[A]) {
...
/**
* Possibly moves to next element to the right of focus.
*/
def next: Option[Zipper[A]] = rights match {
case Stream.Empty => None
case r #:: rs     => Some(zipper(Stream.cons(focus, lefts), r, rs))
}

/**
* Possibly moves to next element to the right of focus.
*/
def nextOr[AA >: A](z: => Zipper[AA]): Zipper[AA] =
next getOrElse z
/**
* Possibly moves to the previous element to the left of focus.
*/
def previous: Option[Zipper[A]] = lefts match {
case Stream.Empty => None
case l #:: ls     => Some(zipper(ls, l, Stream.cons(focus, rights)))
}

/**
* Possibly moves to previous element to the left of focus.
*/
def previousOr[AA >: A](z: => Zipper[AA]): Zipper[AA] =
previous getOrElse z
/**
* Moves focus n elements in the zipper, or None if there is no such element.
*
* @param  n  number of elements to move (positive is forward, negative is backwards)
*/
def move(n: Int): Option[Zipper[A]] = {
@tailrec
def move0(z: Option[Zipper[A]], n: Int): Option[Zipper[A]] =
if (n > 0 && rights.isEmpty || n < 0 && lefts.isEmpty) None
else {
if (n == 0) z
else if (n > 0) move0(z flatMap ((_: Zipper[A]).next), n - 1)
else move0(z flatMap ((_: Zipper[A]).previous), n + 1)
}
move0(Some(this), n)
}

/**
* Moves focus to the start of the zipper.
*/
def start: Zipper[A] = {
val rights = this.lefts.reverse ++ focus #:: this.rights
}

/**
* Moves focus to the end of the zipper.
*/
def end: Zipper[A] = {
val lefts = this.rights.reverse ++ focus #:: this.lefts
}

/**
* Moves focus to the nth element of the zipper, or the default if there is no such element.
*/
def moveOr[AA >: A](n: Int, z: => Zipper[AA]): Zipper[AA] =
move(n) getOrElse z
...```

start,end,move,next,previous移动方式都齐了。还有定位函数：

```...
/**
* Moves focus to the nearest element matching the given predicate, preferring the left,
* or None if no element matches.
*/
def findZ(p: A => Boolean): Option[Zipper[A]] =
if (p(focus)) Some(this)
else {
val c = this.positions
std.stream.interleave(c.lefts, c.rights).find((x => p(x.focus)))
}

/**
* Moves focus to the nearest element matching the given predicate, preferring the left,
* or the default if no element matches.
*/
def findZor[AA >: A](p: A => Boolean, z: => Zipper[AA]): Zipper[AA] =
findZ(p) getOrElse z

/**
* Given a traversal function, find the first element along the traversal that matches a given predicate.
*/
def findBy[AA >: A](f: Zipper[AA] => Option[Zipper[AA]])(p: AA => Boolean): Option[Zipper[AA]] = {
@tailrec
def go(zopt: Option[Zipper[AA]]): Option[Zipper[AA]] = {
zopt match {
case Some(z) => if (p(z.focus)) Some(z) else go(f(z))
case None    => None
}
}
go(f(this))
}

/**
* Moves focus to the nearest element on the right that matches the given predicate,
* or None if there is no such element.
*/
def findNext(p: A => Boolean): Option[Zipper[A]] = findBy((z: Zipper[A]) => z.next)(p)

/**
* Moves focus to the previous element on the left that matches the given predicate,
* or None if there is no such element.
*/
def findPrevious(p: A => Boolean): Option[Zipper[A]] = findBy((z: Zipper[A]) => z.previous)(p)
...```

```...
/**
* An alias for insertRight
*/
def insert[AA >: A]: (AA => Zipper[AA]) = insertRight(_: AA)

/**
* Inserts an element to the left of focus and focuses on the new element.
*/
def insertLeft[AA >: A](y: AA): Zipper[AA] = zipper(lefts, y, focus #:: rights)

/**
* Inserts an element to the right of focus and focuses on the new element.
*/
def insertRight[AA >: A](y: AA): Zipper[AA] = zipper(focus #:: lefts, y, rights)

/**
* An alias for `deleteRight`
*/
def delete: Option[Zipper[A]] = deleteRight

/**
* Deletes the element at focus and moves the focus to the left. If there is no element on the left,
* focus is moved to the right.
*/
def deleteLeft: Option[Zipper[A]] = lefts match {
case l #:: ls     => Some(zipper(ls, l, rights))
case Stream.Empty => rights match {
case r #:: rs     => Some(zipper(Stream.empty, r, rs))
case Stream.Empty => None
}
}

/**
* Deletes the element at focus and moves the focus to the left. If there is no element on the left,
* focus is moved to the right.
*/
def deleteLeftOr[AA >: A](z: => Zipper[AA]): Zipper[AA] =
deleteLeft getOrElse z

/**
* Deletes the element at focus and moves the focus to the right. If there is no element on the right,
* focus is moved to the left.
*/
def deleteRight: Option[Zipper[A]] = rights match {
case r #:: rs     => Some(zipper(lefts, r, rs))
case Stream.Empty => lefts match {
case l #:: ls     => Some(zipper(ls, l, Stream.empty))
case Stream.Empty => None
}
}

/**
* Deletes the element at focus and moves the focus to the right. If there is no element on the right,
* focus is moved to the left.
*/
def deleteRightOr[AA >: A](z: => Zipper[AA]): Zipper[AA] =
deleteRight getOrElse z

/**
* Deletes all elements except the focused element.
*/
def deleteOthers: Zipper[A] = zipper(Stream.Empty, focus, Stream.Empty)
...
/**
* Update the focus in this zipper.
*/
def update[AA >: A](focus: AA) = {
this.copy(this.lefts, focus, this.rights)
}

/**
* Apply f to the focus and update with the result.
*/
def modify[AA >: A](f: A => AA) = this.update(f(this.focus))
...```

insert,modify,delete也很齐备。值得注意的是多数Zipper的移动函数和操作函数都返回Option[Zipper[A]]类型，如此我们可以用flatMap把这些动作都连接起来。换句话说就是我们可以用for-comprehension在Option的context内实现行令编程（imperative programming）。我们可以通过一些例子来示范Zipper用法：

``` 1 val zv = for {
2     z <- List(2,8,1,5,4,11).toZipper
3     s1 <- z.next
4     s2 <- s1.modify{_ + 2}.some
5   } yield s2                                      //> zv  : Option[scalaz.Zipper[Int]] = Some(Zipper(<lefts>, 10, <rights>))
6
7   zv.get.show          //> res8: scalaz.Cord = Zipper(Stream(2), 10, Stream(1,5,4,11))
8   zv.get.toList        //> res9: List[Int] = List(2, 10, 1, 5, 4, 11)
9 ...
10 val zv = for {
11     z <- List(2,8,1,5,4,11).toZipper
12     s1 <- z.next
13     s2 <- s1.modify{_ + 2}.some
14     s3 <- s2.move(1)
15     s4 <- s3.delete
16   } yield s4                                      //> zv  : Option[scalaz.Zipper[Int]] = Some(Zipper(<lefts>, 5, <rights>))
17
18   zv.get.show       //> res8: scalaz.Cord = Zipper(Stream(10,2), 5, Stream(4,11))
19   zv.get.toList     //> res9: List[Int] = List(2, 10, 5, 4, 11)
20 ...
21 val zv = for {
22     z <- List(2,8,1,5,4,11).toZipper
23     s1 <- z.next
24     s2 <- s1.modify{_ + 2}.some
25     s3 <- s2.move(1)
26     s4 <- s3.delete
27     s5 <- s4.findZ {_ === 11}
28     s6 <- if (s5.focus === 12) s5.delete else s2.insert(12).some
29   } yield s6                                      //> zv  : Option[scalaz.Zipper[Int]] = Some(Zipper(<lefts>, 12, <rights>))
30
31   zv.get.show        //> res8: scalaz.Cord = Zipper(Stream(10,2), 12, Stream(1,5,4,11))
32   zv.get.toList      //> res9: List[Int] = List(2, 10, 12, 1, 5, 4, 11)
33 ...
34 val zv = for {
35     z <- List(2,8,1,5,4,11).toZipper
36     s1 <- z.next
37     s2 <- s1.modify{_ + 2}.some
38     s3 <- s2.move(1)
39     s4 <- s3.delete
40     s5 <- s4.findZ {_ === 11}
41     s6 <- if (s5.focus === 12) s5.delete else s2.insert(12).some
42     s7 <- s6.end.delete
43     s8 <- s7.start.some
44   } yield s8                                      //> zv  : Option[scalaz.Zipper[Int]] = Some(Zipper(<lefts>, 2, <rights>))
45
46   zv.get.show         //> res8: scalaz.Cord = Zipper(Stream(), 2, Stream(10,12,1,5,4))
47   zv.get.toList       //> res9: List[Int] = List(2, 10, 12, 1, 5, 4)```

```def peak(list: List[Int]): Option[Int] = {
list.indices.find { index =>
val x = list(index)
index > 0 && index < list.size - 1 &&
x > list(index - 1) && x > list(index + 1)
}.map(list(_))
}```

```def peak_fp(list: List[Int]): Option[Int] = list match {
case x :: y :: z :: tl if y > x && y > z => Some(y)
case x :: tl => peak(tl)
case Nil => None
}  ```

```def raisePeak(list: List[Int]): Option[List[Int]] = {
def rec(head: List[Int], tail: List[Int]): Option[List[Int]] = tail match {
case x :: y :: z :: tl if y > x && y > z =>
Some((x :: head).reverse ::: ((y +1) :: z :: tl))
case x :: tl => rec(x :: head, tl) case Nil => None
}
rec(List.empty, list)
}```

```def raisePeak_z(list: List[Int]): Option[List[Int]] = {
for {
zipper <- list.toZipper
peak <- zipper.positions.findNext( z =>
(z.previous, z.next) match {
case (Some(p), Some(n)) => p.focus < z.focus && n.focus < z.focus
case _ => false
})
} yield (peak.focus.modify(_ + 1).toStream.toList)
}```

```/**
* A zipper of all positions of the zipper, with focus on the current position.
*/
def positions: Zipper[Zipper[A]] = {
val left = std.stream.unfold(this)(_.previous.map(x => (x, x)))
val right = std.stream.unfold(this)(_.next.map(x => (x, x)))

zipper(left, this, right)
}```

positions函数返回类型是Zipper[Zipper[A]]符合findNext使用。我们前面已经提到：使用Zipper的成本约为O(n)。

0 条评论

## 相关文章

884

1816

### Scalaz（48）－ scalaz-stream: 深入了解-Transducer: Process1-tee-wye

在上一篇讨论里我们介绍了Source，它的类型款式是这样的：Process[F[_],O]。Source是通过await函数来产生数据流。await函数款...

2025

2745

2128

### 我的WCF之旅（4）：WCF中的序列化[下篇]

XMLSerializer 提到XMLSerializer，我想绝大多数人都知道这是asmx采用的Serializer。首先我们还是来看一个例子，通过比较Ma...

18910

### 如何理解 golang nil

golang 中的 nil 是不同于其他语言的，为了更好的理解 nil，在此我将尝试一步一步揭示 nil 在 golang 中的一些操作和现象。 1. nil ...

3155

### 动态调用WebService

http://linglong117.blog.163.com/blog/static/277145472009127514463/

731

### 聊聊storm的PartialKeyGrouping

storm-core-1.2.2-sources.jar!/org/apache/storm/grouping/PartialKeyGrouping.java

862

923