Map

January 22, 2022

在〈Pattern matching〉看過這個範例:

def doubleIt(lt):
    match lt:
        case []:
            return []      
        case [head, *tail]:
            return [head * 2] + doubleIt(tail)

map 映射

你可能會想把一組資料全部乘 2,那麼可以使用上面的 doubleIt,如果你想將一組資料加 3 呢?將一組資料平方?

def plus3(lt):
    match lt:
        case []:
            return []      
        case [head, *tail]:
            return [head + 3] + plus3(tail)

def pow2(lt):
    match lt:
        case []:
            return []      
        case [head, *tail]:
            return [head ** 2] + pow2(tail)

嗯嗯?流程與 doubleIt 幾乎是一模一樣,除了 head * 2head + 3head ** 2、遞迴函式名稱不同?想對首元素做什麼,若可以傳入函式決定就可以的話,就可以抽取出一個 map 函式,來完成這些任務:

def map(mapper, lt):
    match lt:
        case []:
            return []      
        case [head, *tail]:
            return [mapper(head)] + map(mapper, tail)

lt = [1, 3, 2, 5, 8]
doubled = map(lambda n: n * 2, lt)
plus3 = map(lambda n: n + 3, doubled)
pow2 = map(lambda n: n ** 2, plus3)

實際上,Python 本身就有 map 函式,而且它傳回的會是產生器,差別在哪個,以上的範例,若最後想要的是 pow2,必須先迭代 lt 生成 doubled,這是一個 list,然後迭代 doubled 生成 plus3,這也是一個 list,最後再迭代 plus3,生成最後的 list

不過,若使用 Python 內建的 map

lt = [1, 3, 2, 5, 8]
doubled = map(lambda n: n * 2, lt)
plus3 = map(lambda n: n + 3, doubled)
pow2 = map(lambda n: n ** 2, plus3)

doubled 是個產生器,實際上這時還沒真正進行迭代,plus3pow2 也都是產生器,最後你想要什麼呢?一個 list?那就 list(pow2),這時才會要求 pow2 產生器迭代,然後 pow2 要求 plus3plus3 才開始處理,每處理一個元素乘 2,就交給下一層加 3,然後下一層做平方…

也就是說這整個流程,實際上只會做一次迭代,這也是在〈Immutable〉中談到的,「根據任務的性質,也有不同的方式可以減少運算次數」,Python 的產生器,就是其中一個例子。

實際上,對於映射這種任務,Python 更常使用的是 comprehension 表示式,這部份將一起在〈Filter〉中說明。

Java 的 Stream API 也具有這種惰性求值(lazy evaluation)的特性,每次的 map 操作會傳回 Stream,最後才有個終結操作,看指定使用哪種 Collector,以傳回想要的型態:

var result = List.of(1, 3, 2, 5, 8)
                 .stream()
                 .map(n -> n * 2)
                 .map(n -> n + 3)
                 .map(n -> n * n)
                 .collect(Collectors.toList());

不過,並不是每種語言的標準 API 都會有惰性求值就是了,例如,JavaScript 就沒有,每次的 map 操作,會傳回 Array

const result = [1, 3, 2, 5, 8].map(n => n * 2)
                              .map(n => n + 3)
                              .map(n => n * n);

回到命令式

方才談到了三個語言,都有 map 這類的 API,只是使用上風格不同,為什麼?想將一組數字乘 2、加 3、平方,命令式角度的話,很容易會想到用迴圈:

lt = [1, 3, 2, 5, 8]

doubled = []
for n in lt:
    doubled.append(n * 2)

plus3 = []
for n in lt:
    plus3.append(n + 3)

pow2 = []
for n in lt:
    pow2.append(n ** 2)

命令式中使用迴圈本身是沒什麼問題,就上例來說,也還算容易觀察出類似流程,可以抽取出來:

def map(mapper, lt):
    result = []
    for n in lt:
        result.append(mapper(n))
    return result

不過,〈Immutable〉中談過,許多開發者很容易就出現順便在迴圈裡做個什麼行為的壞習慣,然後整個迴圈中的類似流程,就被埋沒了,變得難以抽取共用流程,從而只能不斷不斷地使用迴圈。

Immutable〉中談過,若無法做 x = x + 1 這類動作,你就只能透過遞迴來做重複性的任務,因為無法做 x = x + 1 的動作,為了便於實作遞迴,你會自然地一次只做一次事,從而令流程不至於複雜,然後,很容易像這篇文件一開始的範例,馬上發現流程的相似性。

最後你就會發現,你想做的就是將一組資料,映射為另一組資料,這是從比較高階的角度,來看待將一組數字乘 2、加 3、平方的需求,現代語言若有 map 這類元素,就是希望你面對一組資料的處理時,可以用這種高階角度來撰寫程式,避免不斷地寫出類似的迴圈,避免出現順便在迴圈裡做個什麼行為的壞習慣。

而且這種對流程的高階抽象,還隱藏了效能增進的可能性,如果你親自寫迴圈來完成這類需求,採用的是外部迭代(External iteration),然而,若將實作細節隱藏在 map 裡,你使用 map 時,怎麼會知道 map 怎麼迭代呢?這是內部迭代(Internal iteration),因為內部迭代行為被隱藏了,也就有許多實現效率的可能性。

Python 的產生器做法,是其中一個例子,Java 的 Stream API,甚至還有機會進行平行化來增進效能:

var result = List.of(1, 3, 2, 5, 8)
                 .parallelstream()
                 .map(n -> n * 2)
                 .map(n -> n + 3)
                 .map(n -> n * n)
                 .collect(Collectors.toList());

面對一組資料,想逐一處理其中元素,成為另一組資料時,若使用的語言中,有 map 之類的 API,可以優先考慮該怎麼運用它們來完成需求,而不是第一時間想到迴圈。

其實 Python 的話,還有 comprehension 的寫法,可以完成 map 的需求,這就下一篇文件再來談吧!

可以 map 的來源並不限於 list,也可能是樹狀結構等其他類型,例如,Java 的 Collection 具有 stream 方法可以建立 Stream,後續可以進行 map 操作,這表示 TreeSet 等結構,也是作為 map 來源,因此 map 可以再抽象化為指定 a -> b 函式,將 f a 轉換為 f bf 代表 list、樹狀等類型),這種再度抽象化後的概念就是 Functor