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]

这个“应用”操作就是为什么这些被称为“应用函数器”的原因。不是任何旧的函数器，而是实用的函数器。(为什么他们是“functor”的原因稍微复杂一点)

到目前一切尚好。但是等等！如果我的函数列表中的每个函数都返回另一个函数，该怎么办？

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

或者，如果我记得可以用fun x y -> ...的缩写形式来编写fun x -> fun 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。在下一行，我简单地将这个函数列表折叠起来，将每个函数应用于前一个函数的结果。

Answer 2

您可以检查实现中的想法：

https://github.com/fsharp/fsharp/blob/master/src/fsharp/FSharp.Core/array.fs

  let fold<'T,'State> (f : 'State -> 'T -> 'State) (acc: 'State) (array:'T[]) =
        checkNonNull "array" array
        let f = OptimizedClosures.FSharpFunc<_,_,_>.Adapt(f)
        let mutable state = acc             
        for i = 0 to array.Length-1 do 
            state <- f.Invoke(state,array.[i])
        state

下面是几个实现：

let fold2<'a,'b,'State> (f : 'State -> 'a -> 'b -> 'State) (acc: 'State) (a:'a array) (b:'b array) =
  let mutable state = acc    
  Array.iter2 (fun x y->state<-f state x y) a b
  state

let iter3 f (a: 'a[]) (b: 'b[]) (c: 'c[]) = 
  let f = OptimizedClosures.FSharpFunc<_,_,_,_>.Adapt(f)
  if a.Length <> b.Length || a.Length <> c.Length then failwithf "length"
  for i = 0 to a.Length-1 do 
    f.Invoke(a.[i], b.[i], c.[i])

let altIter3 f (a: 'a[]) (b: 'b[]) (c: 'c[]) = 
  if a.Length <> b.Length || a.Length <> c.Length then failwithf "length"
  for i = 0 to a.Length-1 do 
    f (a.[i]) (b.[i]) (c.[i])

let fold3<'a,'b,'State> (f : 'State -> 'a -> 'b -> 'c -> 'State) (acc: 'State) (a:'a array) (b:'b array) (c:'c array) =
  let mutable state = acc    
  iter3 (fun x y z->state<-f state x y z) a b c
  state

注意：我们没有iter3，所以，实现它吧。OptimizedClosures.FSharpFunc最多只允许5个(或者是7个？)参数。有有限数量的类型插槽可用。这不足为奇。当然，您可以在不使用OptimizedClosures的情况下进行更高的测试。

..。不管怎样，一般来说，你不想一次迭代太多的列表/数组/序列。因此，我要告诫不要走得太高。

..。在这种情况下，更好的前进方式可能是首先从所述列表/数组构造记录或元组。然后，您可以只使用map和iter，它们已经内置。这就是zip / zip3的全部内容(参见："(array1.i，array2.i，array3.i)")

    let zip3 (array1: _[]) (array2: _[]) (array3: _[]) = 
        checkNonNull "array1" array1
        checkNonNull "array2" array2
        checkNonNull "array3" array3
        let len1 = array1.Length
        if len1 <> array2.Length || len1 <> array3.Length then invalidArg3ArraysDifferent "array1" "array2" "array3" len1 array2.Length array3.Length
        let res = Microsoft.FSharp.Primitives.Basics.Array.zeroCreateUnchecked len1 
        for i = 0 to res.Length-1 do 
            res.[i] <- (array1.[i],array2.[i],array3.[i])
        res

我目前使用的是数组，所以我的解决方案与数组有关。真对不起。这是一个列表的递归版本。

let fold3 f acc a b c =
  let mutable state = acc
  let rec fold3 f a b c =
    match a,b,c with
    | [],[],[] -> ()
    | [],_,_
    | _,[],_
    | _,_,[] -> failwith "length"
    | ahead::atail, bhead::btail, chead::ctail -> 
        state <- f state ahead bhead chead
        fold3 f atail btail ctail
    fold3 f a b c 

也就是说，我们在一个函数中定义了一个递归函数，它作用于/改变/改变外部作用域可变acc变量(函数中的闭包)。最后，这将被返回。

从这些函数中推断出多少类型信息是相当酷的。在上面的数组示例中，我主要是显式地使用'a 'b 'c。这一次，我们让类型推断生效。它知道我们正在处理来自::运算符的列表。这是一种巧妙的做法。

注意：编译器可能会展开这种尾递归方法，因此它只是一个幕后的循环。通常，在优化之前得到一个正确的答案。不过，只是提到这一点，作为以后思考的食粮。

Answer 3

我认为现有的答案提供了很好的选择，如果你想推广折叠，这是你最初的问题。但是，如果我只是想在A、B和C中指定的输入上调用polynomial函数，那么我可能不想在我的代码库中引入相当复杂的结构，比如带有花哨操作符的应用函数器。

如果您转置输入数据，问题就会变得简单得多，这样您就可以得到一个转置后的列表，其中包含用于计算每个多项式的输入，而不是一个包含单个变量列表的列表[A; B; C]。为此，我们需要transpose function：

let rec transpose = function
  | (_::_)::_ as M -> List.map List.head M :: transpose (List.map List.tail M)
  | _ -> []

现在，您可以使用输入创建一个列表，对其进行转置并使用List.map计算所有多项式

transpose [A; B; C]
|> List.map (function 
  | [a; b; c] -> polynomial 0.7 a b c
  | _ -> failwith "wrong number of arguments")