折叠和还原的区别？

试图学习 F # ，但在试图区分 弃牌和 减少时弄混了。Fold 似乎执行 一样，但是带有一个额外的参数。这两种职能的存在是否有合理的理由，或者它们是为了适应不同背景的人而存在的？(例如: 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])
45104 次浏览
小开
最佳答案

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

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

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

此外，reduce在空输入列表上抛出异常。

小开

除了 Lee 所说的，你可以用 fold来定义 reduce，但是不能(容易地)用 fold来定义 reduce:

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)
小开

让我们看看他们的签名:

> 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，从蓄电池 s开始应用 f:

    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
小开

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
小开

老问题，已经有很多好答案了，所以有点不同的看法。我已经有一段时间没有涉足 F # 了，出于对折叠、减少、收集、注入等等之间的区别的好奇，我来到了这里。一些研究带我去了 维基百科页面折叠实现的各种语言，并从那里得到了一篇非常有趣的论文，作者是赫顿 · 格雷厄姆(Hutton Graham) 折叠的表现力可能会给这个问题带来一些额外的启示

「折叠运算法则起源于可计算性理论(Kleene，1952) 作为一种编程语言的中心概念的折叠可以追溯到减少 APL 的操作符(Iverson，1962) ，后来到 FP 的插入操作符(Backus, 1978年)。”

因此，根据上述引用的历史来看，这些术语从它们的起源开始就被广泛使用，但褶皱是其他术语的根源。本文值得一读，因为作者定义了所有其他相关的操作，使用了摺叠，并提供了一个语言不可知论的视角。


提交答案