文章/答案/技术大牛

发布

社区首页 >问答首页 >F#：什么叫地图和折叠的组合，或者地图和缩减的组合？

问F#：什么叫地图和折叠的组合，或者地图和缩减的组合？
EN

Stack Overflow用户

提问于 2021-11-28 09:41:30

回答 2查看 192关注 0票数 2

一个受这个问题启发的简单示例

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#库的一部分，对输入执行fold操作以返回与scan类似的'result list * 'state元组，但不需要自己提供元组作为状态的一部分。它的签名是：

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

由于投影可以很容易地集成到文件夹中，因此只为说明目的而包含fooFold函数。

和MapReduce

MapReduce是一种使用大量节点处理某些可分布问题的庞大数据集的算法。

现在，对于一个更复杂的例子，fold/reduce不是直接应用于输入，而是应用于所选键后面的分组。这个例子是从Python库借来的，在那里它被称为--也许是误导-- 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的自然名称是什么？

mapreduce

terminology

fold

回答 2

Stack Overflow用户

回答已采纳

发布于 2021-11-28 14:33:50

我可能会将前两个名称称为mapAndFold和mapAndReduce (虽然我同意，如果mapFold和mapReduce还没有被使用的话，它们将是好名字)。或者，我会使用mapThenFold (等)，这可能更明确，但它读起来有点麻烦。

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

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

(我在为Deedle图书馆中的函数命名时经历了这种情况，这在某种程度上是受到Pandas的启发。例如，您可以看到Deedle中的聚集函数作为一个例子--在命名中有一个模式来处理每个函数都需要一个唯一的名称。)

票数 1

Stack Overflow用户

发布于 2021-11-29 16:55:46

作为托马斯，我有不同的看法。

首先，我认为没有重载是件好事，给每个操作都取唯一的名称也是件好事。我还要说，给很少使用的函数取长名称更重要，不应回避。

编写较长的名称通常不会成为问题，因为我们作为编程人员通常使用具有自动完成功能的IDE。但是阅读和理解是不同的。因为一个长的描述性名称而知道一个函数所做的事情比一个短的名称更好。

较长的描述函数名越重要，使用函数的频率就越小。它有助于阅读和理解代码。很少使用的简短和较少描述性的函数名会引起混淆。如果它仅仅是另一个函数名的过载，那么混乱就会增加。

是的，命名事物可能很难，这就是为什么它的重要性和不可回避的原因。

和你描述的一样。我会给它取名为mapFold和mapReduce。就像他们所做的那样。

在F#中已经有了一个F#，在我看来，F#开发人员要么将函数的命名、参数或输出搞砸了。但不管怎样，他们都搞砸了。

我通常会期望mapFold做map，然后做fold。实际上是这样，但它也返回在运行过程中创建的中间列表。我不希望它回来的东西。我也希望它能传递两个函数而不是一个函数。

当我们谈到托马斯关于命名它的建议时，mapAndFold或mapThenFold。那么，我希望这两种功能有不同的行为。mapThenFold准确地告诉了它所做的事情。map，然后fold在上面。我认为和并不重要。这也是为什么我会把它命名为mapFold或mapReduce。用这种方式编写它已经建议使用，然后是。

但是mapAndFold或mapAndReduce并没有透露执行顺序。它只是说它做了两件事，或者以某种方式返回这个和。

考虑到这一点，我想说的是，F#库应该将其mapFold命名为mapAndFold或mapAndFold，将返回值更改为只返回折叠(并且有两个参数而不是一个参数)。但是，现在一切都搞砸了，我们不能再改变了。

至于mapReduce，我认为你有点弄错了。mapReduce算法就是这样命名的，因为它只执行map和reduce。就是这样。

但是，使用其无状态和更具描述性的操作进行函数式编程有时会带来额外的好处。从技术上讲，map的功能不如for/fold，因为它只是描述了值是如何改变的，而不是顺序或列表中的位置。但是由于这个限制，您可以并行运行它，甚至可以在大型计算机集群上运行。这就是你引用的mapReduce算法。

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

总的来说，我认为F#提供的F#是愚蠢的，下面是我认为应该提供的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返回与mapFold的默认实现相同的废话，并提供mapThenReduce。
喜欢(3)，还添加了mapThenFold。

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

在我看来，我只是：

实现mapReduce，返回映射的结果，然后减少。
我不关心返回列表和结果的mapAndReduce版本。
提供一个mapThenFold，它需要两个函数参数，返回折叠的结果。

请注意:只通过调用mapReduce然后调用reduce就实现了reduce，这有点毫无意义。我希望它有一个更低级别的实现，只需遍历一次数据结构就可以做到这两件事。如果没有，我只需打电话给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]