Strictness 和 Laziness (2)

LazyList 細部處理拆解

講進階用法之前,先來看一下 LazyList 是怎麼處理 LazyList(1, 2, 3, 4).map(_ + 10).filter(_ % 2 == 0).toList 的,

LazyList(1, 2, 3, 4).map(_ + 10).filter(_ % 2 == 0).toList

// 將 map 用於第 1 個元素
cons(11, LazyList(2, 3, 4).map(_ + 10)).filter(_ % 2 == 0).toList 

// 將 filter 用於第 1 個元素
LazyList(2, 3, 4).map(_ + 10).filter(_ % 2 == 0).toList 

// 將 map 用於第 2 個元素
cons(12, LazyList(3, 4).map(_ + 10)).filter(_ % 2 == 0).toList 

// 將 filter 用於第 2 個元素,符合條件成為結果的第一個元素
12 :: LazyList(3, 4).map(_ + 10).filter(_ % 2 == 0).toList 


12 :: cons(13, LazyList(4).map(_ + 10)).filter(_ % 2 == 0).toList

12 :: LazyList(4).map(_ + 10).filter(_ % 2 == 0).toList 

12 :: cons(14, LazyList().map(_ + 10)).filter(_ % 2 == 0).toList

// 將 filter 用於第 4 個元素,符合條件成為結果的第二個元素
12 :: 14 :: LazyList().map(_ + 10).filter(_ % 2 == 0).toList 

// map 和 filter 沒有更多元素需要處理,空的 LazyList 轉成空的 List 
12 :: 14 :: List()

// 最後結果
List(12, 14)

Strictness 和 Laziness (1) 一開始用 List 處理的方式很不同,LazyList 在轉換時是漸近式的,也不會產生暫時用的 List,它只對目前需要處理的元素做轉換,這也代表了我們可以操作大量的數據而不用擔心記憶體爆掉,也不用擔心是否對 LazyList 做了太多操作。

從 Evaluation 中分離程式的關注點

functional programming 中一個重要的主題是關注點分離,跟設計模式 SOLID 原則或 Clean Articuture 中提到的概念類似,把框架抽象出來,在讓實作的人決定核心業務邏輯怎麼運行,

我們在前面寫到的許多方法都是透過 high-order function 來讓調用的人決定執行邏輯,而我們則把它們變成 pure function,讓它能優美的且能隨意組合的方式做流式處理,

而有 Laziness 的 List,則是更進一步將表達式的執行分離成部份執行,所以我們可以選擇描述大型的表達式,舉例來說我們在 LazyList 中新增 exists function,檢查 LazyList 中是否存在某值,

  def exists(p: A => Boolean): Boolean = this match
    case Cons(h, t) => p(h()) || t().exists(p)
    case _ => false

一樣的,此邏輯可以抽象成 foldRight function,跟 Scala 下的 Functional 資料結構 (2) 的 List 類似,但這次的程式支持 laziness,表示 f 的第二個參數可能不會執行到,

  def foldRight[B](z: => B)(f: (A, => B) => B): B = 
    this match
      case Cons(h, t) => f(h(), t().foldRight(z)(f)) 
      case _ => z

然後我們可以用 foldRight 來改寫 exists 方法,

  def exists(p: A => Boolean): Boolean =
    foldRight(false)((a, b) => p(a) || b)

在 foldRight 這個基礎上我們也用它來設計 append function。

  def append[A2 >: A](that: => LazyList[A2]): LazyList[A2] =
    foldRight(that)((a, acc) => cons(a, acc))

Exercise D11-1

用 foldRight 來實作 takeWhilefilter

def takeWhileViaFoldRight(p: A => Boolean): LazyList[A]
def filter(f: A => Boolean): LazyList[A]

Exercise D11-2

用 foldRight 來實作 mapflatMap

def map[B](f: A => B): LazyList[B]
def flatMap[B](f: A => LazyList[B]): LazyList[B]

無限長的 LazyList 和核心迭代

因為 LazyList 是漸近式增長,某種意義來說它能用來寫無限長的 List,

scala> val ones: LazyList[Int] = LazyList.cons(1, ones)

scala> ones.take(3).toList
val res0: List[Int] = List(1, 1, 1)

scala> ones.exists(_ % 2 != 0)
val res1: Boolean = true

scala> ones.map(_ + 1).exists(_ % 2 == 0)
val res2: Boolean = true

ones 的結構如下圖,

但要小心寫那種沒有終止條件的操作,例如 ones.takeWhile(_ == 1),所以測試很重要!

總結

這 2 天主要講了什麼是 strict 和 non-strict,Scala 的 lazy 關鍵字和 call by name 能讓 List 變成 LazyList(non-strict),我們只在需要的時候才會 evaluate (執行) 必要元素,最後則介紹 LazyList 怎麼運作以及在使用上要注意的地方。


Exercise answer

tshine73
tshine73
文章: 50

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *