设为首页 加入收藏

TOP

Scalaz(23)- 泛函数据结构: Zipper-游标定位(一)
2017-10-10 12:13:24 】 浏览:9097
Tags:Scalaz 数据结构 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])

它以Stream为基础,A可以是任何类型,无论基础类型或高阶类型。Zipper的结构如上:当前焦点窗口、左边一串数据元素、右边一串,形似拉链,因而命名Zipper。或者这样看会更形象一点:

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
编程开发网
首页 上一页 1 2 3 4 下一页 尾页 1/4/4
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇Scalaz(22)- 泛函编程思维: C.. 下一篇\x 开头编码的数据解码成中文

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }