Filter

在〈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）的特性，當然也可以結合 filter、map 操作，每次都傳回 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 就沒有，每次的 filter、map 操作，會傳回 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〉貼過來的啦！重點其實是，面對一組資料，請想想看你想處理的事情，可否分解為一次只做一件事，然後以高階抽象來看待，試著使用語言提供的 filter、map 等特性，這種概念，是從函數式典範來的！

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]

當然也可以併用，完成 filter、map 的效果：

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

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

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

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