Difference between fold and reduce?

Question

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])

Answer 1

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)

Answer 2

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.

Answer 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

Answer 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 in fold could be in different types.

• With reduce, you apply a function f to every list element starting from the first one:

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

  With fold, you apply f starting from the accumulator s:

  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

Answer 5

Old question, which already has a lot of good answers, so a bit of a different take. I have not dabbled in F# in quite a while and landed here out of curiosity for the difference between fold, reduce, collect, inject et al. A bit of research took me to the wikipedia page on fold as implemented in various languages and from there to a very interesting paper by Hutton Graham: A tutorial on the universality and expressiveness of fold which may shed some additional light on this. Quote:

"The fold operator has its origins in recursion theory (Kleene, 1952), while the use of fold as a central concept in a programming language dates back to the reduction operator of APL (Iverson, 1962), and later to the insertion operator of FP (Backus, 1978)."

So, as far as history goes per the above quote, the terms have been pretty closely used since their origins, but fold is the one that is at the root of the others. The paper is worth a read as the author defines all the other related operations, using fold and provides a language agnostic perspective.