用一些例子介紹摺疊

摺疊是與元素序列一起使用的(高階)函式。他們將 seq<'a> 摺疊成'b,其中'b 是任何型別(可能仍然是'a)。這有點抽象,所以讓我們進入具體的實際例子。

計算所有數字的總和

在這個例子中,'a 是一個 int。我們有一個數字列表,我們想要計算所有數字的總和。總結我們寫的列表 [1; 2; 3] 的數量

List.fold (fun x y -> x + y) 0 [1; 2; 3] // val it : int = 6

讓我解釋一下,因為我們正在處理列表,我們在 List 模組中使用 fold,因此 List.foldfold 採用的第一個引數是二進位制函式,即資料夾。第二個引數是初始值fold 通過將資料夾函式連續應用於列表中以初始值和第一個元素開頭的元素開始摺疊列表。如果列表為空,則返回初始值!

執行示例的原理圖概述如下所示:

let add x y = x + y // this is our folder (a binary function, takes two arguments)
List.fold add 0 [1; 2; 3;]
=> List.fold add (add 0 1) [2; 3] 
// the binary function is passed again as the folder in the first argument
// the initial value is updated to add 0 1 = 1 in the second argument
// the tail of the list (all elements except the first one) is passed in the third argument
// it becomes this:
List.fold add 1 [2; 3]
// Repeat untill the list is empty -> then return the "inital" value
List.fold add (add 1 2) [3]
List.fold add 3 [3] // add 1 2 = 3
List.fold add (add 3 3) [] 
List.fold add 6 [] // the list is empty now -> return 6
6

函式 List.sum 大致是 List.fold add LanguagePrimitives.GenericZero,其中通用零使其與整數,浮點數,大整數等相容。

計算列表中的 elemets(實現 count

這與上面幾乎完全相同,但忽略了列表中元素的實際值,而是新增 1。

List.fold (fun x y -> x + 1) 0 [1; 2; 3] // val it : int = 3

這也可以這樣做:

[1; 2; 3]
|> List.map (fun x -> 1) // turn every elemet into 1, [1; 2; 3] becomes [1; 1; 1]
|> List.sum // sum [1; 1; 1] is 3

所以你可以定義 count 如下:

let count xs = 
    xs 
    |> List.map (fun x -> 1) 
    |> List.fold (+) 0 // or List.sum

查詢列表的最大值

這次我們將使用 List.reduce,它就像 List.fold 但沒有初始值,因為在這種情況下我們不知道我們正在進行的值的型別是什麼:

let max x y = if x > y then x else y
// val max : x:'a -> y: 'a -> 'a when 'a : comparison, so only for types that we can compare
List.reduce max [1; 2; 3; 4; 5] // 5
List.reduce max ["a"; "b"; "c"] // "c", because "c" > "b" > "a"
List.reduce max [true; false] // true, because true > false 

找到列表的最小值

就像找到最大值時一樣,資料夾也不同

let min x y = if x < y then x else y
List.reduce min [1; 2; 3; 4; 5] // 1
List.reduce min ["a"; "b"; "c"] // "a"
List.reduce min [true; false] // false

連線列表

這裡我們列出列表資料夾功能是 @ 運算子

// [1;2] @ [3; 4] = [1; 2; 3; 4]
let merge xs ys = xs @ ys
List.fold merge [] [[1;2;3]; [4;5;6]; [7;8;9]] // [1;2;3;4;5;6;7;8;9]

或者你可以使用二元運算子作為資料夾函式:

List.fold (@) [] [[1;2;3]; [4;5;6]; [7;8;9]] // [1;2;3;4;5;6;7;8;9]
List.fold (+) 0 [1; 2; 3] // 6
List.fold (||) false [true; false] // true, more on this below
List.fold (&&) true [true; false] // false, more on this below
// etc...

計算數字的階乘

與數字相加時的想法相同,但現在我們將它們相乘。如果我們想要 n 的階乘,我們乘以列表 [1 .. n] 中的所有元素。程式碼變為:

// the folder
let times x y = x * y
let factorial n = List.fold times 1 [1 .. n]
// Or maybe for big integers
let factorial n = List.fold times 1I [1I .. n] 

實施 forallexistscontains

函式 forall 檢查序列中的所有元素是否滿足條件。exists 檢查列表中的至少一個元素是否滿足條件。首先,我們需要知道如何摺疊 bool 值的列表。好吧,我們使用摺疊的類! 布林運算子將是我們的資料夾函式。

要檢查列表中的所有元素是否都是 true,我們將使用 && 函式將其摺疊為 true 作為初始值。

List.fold (&&) true [true; true; true] // true
List.fold (&&) true [] // true, empty list -> return inital value
List.fold (&&) true [false; true] // false

同樣,為了檢查列表中的一個元素是否為 true,我們使用||運算子以 false 作為初始值將其摺疊:

List.fold (||) false [true; false] // true
List.fold (||) false [false; false] // false, all are false, no element is true
List.fold (||) false [] // false, empty list -> return inital value

回到 forallexists。這裡我們獲取任何型別的列表,使用條件將所有元素轉換為布林值,然後將其摺疊:

let forall condition elements = 
    elements 
    |> List.map condition // condition : 'a -> bool
    |> List.fold (&&) true

let exists condition elements = 
    elements
    |> List.map condition
    |> List.fold (||) false

檢查[1; 2; 3; 4]小於 5:

forall (fun n -> n < 5) [1 .. 4] // true

使用 exists 定義 contains 方法:

let contains x xs = exists (fun y -> y = x) xs

甚至

let contains x xs = exists ((=) x) xs

現在檢查列表[1 .. 5]是否包含值 2:

contains 2 [1..5] // true

實施 reverse

let reverse xs = List.fold (fun acc x -> x::acc) [] xs
reverse [1 .. 5] // [5; 4; 3; 2; 1]

實施 mapfilter

let map f = List.fold (fun acc x -> List.append acc [f x]) List.empty
// map (fun x -> x * x) [1..5] -> [1; 4; 9; 16; 25]   

let filter p = Seq.fold (fun acc x -> seq { yield! acc; if p(x) then yield x }) Seq.empty
// filter (fun x -> x % 2 = 0) [1..10] -> [2; 4; 6; 8; 10]

fold 還有什麼不能做的嗎?我真的不知道