用一些例子介绍折叠

折叠是与元素序列一起使用的(高阶)函数。他们将 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 还有什么不能做的吗?我真的不知道