Kotlin – Difference between fold and reduce in Kotlin, When to use which

foldkotlinreduce

I am pretty confused with both functions fold() and reduce() in Kotlin, can anyone give me a concrete example that distinguishes both of them?

Best Answer

fold takes an initial value, and the first invocation of the lambda you pass to it will receive that initial value and the first element of the collection as parameters.

For example, take the following code that calculates the sum of a list of integers:

listOf(1, 2, 3).fold(0) { sum, element -> sum + element }

The first call to the lambda will be with parameters 0 and 1.

Having the ability to pass in an initial value is useful if you have to provide some sort of default value or parameter for your operation. For example, if you were looking for the maximum value inside a list, but for some reason want to return at least 10, you could do the following:

listOf(1, 6, 4).fold(10) { max, element ->
    if (element > max) element else max
}

reduce doesn't take an initial value, but instead starts with the first element of the collection as the accumulator (called sum in the following example).

For example, let's do a sum of integers again:

listOf(1, 2, 3).reduce { sum, element -> sum + element }

The first call to the lambda here will be with parameters 1 and 2.

You can use reduce when your operation does not depend on any values other than those in the collection you're applying it to.

Related Solutions

How to know when to use fold-left and when to use fold-right

You can transfer a fold into an infix operator notation (writing in between):

This example fold using the accumulator function x

fold x [A, B, C, D]

thus equals

A x B x C x D

Now you just have to reason about the associativity of your operator (by putting parentheses!).

If you have a left-associative operator, you'll set the parentheses like this

((A x B) x C) x D

Here, you use a left fold. Example (haskell-style pseudocode)

foldl (-) [1, 2, 3] == (1 - 2) - 3 == 1 - 2 - 3 // - is left-associative

If your operator is right-associative (right fold), the parentheses would be set like this:

A x (B x (C x D))

Example: Cons-Operator

foldr (:) [] [1, 2, 3] == 1 : (2 : (3 : [])) == 1 : 2 : 3 : [] == [1, 2, 3]

In general, arithmetic operators (most operators) are left-associative, so foldl is more widespread. But in the other cases, infix notation + parentheses is quite useful.

Difference between fold and reduce

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)

Best Answer

Related Solutions

How to know when to use fold-left and when to use fold-right

Difference between fold and reduce

Related Topic