F#：如何称呼 map 和 fold 的组合，或者 map 和 reduce 的组合？

Question

一个简单的例子，灵感来自 this question:

module SimpleExample =
    let fooFold projection folder state source =
        source |> List.map projection |> List.fold folder state
    // val fooFold :
    //   projection:('a -> 'b) ->
    //     folder:('c -> 'b -> 'c) -> state:'c -> source:'a list -> 'c

    let fooReduce projection reducer source =
        source |> List.map projection |> List.reduce reducer
    // val fooReduce :
    //   projection:('a -> 'b) -> reducer:('b -> 'b -> 'b) -> source:'a list -> 'b

    let game = [0, 5; 10, 15]
    let minX, maxX = fooReduce fst min game, fooReduce fst max game
    let minY, maxY = fooReduce snd min game, fooReduce snd max game

在此示例中，函数 fooFold 和 fooReduce 的自然名称是什么？唉，mapFold 和 mapReduce 已经有人了。

mapFold 是 F# 库的一部分，对 return 'result list * 'state 的元组的输入执行 fold 操作，类似于 scan ，但没有初始状态，也不需要自己提供元组作为状态的一部分。它的 signature 是：

val mapFold : ('State -> 'T -> 'Result * 'State) -> 'State -> 'T list -> 'Result list * 'State

由于投影可以很容易地集成到文件夹中，因此包含 fooFold 功能仅用于说明目的。

和MapReduce：

MapReduce is an algorithm for processing huge datasets on certain kinds of distributable problems using a large number of nodes

现在来看一个更复杂的示例，其中 fold/reduce 不直接应用于输入，而是应用于选择键后的分组。这个例子是从 a Python library 借来的，它被称为 - 可能是误导性的 - reduceby.

module ComplexExample =
    let fooFold keySelection folder state source =
        source |> Seq.groupBy keySelection 
        |> Seq.map (fun (k, xs) ->
            k, Seq.fold folder state xs) 
    // val fooFold :
    //   keySelection:('a -> 'b) ->
    //     folder:('c -> 'a -> 'c) -> state:'c -> source:seq<'a> -> seq<'b * 'c>
    //     when 'b : equality

    let fooReduce keySelection projection reducer source =
        source |> Seq.groupBy keySelection 
        |> Seq.map (fun (k, xs) ->
            k, xs |> Seq.map projection |> Seq.reduce reducer) 
    // val fooReduce :
    //   keySelection:('a -> 'b) ->
    //     projection:('a -> 'c) ->
    //     reducer:('c -> 'c -> 'c) -> source:seq<'a> -> seq<'b * 'c>
    //     when 'b : equality

    type Project = { name : string; state : string; cost : decimal }
    let projects =
        [ { name = "build roads";  state = "CA"; cost = 1000000M }
          { name = "fight crime";  state = "IL"; cost = 100000M  }
          { name = "help farmers"; state = "IL"; cost = 2000000M }
          { name = "help farmers"; state = "CA"; cost = 200000M  } ]
    fooFold (fun x -> x.state) (fun acc x -> acc + x.cost) 0M projects
    // val it : seq<string * decimal> = seq [("CA", 1200000M); ("IL", 2100000M)]

    fooReduce (fun x -> x.state) (fun x -> x.cost) (+) projects
    // val it : seq<string * decimal> = seq [("CA", 1200000M); ("IL", 2100000M)]

此处函数 fooFold 和 fooReduce 的自然名称是什么？

Answer 1

我可能会将前两个命名为 mapAndFold 和 mapAndReduce（尽管我同意 mapFold 和 mapReduce 如果尚未被使用的话，它们会是个好名字).或者，我会选择 mapThenFold（等），这可能更明确，但读起来有点麻烦。

对于更复杂的，reduceBy 和 foldBy 听起来不错。问题是，如果您还想要不执行映射操作的那些函数的版本，这将不起作用。如果你想要那个，你可能需要 mapAndFoldBy 和 mapAndReduceBy（以及 foldBy 和 reduceBy）。这有点难看，但恐怕这是你能做的最好的了。

更一般地说，将名称与 Python 进行比较时的问题是 Python 允许重载，而 F# 函数则不允许。这意味着您需要为具有多个重载的函数指定一个唯一的名称。这意味着你只需要想出一个一致的命名方案，不会让名字长得难以忍受。

（我在为 Deedle 库中的函数起名字时遇到过这种情况，这在某种程度上受到了 Pandas 的启发。例如，您可以查看 the aggregation functions in Deedle 的示例 - 有一个命名中的模式来处理每个函数需要一个唯一名称的事实。）

Answer 2

我和托马斯有不同的看法。

首先；我认为没有重载是一件好事，给每个操作唯一的名字也是好东西。我还要说，为很少使用的函数赋予长名称更为重要并且不应避免。

编写更长的名称通常从来都不是问题，因为我们作为程序员通常使用具有自动完成功能的 IDE。但是阅读和理解是不同的。知道一个函数的作用是因为它的描述性名称很长比短名称更好。

函数的使用频率越低，越长的描述性函数名称越重要。它有助于阅读和理解代码。很少使用的简短且缺乏描述性的函数名称会导致混淆。这如果它甚至只是另一个函数名称的重载，混乱只会增加。

是；命名事物可能很难，这就是为什么它很重要且不应避免的原因。

根据您的描述。我会将其命名为 mapFold 和 mapReduce。正如那些准确地描述了他们所做的那样。

F# 中已经有一个 mapFold，在我看来，F# 开发人员在命名、参数或函数的输出。但无论如何，他们就是搞砸了。

我通常会期望 mapFold 做 map 然后 fold。实际上它确实如此，但它也是 return 的中间体在运行上创建的列表。我不希望它 return。我也希望它能通过两个函数而不是一个。

当我们收到 Thomas 关于将其命名为 mapAndFold 或 mapThenFold 的建议时。那么我会期待不同的行为对于这两个功能。 mapThenFold 确切地说明了它的作用。 map然后fold就可以了。我认为 then 是不重要。这也是我将其命名为 mapFold 或 mapReduce 的原因。以这种方式编写它已经建议 then.

但是 mapAndFold 或 mapAndReduce 并没有说明执行顺序。它只是说它做了两件事或者不知何故 return 这个和那个

考虑到这一点，我会说 F# 库应该将其 mapFold 命名为 mapAndFold，更改 return 价值只是 return 折叠（并且有两个参数而不是一个）。但是，嘿，现在搞砸了，我们不能再改变它了。

至于mapReduce，我觉得你有点误会了。 mapReduce 算法就是这样命名的，因为它只是 map 然后 reduce。就是这样。

但是函数式编程及其无状态和更具描述性的操作有时会带来额外的好处。技术上与 for/fold 相比，map 的功能较弱，因为它仅描述了值的更改方式，而顺序无关紧要或列表中的位置。但是由于这个限制，您可以运行并行处理它，即使在大型计算机集群上也是如此。就这样 mapReduce 你引用的算法是做什么的。

但这并不意味着 mapReduce 必须始终运行在大集群上或并行运行。在我看来你可以只需将其命名为 mapReduce 即可。每个人都会知道它的作用，我认为没有人会期望它突然运行群集。

总的来说，我认为 F# 提供的 mapFold 很愚蠢，这里有 4 个我认为应该提供的示例。

let double x = x * 2
let add x y  = x + y

mapFold      double add 0 [1..10] // 110
mapAndFold   double add 0 [1..10] // [2;4;6;8;10;12;14;16;18;20] * 110
mapReduce    double add   [1..10] // Some (110)
mapAndReduce double add   [1..10] // Some ([2;4;6;8;10;12;14;16;18;20] * 110)

好吧 mapFold 这样不行，所以你有以下选择。

按照您的方式实施mapReduce。并忽略与 mapFold.
提供 mapAndReduce 和 mapReduce.
使您的 mapReduce return 与 mapFold 的默认实现相同，并提供 mapThenReduce.
喜欢 (3) 但还要添加 mapThenFold.

选项 4 与 F# 中已有的内容具有最大的兼容性和期望。但这并不意味着你必须那样做。

在我看来我会：

执行 mapReduce returning map 的结果然后 reduce.
我不关心 mapAndReduce 版本 return 是一个列表和结果。
提供一个 mapThenFold 期望两个函数参数 return 只是 fold.

作为一般注意事项：仅通过调用 map 然后 reduce 实现 mapReduce 有点毫无意义。我会希望它有一个更底层的实现，只需遍历一次数据结构就可以完成这两项工作。如果没有，我可以调用 map 然后 reduce 无论如何。

所以一个实现应该是这样的：

let mapReduce mapper reducer xs =
    let rec loop state xs =
        match xs with
        | []    -> state
        | x::xs -> loop (reducer state (mapper x)) xs
    match xs with
    | []    -> ValueNone
    | [x]   -> ValueSome (mapper x)
    | x::xs -> ValueSome (loop (mapper x) xs)

let double x = x * 2
let add x y  = x + y

let some110 = mapReduce double add [1..10]

F#：如何称呼 map 和 fold 的组合，或者 map 和 reduce 的组合？

F#: What to call a combination of map and fold, or of map and reduce?

f#

mapreduce

terminology

fold