深入探討 List Module 所提供的 Function Part I (A ~ F)

F# 的 List module 提供眾多 list 常用的 Higher Order Function，要能發揮 FP 的威力，首先必須能活用 List module 所提供的眾多 function。

本文先探討英文字母 A ~ F 開頭的 function。

Version

macOS High Sierra 10.13.3

.NET Core SDK 2.1.101

JetBrains Rider 2017.3.1

F# 4.1

List.allPairs

將兩個 list 的 element 取 cartesian product 為 tuple，回傳新的 list

list1 : 'T1 list -> list2 : 'T2 list -> ('T1 * 'T2) list

[ 1 .. 3 ]
|> List.allPairs [ 4 .. 6 ]
|> printf "%A"
// [(4, 1); (4, 2); (4, 3); (5, 1); (5, 2); (5, 3); (6, 1); (6, 2); (6, 3)]

兩個 list 可以不同型別，反正最後會以 tuple 形式呈現。

List.append

傳入兩個 list，第 2 個 list 會 append 到第 1 個 list 之後，相當於 list1@list2

list1 : 'T list -> list2 : 'T list -> 'T list

[ 1 .. 3 ]
|> List.append [ 4 .. 6]
|> printf "%A"
// [4; 5; 6; 1; 2; 3]

List.average

計算 list 中所有 element 的平均值

list : 'T list -> T

[ 1.0 .. 10.0 ]
|> List.average
|> printf "%f"
// 5.500000

List.averageBy

將 list 所有 element 先經過 project funtion 計算後，再取平均值

project : ('T -> 'U) -> list : 'T list -> 'U

[ 1 .. 3 ]
|> List.averageBy (fun elem -> float elem)
|> printf "%f"

[ 1..3 ] 無法透過 List.average() 取平均值，先透過 List.averageBy() 轉成 float，再取平均值。

[ 1.0 .. 3.0 ]
|> List.averageBy (fun elem -> elem * elem)
|> printf "%f"
// 4.666667

先將 [1.0; 2.0; 3.0] project 成 [1.0; 4.0; 9.0] 之後，再取平均值。

List.choose

將 list 經過 chooser function 塞選過，傳回 option 型別的 list，其中 chooser function 必須回傳 option

chooser : ('T -> 'U option) -> list : 'T list -> 'U list

[ 1 .. 10]
|> List.filter (fun elem -> elem % 2 = 0)
|> List.map (fun elem -> elem + 1)
|> printf "%A"
// [3; 5; 7; 9; 11]

先找出偶數，在每個 element + 1。

傳統須先使用 List.filter() 找出 偶數 ，在用 List.map() 計算 +1 。

let chooser elem = 
    match elem % 2 with
    | 0 -> Some (elem + 1)
    | _ -> None

[ 1 .. 10]
|> List.choose chooser
|> printf "%A"
// [3; 5; 7; 9; 11]

若使用 List.choose() ，則可在 chooser function 使用 Pattern Matching：

• 在 pattern 與 when 完成 List.filter() 該做的事情
• 在 -> 之後完成 List.map() 該做的事情

也就是 List.choose() = List.filter() + List.map() 。

List.chunkBySize

將 list 根據 size 切成小 list，並包在一個 list 內

chunkSize : int -> list : 'T list -> 'T list list

[ 1 .. 10]
|> List.chunkBySize 3
|> printf "%A"
// [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]; [10]]

注意 List.chunkBySize() 的回傳型態為 'T list list ，表示回傳為 list，其 element 型態為 'T list 。

List.collect

將 list 所有 element 經過 mapping function 轉換，其中 mapping function 會回傳新的 list，最後再將所有 list 攤平成新的 list

mapping : ('T -> 'U list) -> list : 'T list -> 'U list

let mapping elem = [
    for i in 1 .. 3 -> elem * i
]     
    
[ 1 .. 3 ]
|> List.collect mapping
|> printf "%A"
// [1; 2; 3; 2; 4; 6; 3; 6; 9]

mapping() 會為每個 element 產生新的 list，最後再打平成單一 list。

Q : List.collect() 與 List.map() 有何差異？

相同

• 都需使用 mapping function

相異

• List.map() 的 mapping function 傳回 value；但 List.collect() 的 mapping function 傳回新 list
• List.map() 產生的 list ，其 element 個數與原本 list 一樣大；但 List.collect() 產生的 list，其 element 個數大於等於原本 list

List.compareWith

自行定義 comparer function 比較兩個 list

comparer : ('T -> 'T -> int) -> list1 : 'T list -> list2 : 'T list -> int

let list1 = [ 4 .. 6 ]
let list2 = [ 1 .. 3 ]

let comparer elem1 elem2 = elem1 - elem2
    
let compareList list1 list2 =
    match (List.compareWith comparer list1 list2) with 
    | x when x > 0 -> printfn "list1 is larget than list2"
    | x when x < 0 -> printfn "list2 is larger than list1"
    | _            -> printfn "list1 and list2 are equal"    
    
compareList list1 list2
// list1 is larger than list2

comparer() 定義 element 間的比較方式：

• 若 elem1 大於 elem2 ，則傳回 正數
• 若 elem1 等於 elem2 ，則傳回 0
• 若 elem1 小於 elem2 ，則傳回 負數

若簡單的比較，可使用數學的 兩數相減 即可

List.compareWith() 將回傳第一個 comparer function 所傳回的 非零之數 ，可使用 Pattern Matching 對回傳值做判斷。

List.concat

將 n 個 list 合併為 1 個 list

lists : seq<'T list> -> 'T list

let list1 = [ 1 .. 3 ]
let list2 = [ 4 .. 6 ]
let list3 = [ 7 .. 9 ]

let myList = List.concat [list1; list2; list3]

myList
|> printf "%A"
// [1; 2; 3; 4; 5; 6; 7; 8; 9]

List.concat() 可合併 n 個 list，但必須將 n 個 list 包在同一個 list 傳入。

Q： List.append() 與 List.map() 有何差異？

• List.append() 只能合併 2 個 list
• List.concat() 能合併 n 個 list

List.contains

判斷 list 的 element 是否包含某一 value

value : 'T -> source : 'T list -> bool

[ 1 .. 3 ]
|> List.contains 4
|> printfn "%b"
// false

List.countBy

將 list 根據 projection function 分組後，各自計算分組後 element 個數，類似 SQL 的 GROUP BY + count(*)

projection : ('T -> 'Key) -> list : 'T list -> ('Key * int) list

[ 1 .. 100 ]
|> List.countBy (fun elem -> elem % 3)
|> printf "%A"
// [(1, 34); (2, 33); (0, 33)]

將 [ 1 .. 100 ] % 3 分成三組，餘數為 1 有 34 個，餘數為 2 有 33 個，餘數為 0 有 33 個。

List.distinct

將重複的 element 去除，回傳新 list

list : 'T list -> 'T list

[ 1 ; 2; 2; 3]
|> List.distinct
|> printf "%A"
// [1; 2; 3]

List.distinctBy

將 list 所有 element 經過 projection function 產生新 key 後，將重複 key 的去除，回傳新 list

[ 1 .. 100 ]
|> List.distinctBy (fun elem -> elem % 3)
|> printf "%A"
// [1; 2; 3]

經過 projection function fun elem -> elem % 3 之後的 key 為 [ 0; 1; 2; 0; 1; 2 …] ，其不重複的 key 為 [ 0; 1; 2 ] ，但其對應的 element 為 [ 1; 2; 3] 。

Q： List.distinctBy() 與 List.map() 後再 List.distinct() 有什麼不同？

[ 1 .. 100]
|> List.map (fun elem -> elem % 3)
|> List.distinct
|> printf "%A"
// [1; 2; 0]

經過 mapping function fun elem -> elem % 3 之後的 element 為 [ 0; 1; 2; 0; 1; 2 …] ，其不重複的 element 為 [ 0; 1; 2 ] 。

• Project function 是產生新的 key；mapping function 是產生新的 element
• List.distinctBy() 是排除重複的 key； List.map() + List.distinct() 是排除重複的 element

List.empty

由泛型傳回指定 element 型別的 empty list

empty<'T> : 'T list

List.empty<int>
|> printf "%A"
// []

Q : List.Empty 與 List.empty 有何差異？

type myListType = int list

myListType.Empty
|> printf "%A"
// []

相同

• 均回傳 empty list

相異

• List.Empty 為 List type 的 static method； List.empty() 定義在 List module
• List.Empty 須先定義 type； List.empty() 可由泛型直接指定 element type

List.exactlyOne

從 list 回傳單一 value

list : 'T list -> 'T

[ 1 ]
|> List.exactlyOne
|> printf "%A"
// 1

若 list 的 Length 不為 1 ，將拋出 System.ArgumentException : The input sequence contains more than one element.

List.except

從 list 中排出另一個 list 中的 element，並回傳新的 list

seq<'T> -> list : 'T list -> 'T list

[ 1 .. 10 ]
|> List.except [ 1 .. 2 ]
|> printf "%A"
// [3; 4; 5; 6; 7; 8; 9; 10]

List.exists

判斷符合 predicate function 條件的 element 是否存在

predicate : ('T -> bool) -> list : 'T list -> bool

[ 1 .. 10 ]
|> List.exists (fun elem -> elem = 2)
|> printf "%A"
// true

List.exists2

判斷兩個 list 是否相等，須自行提供 predicate function 為判斷的依據

predicate : ('T1 -> 'T2 -> bool) -> list1 : 'T1 list -> list2 : 'T2 list -> bool

let list1 = [ 1 .. 10 ]
let list2 = [ 11 .. 20 ]
let predicate elem1 elem2 = elem1 = elem2 
    
list1
|> List.exists2 predicate list2
|> printf "%b"
// false

若 list1 與 list2 的 Length 不同，會拋出 System.ArgumentException : The lists had different lengths.

List.filter

過濾出符合 predicate function 的 list

predicate : ('T -> bool) -> list : 'T list -> 'T list

[ 1 .. 10 ]
|> List.filter (fun elem -> elem % 2 = 0)
|> printf "%A"
// [2; 4; 6; 8; 10]

List.find

找出符合 predicate function 條件的第一個 element

predicate : ('T -> bool) -> list : 'T list -> 'T

[ 1 .. 10 ]
|> List.find (fun elem -> elem % 2 = 0)
|> printf "%A"
// 2

若找不到 element，會拋出 KeyNotFoundException : An index satisfying the predicate was not found in the collection.

List.findBack

從 list 的尾巴開始找出符合 predicate function 條件的第一個 element

predicate : ('T -> bool) -> list : 'T list -> 'T

[ 1 .. 10 ]
|> List.findBack (fun elem -> elem % 2 = 0)
|> printf "%A"
// 10

List.findIndex

找出符合 predicate function 條件的第一 element 的 index

predicate : ('T -> bool) -> list : 'T list -> int

[ 1 .. 10 ]
|> List.findIndex (fun elem -> elem % 2 = 0)
|> printf "%A"
// 1

List.findIndexBack

從 list 的尾巴開始找出符合 predicate function 條件的第一 element 的 index

predicate : ('T -> bool) -> list : 'T list -> int

[ 1 .. 10 ]
|> List.findIndexBack (fun elem -> elem % 2 = 0)
|> printf "%A"
// 9

List.fold

List.reduce() 的進階版，將每個 element 的值經過 folder function 加以累加

folder : ('State -> 'T -> 'State) -> state : 'State -> list : 'T list -> 'State

[ 
    ("Cats", 4)
    ("Dogs", 5)
    ("Mice", 3)
    ("Elephants", 2) 
]
|> List.fold (fun acc (_, number) -> acc + number) 0 
|> printf "%d"
// 14

Q : List.fold() 與 List.reduce() 有何差異？

[ 4; 5; 3; 2 ]
|> List.reduce (fun acc elem -> acc + elem)
|> printf "%d"
// 14

相同

• 都是 累加

相異

• List.fold() 可以設定初始值； List.reduce() 不能設定初始值
• List.fold() 可以不同型別，如 (string * int) list -> int； List.reduce() 從頭到尾必須相同型別，如 int lint -> int

List.folder2

將兩個 list 透過 folder function 加以累加

folder : ('State -> 'T1 -> 'T2 -> 'State) -> state : 'State -> list1 : 'T list -> list2 : 'T list -> 'State

let list1 = [ 
    ("Cats", 1)
    ("Dogs", 2)
    ("Mice", 3)
    ("Elephants", 4) 
] 

let list2 = [ 
    ("Cats", 4)
    ("Dogs", 5)
    ("Mice", 3)
    ("Elephants", 2) 
]

let folder acc (_, number1) (_, number2) = 
    acc + number1 + number2

list1
|> List.fold2 folder 0 list2 
|> printf "%d"
// 24

List.foldBack

List.reduce() 的進階版，將每個 element 的值從尾部經過 folder function 加以累加

folder : ('T -> 'State -> State) -> list : 'T list -> state : 'State -> 'State

let list1 = [ 1 .. 5 ]

List.fold (fun acc elem -> elem::acc) [] list1
|> printfn "%A"

List.foldBack (fun elem acc -> elem::acc) list1 []
|> printfn "%A"

// [5; 4; 3; 2; 1]
// [1; 2; 3; 4; 5]

數值累加，從頭加到尾，或尾加到頭都一樣，有有些運算，不同方向累加結果會不一樣，此時就必須使用 List.foldBack() 了。

注意 signature 也不太一樣。

List.foldBack2

將兩個 list 透過 folder function 從尾部加以累加

folder : ('T1 -> 'T2 -> 'State -> 'State) -> list1 : 'T1 list -> list2 : 'T2 list -> state : 'State -> 'State

let list1 = [ 1 .. 5 ]
let list2 = [ 1 .. 5 ]

List.fold2 (fun acc elem1 elem2 -> elem1::elem2::acc) [] list1 list2
|> printfn "%A"

List.foldBack2 (fun elem1 elem2 acc -> elem1::elem2::acc) list1 list2 []
|> printfn "%A"

// [5; 5; 4; 4; 3; 3; 2; 2; 1; 1]
// [1; 1; 2; 2; 3; 3; 4; 4; 5; 5]

List.forall

判斷是否 list 的所有 element 都通過 predicate function 條件

predicate : ('T -> bool) -> list : 'T list -> bool

[ 0 .. 2 .. 10 ]
|> List.forall (fun elem -> elem % 2 = 0)
|> printf "%b"
// true

List.forall2

判斷是否兩個 list 的所有 element 都通過 predicate function 條件

predicate : ('T1 -> 'T2 -> bool) -> list1 : 'T1 list -> list2 : 'T2 list -> bool

let list1 = [ 1 .. 10]

[ 1 .. 10 ]
|> List.forall2 (fun elem1 elem2 -> (elem1 + elem2) % 2 = 0) list1 
|> printf "%b"
// true

Conclusion

• List module 所提供的 function 都必須非常熟練，因為這些都是常用的 Higher Order Function，算是 FP 的基本功

Reference

MSDN , Collection.List Module (F#)