130

尝试学习 F#，但在尝试区分fold和reduce时感到困惑。折叠似乎做同样的事情，但需要一个额外的参数。这两个功能的存在是否有正当理由，或者它们的存在是为了容纳不同背景的人？（例如：C# 中的字符串和字符串）

这是从示例中复制的代码片段：

let sumAList list =
    List.reduce (fun acc elem -> acc + elem) list

let sumAFoldingList list =
    List.fold (fun acc elem -> acc + elem) 0 list

printfn "Are these two the same? %A " 
             (sumAList [2; 4; 10] = sumAFoldingList [2; 4; 10])
4

4 回答 4

182

除了 Lee 所说的之外，您可以根据 来定义reduce，fold但不能（容易）反过来：

let reduce f list = 
  match list with
  | head::tail -> List.fold f head tail
  | [] -> failwith "The list was empty!"

为累加器采用显式初始值这一事实fold也意味着fold函数的结果可以具有与列表中值的类型不同的类型。例如，您可以使用类型string的累加器将列表中的所有数字连接成文本表示：

[1 .. 10] |> List.fold (fun str n -> str + "," + (string n)) ""

使用 时reduce，累加器的类型与列表中值的类型相同 - 这意味着如果您有一个数字列表，则结果必须是一个数字。要实现前面的示例，您必须string先将数字转换为然后累加：

[1 .. 10] |> List.map string
          |> List.reduce (fun s1 s2 -> s1 + "," + s2)
于 2012-01-29T19:14:01.503 回答
178

Fold为累加器取一个显式的初始值，同时reduce使用输入列表的第一个元素作为初始累加器值。

这意味着累加器和结果类型必须与列表元素类型匹配，而它们可以不同，fold因为累加器是单独提供的。这反映在类型中：

List.fold : ('State -> 'T -> 'State) -> 'State -> 'T list -> 'State
List.reduce : ('T -> 'T -> 'T) -> 'T list -> 'T

此外reduce在空输入列表上引发异常。

于 2012-01-29T19:08:39.650 回答
21

fold是一个比 更有价值的功能reduce。您可以定义许多不同的函数fold。

reduce只是 的一个子集fold。

折叠的定义：

let rec fold f v xs =
    match xs with 
    | [] -> v
    | (x::xs) -> f (x) (fold f v xs )

根据折叠定义的函数示例：

let sum xs = fold (fun x y -> x + y) 0 xs

let product xs = fold (fun x y -> x * y) 1 xs

let length xs = fold (fun _ y -> 1 + y) 0 xs

let all p xs = fold (fun x y -> (p x) && y) true xs

let reverse xs = fold (fun x y -> y @ [x]) [] xs

let map f xs = fold (fun x y -> f x :: y) [] xs

let append xs ys = fold (fun x y -> x :: y) [] [xs;ys]

let any p xs = fold (fun x y -> (p x) || y) false xs 

let filter p xs = 
    let func x y =
        match (p x) with
        | true -> x::y
        | _ -> y
    fold func [] xs
于 2014-03-15T04:46:06.420 回答
19

让我们看看他们的签名：

> List.reduce;;
val it : (('a -> 'a -> 'a) -> 'a list -> 'a) = <fun:clo@1>
> List.fold;;
val it : (('a -> 'b -> 'a) -> 'a -> 'b list -> 'a) = <fun:clo@2-1>

有一些重要的区别：

  • 虽然reduce仅适用于一种类型的元素，但累加器和列表元素fold可能属于不同类型。

  • 使用reduce，您将一个函数f应用于从第一个元素开始的每个列表元素：

    f (... (f i0 i1) i2 ...) iN.

    使用fold，您f从累加器开始申请s：

    f (... (f s i0) i1 ...) iN.

因此，reduce导致一个ArgumentException空列表。此外，fold比reduce;更通用 您可以使用轻松fold实现。reduce

在某些情况下，使用reduce更简洁：

// Return the last element in the list
let last xs = List.reduce (fun _ x -> x) xs

如果没有任何合理的累加器，则更方便：

// Intersect a list of sets altogether
let intersectMany xss = List.reduce (fun acc xs -> Set.intersect acc xs) xss

一般来说，fold使用任意类型的累加器更强大：

// Reverse a list using an empty list as the accumulator
let rev xs = List.fold (fun acc x -> x::acc) [] xs
于 2012-01-29T19:25:17.483 回答