F# 折叠介绍，并举几个例子

2024-04-14 20:54:04 113

示例

折叠是与元素序列一起使用的（高阶）函数。他们崩溃seq<'a>到'b那里'b是任何类型（还可能'a）。这有点抽象，因此让我们进入具体的实际示例。

计算所有数字的总和

在此示例中，'a是int。我们有一个数字列表，我们想计算所有数字的总和。总结列表中的数字，[1;2;3]我们写

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

让我解释一下，因为我们正在处理列表，因此我们fold在List模块中使用List.fold。第一个参数fold是二进制函数folder。第二个参数是初始值。fold通过将folder函数连续应用于列表中的元素（从初始值和第一个元素开始）开始折叠列表。如果列表为空，则返回初始值！

执行示例的示意图如下所示：

let add x y = x + y //这是我们的文件夹（一个二进制函数，带有两个参数）
List.fold add 0 [1; 2; 3;]
=>List.foldadd (add 0 1) [2; 3] 
//二进制函数作为第一个参数中的文件夹再次传递
//初始值更新为在第二个参数中加01=1
//列表的尾部（除第一个元素外的所有元素）在第三个参数中传递
//变成这样：
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] //加12=3
List.fold add (add 3 3) [] 
List.fold add 6 [] // the list is empty now -> return 6
6

该函数List.sum大致List.foldaddLanguagePrimitives.GenericZero是通用零使其与整数，浮点数，大整数等兼容的地方。

计数列表中的元素（实现count）

这项操作几乎与上述操作相同，但是忽略了列表中元素的实际值，而是添加了1。

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

也可以这样完成：

[1; 2; 3]
|>List.map(fun x -> 1) //将每个要素变成1，[1;2;3]变为[1;1;1]
|>List.sum//总和[1;1;1]是3

因此，您可以定义count如下：

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

查找列表的最大值

这次我们将使用List.reducelike，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] //真正, 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] //假

串联清单

在这里，我们获取列表列表文件夹功能是@运算符

//[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] //是的，下面有更多内容
List.fold (&&) true [true; false] //假, more on this below
//等等...

计算数字的阶乘

与将数字求和相同的想法，但是现在我们将它们相乘。如果我们想要阶乘n我们将列表中的所有元素复数[1..n]。代码变为：

//文件夹
let times x y = x * y
let factorial n =List.foldtimes 1 [1 .. n]
//或者也许是大整数
let factorial n =List.foldtimes 1I [1I .. n]

实施forall，exists以及contains

该函数forall检查序列中的所有元素是否都满足条件。exists检查列表中至少一个元素是否满足条件。首先，我们需要知道如何折叠bool值列表。好吧，我们使用折线！布尔运算符将成为我们的文件夹函数。

为了检查列表中的所有元素是否都被true折叠，我们使用&&函数true作为初始值来折叠它们。

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

同样，要检查true列表布尔中是否有一个元素，我们使用||运算符将其折叠false为初始值：

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

返回forall和exists。在这里，我们获取任何类型的列表，使用条件将所有元素转换为布尔值，然后将其折叠：

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

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

检查[1;2;3;4]小于5：

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

用以下contains方法定义方法exists：

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

甚至

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

现在检查列表[1..5]是否包含值2：

contains 2 [1..5] //真正

实施reverse：

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

实施map和filter

let map f =List.fold(fun acc x ->List.appendacc [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不能做的吗？我真的不知道