iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 4
0

Kotlin collections: List, Map and Set

上一篇的解答:答案是不一定,如果 Money 這個 class 的其中一個變數是 var ,或是他也用到了另外一個 class ,就會是 mutable 的(可以被修改)

class Account(val id: Int, val money: Money)
// amount 可能會被修改
class Money(var amount: Int, val currency: String)

接下來進入這這一篇應該是最多人會接觸到的部分,很多人是由 mapfilter 這些 operator 認識 functional programming 的。那麼,只要使用這些 operator 就代表我們真的在寫 functional programming 了嗎?還是看個例子比較快,先來看看 map 的用法吧:

Map

val numbers = listOf(1, 2, 3)
// numbers = [1, 2, 3]
val doubleNumbers = numbers.map { x -> x * 2}
// doubleNumbers = [2, 4, 6]

map 所做的事情就是將 list 裡的所有元素都拿出來計算,並建立出一個新的 List 來存放他。以下分幾個層面來探討:

為什麼叫做 map ?

對一個 Java 開法者來說,map 是一個非常熟悉的資料結構,常常用來解決空間換取時間的問題。以抽象一點的層面上來看,他的概念是一個 key 對應到一個 value ,而這個一對一的對應關係就是 map 。現在再回頭來看這個 operator ,其實他的概念也是一對一,只是他的對應關係變成了, 一組集合對應到了另一組集合。下面舉了其中幾種可能性

// Int 的集合 -> String 的集合
val stringNumbers = numbers.map { x -> x.toString() }
// Int 的集合 -> float 的集合
val divideNumbers = numbers.map { x -> x / 3f }
// Int 的集合 -> Point 的集合
val points = numbers.map { x -> Point(x, x + 1) }

map 的實作

既然我們都要學 functional programming 了,那實作也得要好好看懂才是:

public inline fun <T, R> Iterable<T>.map(transform: (T) -> R): List<R> {
    return mapTo(ArrayList<R>(collectionSizeOrDefault(10)), transform)
}

public inline fun <T, R, C : MutableCollection<in R>> Iterable<T>.mapTo(destination: C, transform: (T) -> R): C {
    for (item in this)
        destination.add(transform(item))
    return destination
}

恩....好像有點可怕,但是別擔心,我們來做點小小的簡化

fun <T, R> List<T>.map(transform: (T) -> R): List<R> {
    val destination = ArrayList<R>()        //1
    for (item in this)
				destination.add(transform(item))    //2
		return destination
}

看起來是不是簡單多了呢?你會發現很多特性在前面就有介紹過了: extension function、higher order function 以及泛型。這個 map 在做的事情就是:

(1) 建立一個新的 List - destination,並且

(2) 拿出來原來的 List 裡的每一個 item ,並拿來當作參數執給 transform 這個 function 去執行 ,再把得到的結果加到 destination 裡。

簡化過後的版本跟原來的版本比較起來,不一樣的地方有 Extension 的對象 Iterable 換成了 List,還有為了重用而抽取出來的函式 mapTocollectionSizeOrDefault。那Iterable 是什麼呢?如果對 Java 夠熟的話就會知道他是很多“集合”類別的共同介面,像是 List、ArrayList、Set、Stack 等等。

這些類別都繼承了 Iterable ,只需要實作一次就能支援這麼多類別,超棒的不是嗎?但是不幸的是,這個優點也同時是他的缺點,再來看看以下這段程式:

val list: List<Int> = listOf(1, 2, 3)
val listMapping: List<Int> = list.map { x -> x + 1 }

val set: Set<Int> = setOf(1,2, 3)
val setMapping: List<Int> = set.map { x -> x + 2 }

發現了嗎? Set 在經過 map 過後竟然變成了 List !一般來說,我們會期望型別是不會被改變的,要嘛就是從頭到尾都是 List ,不然就是從頭到尾都是 Set ,當然我相信 Kotlin 這樣設計的背後是有他的理由的,但是這樣隱性(implicit) 的轉換應該會是很多人都不會預期到的。

接下來看看 Map 的 map 吧(好繞口)

val map: Map<String, Int> = mapOf("key" to 4)
// 1
val mapMapping: List<String> = map.map { (key, value) -> key + value }
// 2
val mapMappingValue: Map<String, Int> = map.mapValues { (key, value) -> value *2 }

可以看到

  1. 即使是 Map ,經過 map operator 後還是轉換型態成 List 了。
  2. 如果要的資料型別還是 Map 的話,就得要使用 mapValue 這個 operator (或是 mapKeys 也可以)。

至於具體實作的話就請各位自行研究了,懂了 Iterable 的實作之後不會太難才是。

Filter

一樣先舉個例子

val list: List<Int> = listOf(1, 2, 3)
// list = [1, 2, 3]
val oddList: List<Int> = list.filter { x -> x % 2 == 1 }
// list = [1, 3]
val evenList: List<Int> = list.filter { x -> x % 2 == 0 }
// list = [2]

從上面的例子就能很明顯的得知 filter 的用法,他能過濾不需要的 item ,只要在 lambda 裡寫出判斷的條件即可,條件為 true 的話,就會將該 item 留下來。至於內部實作長什麼樣子呢?有了之前的經驗,應該不難猜出這也是 extension function 跟 higher order function。話不多說,直接來看看這是怎麼看實作出來的吧!

public inline fun <T> Iterable<T>.filter(predicate: (T) -> Boolean): List<T> {
    return filterTo(ArrayList<T>(), predicate)
}

public inline fun <T, C : MutableCollection<in T>> Iterable<T>.filterTo(destination: C, predicate: (T) -> Boolean): C {
    for (element in this) if (predicate(element)) destination.add(element)
    return destination
}

跟 map 的實作非常像,對吧?最大的差異是帶進去的 lambda function type 從 (T) → R 變成了 (T) → Boolean,還有該 lambda 執行的位置:map 是執行在每個 item 上 ,filter 則是執行在 if 的判斷式裡。很一致的, filter 也直接實作在 Iterable 這個界面上,回傳的型別也是 List,上述的隱性型別轉換在這裡也發生了!那 Map 的 filter 又是長什麼樣子的呢?

val map: Map<String, Int> = mapOf("key" to 4)
// map.map 回傳的型別是 List<T>
val mapFilter: Map<String, Int> = map.filter { (key, value) -> value > 2 }
val mapFilterKey: Map<String, Int> = map.filterKeys { key -> key.length > 2 }
val mapFilterValue: Map<String, Int> = map.filterValues { value -> value > 2 }

驚呆了!回傳的型別不是 List 而是 Map!照理說應該要跟 map 這個 operator 的規則一樣不是比較好嗎?為什麼要改來改去的呢?

Function chaining

這在 function programming 中是一個非常常見的風格,簡單的來說,就是把不同的 operator 串在一起,寫的程式碼會少很多,閱讀起來也會相對順暢!

val set: Set<Int> = setOf(1, 2, 3, 4)
val setMapping: Set<Int> = set.map { x -> x + 2 }
    .filter { x -> x % 2 == 0 }
    .toSet()

在這個例子中我們把 map, filter, toSet 串在一起了,不用再每個都要有相對應的變數來儲存他。但是要注意!在每一個 operator 的計算中,都會產生一個新的 List ,不會因為沒有儲存成變數就不存在!

好了,讓我們先忘掉本篇所講的 map 以及 filter 的回傳型別,假裝你不知道他會回傳 List,再仔細看看上面這個範例,好像哪裏怪怪的,對吧!為什麼一個 Set 經由一連串操作過後還要再轉回成 Set ?難道不能每個步驟的型別都回傳 Set 嗎?

再談 composition

還記得 functional programming 其中的一個重要的元素 - composition 嗎?function chaining 看起來是不是也有點像是 composition 呢?在先前的範例中我們計算的是 Int, String 這種簡單的型別,在這裏只是換成了 Set, List, Map,如果是以這種角度來看的話,他們不都是做一樣的事嗎?

val addOne = {x: Int -> x + 1}
val divideTwo = {x: Int -> x/2}

// 還記得 pipe 嗎?忘了的話回去看第二篇吧!
val primitiveApproach = (addOne pipe divideTwo)(5)

val listChaining = listOf(5, 6, 7)
    .map(addOne)
    .map(divideTwo)

val listChaining2 = listOf(5, 6, 7)
    .map(addOne pipe divideTwo)

你可以把第二篇學的內容想像成是水平的 composition,連續兩個 map 則是垂直的 composition。有趣的事情來了,listChaining 跟 listChaining2 這兩種寫法是等價的嗎?看起來是等價的沒錯吧?然而你要怎證明他們是等價的呢?很有趣對吧!好吧,這些知識需要靠後面會介紹到 Category theory ,後面就會知道答案的。

還記得本篇一開始的問題嗎?使用 operator 是不是等於在寫 functional programming 呢?現在有更清楚的答案了嗎?如果沒有,在下一篇的 partial function 與下下一篇的 side effect 你將可以獲得更完整的答案。

小結

又到了實作時間了,本篇有提到說, Map 這個資料型別經由 map 這個 operator 之後,型別變成了 List !現在想請讀者實作看看型別維持原樣的版本,如下:

val sample = mapOf(1 to "1", 2 to "2", 3 to "3")
val result: Map<Int, String> = sample.fmap { str -> str + "hello" }
println(result)        // {1=1hello, 2=2hello, 3=3hello}

請讀者實作看看這個 fmap 。另外提一下,Kotlin 著名的 functional programming library - Arrow,其實也有這種實作,回傳的型別跟原來的型別一致。以下附上連結:https://arrow-kt.io/docs/arrow/core/mapk/

最後的最後,Kotlin 鐵人陣中的團長剛好就是寫 Collection 的主題。想要了解其他延伸的主題,可以去多看看他的文章喔~
文章連結:https://ithelp.ithome.com.tw/users/20107229/ironman/3244


上一篇
Pure function and immutability
下一篇
Partial function and total function
系列文
Functional Programming in Kotlin30

尚未有邦友留言

立即登入留言