Scalaz（23）－ 泛函數據結構： Zipper-游標定位

来源:http://www.cnblogs.com/tiger-xc/archive/2016/01/06/5107491.html
-Advertisement-
Play Games

外面沙塵滾滾一直向北去了，意識到年關到了，碼農們都回鄉過年去了，而我卻留在這裡玩弄“拉鏈”。不要想歪了，我說的不是褲襠拉鏈而是scalaz Zipper，一種泛函數據結構游標（cursor）。在函數式編程模式里的集合通常是不可變的（immutable collection），我們會發現在FP編程過....


  外面沙塵滾滾一直向北去了，意識到年關到了，碼農們都回鄉過年去了，而我卻留在這裡玩弄“拉鏈”。不要想歪了，我說的不是褲襠拉鏈而是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)。

 

 

 

 

 

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • javascript類型系統之Math
    [1]屬性 [2]方法 [3]tips
  • 論javascript中的原始值和對象
    不造你有沒有這樣把js數據類型分類，不造你是否知道各種數據類型是怎樣賦值怎樣傳遞的，所有的不造，看了這篇就能懂了，保證小學生即可懂！
  • 基於jQuery滑鼠點擊水波動畫豎直導航代碼
    基於jQuery滑鼠點擊水波動畫豎直導航代碼。這是一款基於jQuery+CSS3實現的帶動畫效果的豎直導航欄特效。效果圖如下：線上預覽源碼下載實現的代碼。html代碼： 網站首頁 關於我們 產品中心 成功案例 ...
  • DOM LEVEL 1 中的那些事兒[下]
    DOM是前端編程中一個非常重要的部分，我們在動態修改頁面的樣式、內容、添加頁面動畫以及為頁面元素綁定事件時，本質都是在操作DOM。DOM並不是JS語言的一個部分，我們通過JAVA、PHP等語言抓取網頁內容時需要對網頁進行解析並拿到我們感興趣的那部分內容，這時其實也是在操作DOM。當然在前端領域，我們...
  • Lind.DDD.Authorization用戶授權介紹
    回到目錄Lind.DDD.Authorization是Lind.DDD框架的組成部分，之所以把它封裝到框架里，原因就是它的通用性，幾乎在任何一個系統中，都少不了用戶授權功能，用戶授權對於任何一個系統來說都是必要的，像管理型的頁面都需要用戶先去登陸，然後拿到憑證，才可以進行訪問，這在MVC和WebAp...
  • Win下，通過Jstack截取Java進程中的堆棧信息
    在Java軟體的使用過程中，有時會莫名的出現奇怪的問題。而這些問題常常無法使用日誌信息定位，這時我們就需要通過查看進程內部線程的堆棧調用關係來分析問題出在哪裡。 舉個例子，當我們在做某個操作時，莫名的會彈出多個警告框，其中有些信息是正常的，有些則不是。對於這些錯誤的警告信息，我們該如何定位是哪...
  • 樹莓派高級GPIO庫，wiringpi2 for python使用筆記（五）i2c讀取測試
    wiringpi2顯然也把i2c驅動帶給了Python，手頭上正巧有一個DS3231的模塊，上邊帶了一個DS3231 RTC（實時時鐘），與一片24C32，兩個晶元均為iic匯流排設備，與樹莓派接線如下： 也就是VCC GND SDA SCL四個腳分別接到樹莓派的1（3.3v）、9（0v）、3（SDA...
  • 第二章 Java框架整合--maven父子模塊
    2.1、maven父子模塊在實際開發中，我們基本都會用maven父子分模塊的方式進行項目的開發。2.2、實際操作2.2.1、手工建立一個ssmm0的文件夾，併在該文件夾中加入一個pom.xml文件，該pom.xml文件內容如下： 1 2 4 5 4.0.0 6 7 com.x...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類