F#，实现 fold3、fold4、fold_n

Question

我有兴趣实现 fold3、fold4 等，类似于 List.fold 和 List.fold2。例如

// TESTCASE
let polynomial (x:double) a b c = a*x + b*x*x + c*x*x*x
let A = [2.0; 3.0; 4.0; 5.0]
let B = [1.5; 1.0; 0.5; 0.2]
let C = [0.8; 0.01; 0.001; 0.0001]

let result = fold3 polynomial 0.7 A B C
// 2.0 * (0.7   ) + 1.5 * (0.7   )^2 + 0.8    * (0.7   )^3 -> 2.4094
// 3.0 * (2.4094) + 1.0 * (2.4094)^2 + 0.01   * (2.4094)^3 -> 13.173
// 4.0 * (13.173) + 0.5 * (13.173)^2 + 0.001  * (13.173)^3 -> 141.75
// 5.0 * (141.75) + 0.2 * (141.75)^2 + 0.0001 * (141.75)^3 -> 5011.964
//
// Output: result = 5011.964

我的第一个方法是将 3 个列表 A、B、C 分组到一个元组列表中，然后应用 list.fold

let fold3 f x A B C =
    List.map3 (fun a b c -> (a,b,c)) A B C
       |> List.fold (fun acc (a,b,c) -> f acc a b c) x

// e.g. creates [(2.0,1.5,0.8);  (3.0,1.0,0.01); ......]

我的第二种方法是声明一个可变数据，并使用 List.map3

let mutable result = 0.7
List.map3 (fun a b c ->
               result <- polynomial result a b c  // Change mutable data
               // Output intermediate data
               result) A B C
// Output from List.map3: [2.4094; 13.17327905; 141.7467853; 5011.963942]
// result mutable: 5011.963942

我想知道是否有其他方法可以解决这个问题。谢谢。

Answer 1

对于 fold3，您可以先执行 zip3，然后执行 fold:

let polynomial (x:double) (a, b, c) = a*x + b*x*x + c*x*x*x
List.zip3 A B C |> List.fold polynomial 0.7

---

但是如果您希望在一般情况下使用它，那么您需要我们称之为“应用仿函数”的东西。

首先，假设您有一个函数列表和一个值列表。现在我们假设它们的大小相同:

let fs = [ (fun x -> x+1); (fun x -> x+2); (fun x -> x+3) ]
let xs = [3;5;7]

您想要做的(很自然)是将每个函数应用于每个值。这很容易用 List.map2 完成:

let apply fs xs = List.map2 (fun f x -> f x) fs xs

apply fs xs  // Result = [4;7;10]

这个“apply”操作就是这些被称为“applicative functor”的原因。不仅仅是任何 ol' 仿函数，而是应用 仿函数。 (为什么他们是“仿函数”的原因有点复杂)

到目前为止一切顺利。可是等等!如果我的函数列表中的每个函数都返回另一个函数怎么办？

let f1s = [ (fun x -> fun y -> x+y); (fun x -> fun y -> x-y); (fun x -> fun y -> x*y) ]

或者，如果我记得 fun x -> fun y -> ... 可以写成 fun x y -> ... 的缩写形式/p>

let f1s = [ (fun x y -> x+y); (fun x y -> x-y); (fun x y -> x*y) ]

如果我应用这样的函数列表到我的值会怎样？好吧，自然地，我会得到另一个函数列表:

let f2s = apply f1s xs
// f2s = [ (fun y -> 3+y); (fun y -> 5+y); (fun y -> 7+y) ]

嘿，这是个主意!由于 f2s 也是函数列表，我可以再次应用它吗？我当然可以!

let ys = [1;2;3]
apply f2s ys  // Result: [4;7;10]

等等，什么？刚刚发生了什么？
我首先将第一个函数列表应用于xs，结果得到了另一个函数列表。然后我将该结果应用于 ys，并得到一个数字列表。
我们可以在没有中间变量 f2s 的情况下重写它:

let f1s = [ (fun x y -> x+y); (fun x y -> x-y); (fun x y -> x*y) ]
let xs = [3;5;7]
let ys = [1;2;3]
apply (apply f1s xs) ys  // Result: [4;7;10]

为了更加方便，此操作apply 通常表示为运算符:

let (<*>) = apply
f1s <*> xs <*> ys

看到我在那里做了什么吗？使用此运算符，它现在看起来非常类似于仅使用两个参数调用函数。整洁。

但是等等。我们原来的任务呢？在最初的需求中我们没有函数列表，我们只有一个函数。
好吧，这可以通过另一个操作轻松解决，我们称之为“先申请”。此操作将采用单个函数(不是列表)加上值列表，并将此函数应用于列表中的每个值:

let applyFirst f xs = List.map f xs

哦，等等。那只是 map 。傻我:-)
为了更加方便，通常还会为该操作指定一个运算符名称:

let (<|>) = List.map

现在，我可以做这样的事情:

let f x y = x + y
let xs = [3;5;7]
let ys = [1;2;3]
f <|> xs <*> ys  // Result: [4;7;10]

或者这个:

let f x y z = (x + y)*z
let xs = [3;5;7]
let ys = [1;2;3]
let zs = [1;-1;100]
f <|> xs <*> ys <*> zs  // Result: [4;-7;1000]

整洁!我做到了，所以我可以立即将任意函数应用于参数列表!

现在，您终于可以将此应用于您的原始问题:

let polynomial a b c (x:double) = a*x + b*x*x + c*x*x*x
let A = [2.0; 3.0; 4.0; 5.0]
let B = [1.5; 1.0; 0.5; 0.2]
let C = [0.8; 0.01; 0.001; 0.0001]

let ps = polynomial <|> A <*> B <*> C
let result = ps |> List.fold (fun x f -> f x) 0.7

列表 ps 由部分应用于 A、B 的相应元素的 多项式 实例组成，和 C，并且仍然期待最终参数 x。在下一行，我简单地折叠了这个函数列表，将它们中的每一个应用于前一个的结果。