Scalaz(23)- 泛函数据结构: Zipper-游标定位
外面沙尘滚滚一直向北去了,意识到年关到了,码农们都回乡过年去了,而我却留在这里玩弄“拉链”。不要想歪了,我说的不是裤裆拉链而是scalaz Zipper,一种泛函数据结构游标(cursor)。在函数式编程模式里的集合通常是不可变的(immutable collection),我们会发现在FP编程过程中处理不可变集合(immutable collection)数据的方式好像总是缺些什么,比如在集合里左右逐步游动像moveNext,movePrev等等,在一个集合的中间进行添加、更新、删除的功能更是欠奉了,这主要是因为操作效率问题。不可变集合只有对前置操作(prepend operation)才能获得可靠的效率,即对集合首位元素的操作,能得到相当于O(1)的速度,其它操作基本上都是O(n)速度,n是集合的长度,也就是随着集合的长度增加,操作效率会以倍数下降。还有一个原因就是编程时会很不方便,因为大多数程序都会对各种集合进行大量的操作,最终也会导致程序的复杂臃肿,不符合函数式编程要求的精简优雅表达形式。我想可能就是因为以上各种原因,scalaz提供了Zipper typeclass帮助对不可变集合操作的编程。Zipper的定义如下:scalaz/Zipper.scala
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 Some(Zipper.zipper(x.tail, x.head, empty)) ...
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) ...
都是先转换成Stream再生成Zipper的。Zipper本身的构建函数是zipper,在NonEmptyList的Zipper生成中调用过:
trait ZipperFunctions { def zipper[A](ls: Stream[A], a: A, rs: Stream[A]): Zipper[A] = Zipper(ls, a, rs) }
用这些串形结构的构建函数产生Zipper同样很简单:
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
有了串形集合的Zipper构建方法后我们再看看一下Zipper的左右游动函数:
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 this.copy(Stream.Empty, rights.head, rights.tail) * Moves focus to the end of the zipper. def end: Zipper[A] = { val lefts = this.rights.reverse ++ focus #:: this.lefts this.copy(lefts.tail, lefts.head, Stream.empty) * 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 )) 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 )) 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 )) 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 )) 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)
我在上面的程序里在for{...}yield里面逐条添加指令从而示范游标当前焦点和集合元素跟随着的变化。这段程序可以说就是一段行令程序。
回到上面提到的效率和代码质量讨论。我们提过scalaz提供Zipper就是为了使集合操作编程更简明优雅,实际情况是怎样的呢?
举个例子:有一串数字,比如:List(1,4,7,9,5,6,10), 我想找出第一个高点元素,它的左边低,右边高,在我们的例子里是元素9。如果我们尝试用习惯的行令方式用索引去编写这个函数:
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(_)) }
哇!这东西不但极其复杂难懂而且效率低下,重复用find索引导致速度降到O(n * n)。如果用Array会把效率提高到O(n),不过我们希望用immutable方式。那么用函数式编程方式呢?
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 }
用模式匹配(pattern matching)和递归算法(recursion),这段程序好看多了,而且效率也可以提高到O(n)。
但我们再把情况搞得复杂一点:把高点值增高一点(+1)。还是用FP方式编写:
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) }
代码又变得臃肿复杂起来。看来仅仅用FP编程方式还不足够,还需要用一些新的数据结构什么的来帮助。scalaz的Zipper可以在这个场景里派上用场了:
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) }
用Zipper来写程序表达清楚许多。这里用上了Zipper.positions:
/** * 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)。
C语言|数据结构——树的定义、存储与遍历 基本概念 1.有且只有一个称为根的节点; 2.有若干个互不相交的子树,这些子树本身也是一棵树; 3.由节点和边组组成的; 4.每个节点只有一个父节点,可以有无数个子节点(除了根节点)。 |一般树。任意一个子节点个数不受限制,可以是有序树也可以是无序树。 |二叉树。任意一个节点最大度为2,二叉树是有序树,左右节点不能随意互换。 | 一般二叉树 |满二叉树。每一层节点都是满的。 |完全二叉树。除最后一层外,每一层节点都是满的,最后一层节点一定从左向右连续排列。 |森林。n个互不相交的树的集合,可以是互不相连的几个树 一些专业术语:
相关文章
- python的环境变量的设置,安装库的两种方法,pycharm解释器设置字体大小,在DOS下运行python,无法定位动态库「建议收藏」
- 图扑软件 | 数字孪生钢厂人员安全定位
- 【错误记录】BLE 蓝牙搜索失效 ( 关闭了 GPS 定位导致的问题 | 蓝牙串口工具推荐 )
- SQL开发知识:Oracle查询sql语句错误信息的控制和定位处理方式
- 微信小程序判断手机有没有定位的方法详解手机开发
- 保护自己之手机定位信息收集
- 【深入Linux系统:定位光驱的路径】(linux光驱路径)
- 同样是激光定位,这家国内厂商做得比HTC Vive还好?
- 检测Oracle人工智能异常检测新技术开辟异常精准定位(oracle人工生成异常)
- 优点Oracle事务精准定位优势显著(oracle事物的特定)