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

但是如果你想要这个用于一般情况,那么你需要我们称之为"applicative functors"的东西.

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

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]

这个操作"适用"是为什么这些被称为"applicative functors".不仅仅是任何有趣的人,而是应用者.(他们为什么是"仿函数"的原因有点复杂)

到现在为止还挺好.可是等等!如果我的函数列表中的每个函数都返回另一个函数怎么办？

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 -> ...

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

如果我apply的功能列表符合我的价值观怎么办？好吧,当然,我会得到另一个函数列表:

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包括polynomial被部分地施加到相应的元件的实例A,B以及C,仍然期望最后的参数x.在下一行,我简单地折叠这个函数列表,将它们中的每一个应用于前一个的结果.