程式語言導論/顯著高階函式
一些高階函式是非常常見的程式設計習慣用法。三個最著名的例子是map，reduce和filter。本章中的第一個示例是 map 函式的實現。它接受兩個引數，一個數據結構 *t* 和一個對映函式 *f*，並返回一個新的資料結構，其中每個元素都經過 *f* 轉換。通常 map 在列表上工作。Map 不會向輸入列表新增或刪除元素；因此，輸入和輸出列表始終具有相同的尺寸。
Reduce 用於將資料結構轉換為單個值，方法是連續應用二元運算子。在 SML 中，reduce 有兩種形式：foldr 和 foldl。第一個函式 foldr 接受一個型別為 'a * 'b -> 'b 的二元函式、一個型別為 'b 的種子以及一個型別為 'a list 的列表，並返回一個稱為 *歸約* 的型別為 'b 的元素。函式 foldr 從列表的右側開始向左側應用二元運算子。下面給出一些示例
- foldr (op +) 0 [1,2,3,4];
val it = 10 : int
- foldr (op * ) 1 [1,2,3,4];
val it = 24 : int
- foldr (op ^) "" ["abc","def","ghi"];
val it = "abcdefghi" : string
- foldr (op ::) [5] [1,2,3,4];
val it = [1,2,3,4,5] : int list
- foldr (fn(a, b) => (a + b)/2.0) 0.0 [1.0, 2.0, 3.0, 4.0];
val it = 1.625 : real
函式 foldl 與 foldr 非常相似；但是，它從列表的左側開始向右側評估二元運算。下面給出了一些使用示例
- foldl (op +) 0 [1,2,3,4];
val it = 10 : int
- foldl (op * ) 1 [1,2,3,4];
val it = 24 : int
- foldl (op ^) "" ["abc", "def", "ghi"];
val it = "ghidefabc" : string
- foldl (op ::) [5] [1,2,3,4];
val it = [4,3,2,1,5] : int list
- foldl (fn(a, b) => (a + b)/2.0) 0.0 [1.0, 2.0, 3.0, 4.0];
val it = 3.0625 : real
有時，當給定相同的運算元時，foldl 和 foldr 會產生相同的結果。此結果取決於這些操作使用的二元運算子。如果運算子既是關聯的又是可交換的，那麼這些函式將對相同的輸入產生相同的結果。否則，它們的結果可能不同。
這三個函式 map、foldr 和 foldl 是非常有用的並行骨架。例如，map 可以完全並行化，前提是處理器數量與輸入列表的大小成正比，就像在PRAM 模型中一樣。換句話說，在這個場景中，此函式將在 *O(f)*漸近 時間內執行，其中 *O(f)* 是應用對映函式的複雜度。如果處理器數量非常多，即與輸入列表的大小成正比，那麼 foldr 和 foldl 的複雜度都可以降低到輸入列表大小的對數因子。這一觀察結果促使了幾個高效能框架的設計，例如map reduce 和radoop。
我們的最後一個高階函式是 filter。此函式具有型別 ('a -> bool) -> 'a list -> 'a list。此函式接受兩個引數：一個謂詞，即一個對給定輸入返回真或假的函式，以及一個列表。Filter 返回一個新列表，該列表僅包含導致謂詞為真的那些元素。下面可以檢視 SML 中的一些示例
- List.filter (fn s => hd (explode s) = #"p") ["grape", "pineaple", "pumpkin", "strawberry"];
val it = ["pineaple","pumpkin"] : string list
- List.filter (fn x => x > 2) [1,2,3,4,5];
val it = [3,4,5] : int list