Filter

January 22, 2022

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

def greaterThanFive(lt):
    match lt:
        case []:
            return [] 
        case [head, *tail]:
            if head > 5:
                return [head] + greaterThanFive(tail) 
            else:
                return greaterThanFive(tail) 

filter 過濾

你可能會把一組資料大於 5 的元素留下,那麼可以使用上面的 greaterThanFive,如果想留下小於 5 的呢?

def lessThanFive(lt):
    match lt:
        case []:
            return [] 
        case [head, *tail]:
            if head < 5:
                return [head] + lessThanFive(tail) 
            else:
                return lessThanFive(tail) 

嗯嗯?流程與 greaterThanFive 幾乎是一模一樣,嗯…你知道接下來我想講的,跟〈Map〉中談的類似了,也就是若可以可以傳入函式來決定過濾條件的話,就可以抽取出一個 filter 函式,來完成這些任務:

def filter(predicate, lt):
    match lt:
        case []:
            return [] 
        case [head, *tail]:
            if predicate(head):
                return [head] + filter(predicate, tail) 
            else:
                return filter(predicate, tail) 

lt = [1, 3, 2, 5, 8]
print(filter(lambda n: n > 5, lt)) # [8]
print(filter(lambda n: n < 5, lt)) # [1, 3, 2]

實際上,Python 本身就有 filter 函式,它傳回的會是產生器,跟〈Map〉中談過的一樣,Python 內建的 filter 函式傳回產生器,具有惰性求值的特性:

lt = [1, 3, 2, 5, 8]
print(list(filter(lambda n: n > 5, lt))) # [8]
print(list(filter(lambda n: n < 5, lt))) # [1, 3, 2]

當然,它也可以搭配 map

lt = [1, 3, 2, 5, 8]
greaterThan5 = filter(lambda n: n > 5, lt)
print(list(map(lambda n: n + 5, greaterThan5)))   # [13]

這整個流程,實際上只會做一次迭代,而且 map 最後實際上只處理一個元素,這也是在〈Immutable〉中談到的,「根據任務的性質,也有不同的方式可以減少運算次數」。

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

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

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

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

回到命令式

Map〉中談過的,命令式中使用迴圈本身是沒什麼問題,如果一次只做一件事,流程夠單純,想抽取出 filter 也不是什麼大問題:

def filter(predicate, lt):
    result = []
    for n in lt:
        if predicate(n):
            result.append(n)
    return result

lt = [1, 3, 2, 5, 8]
print(filter(lambda n: n > 5, lt))
print(filter(lambda n: n < 5, lt))

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

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

最後你就會發現,你想做的就是將一組資料過濾,留下符合條件的一組資料,這是從比較高階的角度,現代語言若有 filter 這類元素,就是希望你面對一組資料的處理時,可以用這種高階角度來撰寫程式,避免不斷地寫出類似的迴圈,避免出現順便在迴圈裡做個什麼行為的壞習慣,而這種對流程的高階抽象,也就隱藏了效能增進的可能性。

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

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

好吧!以上有些文字,是從〈Map〉貼過來的啦!重點其實是,面對一組資料,請想想看你想處理的事情,可否分解為一次只做一件事,然後以高階抽象來看待,試著使用語言提供的 filtermap 等特性,這種概念,是從函數式典範來的!

comprehension 表示

Python 具有 comprehension 語法,想做 map 時,其實可以寫:

lt = [1, 3, 2, 5, 8]
doubled = [n * 2 for n in lt]

以上會產生 list,若想建立產生器,可以使用 ()

lt = [1, 3, 2, 5, 8]
doubled = (n * 2 for n in lt)

嗯?這不是使用迴圈了嗎?不!comprehension 語法,其實是模仿數學上的集合表示,以上的寫法,其實相當於集合表示:

A = {1, 3, 2, 5, 8}
B = {n * 2| n ∈ A}

函數式其實源於 lambda calculus,而 lambda calculus 是數學,純函數式語言裡,會有 comprehension 語法,就是模仿數學上的集合表示,Python 的 comprehension 語法,基本上借鏡函數式的 comprehension 語法。

Python 的 comprehension 語法,也可以達成 filter 的效果:

lt = [1, 3, 2, 5, 8]
greaterThan5 = [n for n in lt if n > 5]

當然也可以併用,完成 filtermap 的效果:

lt = [1, 3, 2, 5, 8]
r = [n * 2 for n in lt if n > 5]

在許多情況下,comprehension 語法比較方便,相對而言,filtermap 在 Python 中就少用了一些,但不是沒有,視需求而定罷了。

當然,不是每個語言都會 comprehension 語法,重點在於,面對一組資料的處理時,儘量用高階、數學的角度來撰寫程式。

可以 filter 的來源並不限於 list,也可能是樹狀結構等其他類型,例如,Java 的 Collection 具有 stream 方法可以建立 Stream,後續可以進行 map 操作,這表示 TreeSet 等結構,也是作為 filter 來源,因此 filter 可以再抽象化為指定 a -> Bool 函式,將 f a 過濾為 f af 代表 list、樹狀等類型),這種再度抽象化後的概念,在 Haskell 可以使用型態類別來規範,有些 Haskell 套件確實也定義了 Filterable 型態類別。