Difference between fold and reduce?
Solution 1
Fold
takes an explicit initial value for the accumulator while reduce
uses the first element of the input list as the initial accumulator value.
This means the accumulator and therefore result type must match the list element type, whereas they can differ in fold
as the accumulator is provided separately. This is reflected in the types:
List.fold : ('State -> 'T -> 'State) -> 'State -> 'T list -> 'State
List.reduce : ('T -> 'T -> 'T) -> 'T list -> 'T
In addition reduce
throws an exception on an empty input list.
Solution 2
In addition to what Lee said, you can define reduce
in terms of fold
, but not (easily) the other way round:
let reduce f list =
match list with
| head::tail -> List.fold f head tail
| [] -> failwith "The list was empty!"
The fact that fold
takes an explicit initial value for the accumulator also means that the result of the fold
function can have a different type than the type of values in the list. For example, you can use accumulator of type string
to concatenate all numbers in a list into a textual representation:
[1 .. 10] |> List.fold (fun str n -> str + "," + (string n)) ""
When using reduce
, the type of accumulator is the same as the type of values in the list - this means that if you have a list of numbers, the result will have to be a number. To implement the previous sample, you'd have to convert the numbers to string
first and then accumulate:
[1 .. 10] |> List.map string
|> List.reduce (fun s1 s2 -> s1 + "," + s2)
Solution 3
fold
is a much more valuable function than reduce
. You can define many different functions in terms of fold
.
reduce
is just a subset of fold
.
Definition of fold:
let rec fold f v xs =
match xs with
| [] -> v
| (x::xs) -> f (x) (fold f v xs )
Examples of functions defined in terms of fold:
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
Solution 4
Let's look at their signatures:
> 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>
There are some important differences:
- While
reduce
works on one type of elements only, the accumulator and list elements infold
could be in different types. With
reduce
, you apply a functionf
to every list element starting from the first one:f (... (f i0 i1) i2 ...) iN
.With
fold
, you applyf
starting from the accumulators
:f (... (f s i0) i1 ...) iN
.
Therefore, reduce
results in an ArgumentException
on empty list. Moreover, fold
is more generic than reduce
; you can use fold
to implement reduce
easily.
In some cases, using reduce
is more succinct:
// Return the last element in the list
let last xs = List.reduce (fun _ x -> x) xs
or more convenient if there's not any reasonable accumulator:
// Intersect a list of sets altogether
let intersectMany xss = List.reduce (fun acc xs -> Set.intersect acc xs) xss
In general, fold
is more powerful with an accumulator of an arbitrary type:
// Reverse a list using an empty list as the accumulator
let rev xs = List.fold (fun acc x -> x::acc) [] xs
Wallace
Updated on July 08, 2022Comments
-
Wallace almost 2 years
Trying to learn F# but got confused when trying to distinguish between fold and reduce. Fold seems to do the same thing but takes an extra parameter. Is there a legitimate reason for these two functions to exist or they are there to accommodate people with different backgrounds? (E.g.: String and string in C#)
Here is code snippet copied from sample:
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])
-
jpe over 8 yearsYou define your
fold
differently fromList.fold
as the type ofList.fold
is('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
, but in your case('a -> 'b -> 'b) -> 'b -> 'a list -> 'b
. Just to make it explicit. Also, your implementation of append is wrong. It would work if you add a bind to it, e.g.List.collect id (fold (fun x y -> x :: y) [] [xs;ys])
, or replace cons with the append operator. Thus append is not the best example in this list. -
Fresheyeball about 8 yearsWhy define reduce such that it can error at runtime?
-
Andrew over 7 years+1 for the note on the generality of
fold' & its ability to express
reduce'. Some languages have a concept of structural chirality (Haskell I'm looking at you) you can fold left or right visually depicted in this wiki(en.wikipedia.org/wiki/Fold_%28higher-order_function). With an identity construct, the other two 'fundamental' FP operators (filter and fmap) are also implementable with an existing `fold' first-class language construct (they're all isomorphic constructs). (cs.nott.ac.uk/~pszgmh/fold.pdf) See: HoTT, Princeton (This comment section is too small to contain..) -
Pacerier about 7 yearsSo basically instead of doing
fold
, you can simply add that initial value to the start of the list and doreduce
? What's the point offold
then? -
Lee about 7 years@Pacerier - The accumulator function for fold has a different type:
'state -> 'a -> 'state
for fold vs'a -> 'a -> 'a
for reduce, so reduce constrains the result type to be the same as the element type. See Tomas Petricek's answer below. -
sksallaj almost 5 yearsOut of curiosity.. would this make reduce's performance faster than fold because it's under less assumptions about types and exceptions?