• 热门专题

Scalaz(23)泛函数据结构: Zipper游标定位

作者:雪川大虫  发布日期:2016-01-08 19:51:06
Tag标签:游标  数据结构  
  •   外面沙尘滚滚一直向北去了,意识到年关到了,码农们都回乡过年去了,而我却留在这里玩弄“拉链”。不要想歪了,我说的不是裤裆拉链而是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 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>))
     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)

    我在上面的程序里在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)。

About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规