Reduce vs Fold in Scala

For better or worse in functional programming there exists fuzzy concrete notions on what it means to fold over some input versus what it means to reduce over some input. The concrete implementations vary from language to language and even between some libraries. Yet, the underlying fundemental concept tends to hold true, that you are taking some value of N and performing aggregation operations on it such that the end result is typically some value of <= N.

Even in haskell the fold family of functions is overloaded in the sense that it is capable of doing both what scala calls reducing and folding. For example, take the following haskell function that takes a list of integers and produces a sum value in terms of folding:

sumList :: [Int] -> Int  
sumList = foldl (+) 0  

In haskell one might also implement the filterList combinator in terms of folding. The definition of which would resemble the following example:

filterList :: (a -> bool) -> [a] -> [a]  
filterList p = foldl (\ m n -> if (p n) then m ++ [n] else m) []  

While the fold derived operations of sumList and filterList both take a value of N and perform aggregegate operations on it such that the end result is a a value of <= N, their type signatures tell a different story.

sumList takes a list of integers and produces a single integer while filterList takes a list of integers and produces a subset of that list. Putting their type signatures next to each other highlights this important difference.

sumList :: [Int] -> Int  
filterList :: (a -> bool) -> [a] -> [a]  

This is all possible because foldl's type signature is really generic in the sense that all it cares about is that the type of the final value is the same type of the initial value. It's type signature is as follows:

foldl :: (a -> b -> a) -> a -> [b] -> a  

Now this all becomes important when we take the type signatures for scala's implementations of folding and reducing into consideration. Both of which are as follows:

def foldLeft [B] (z: B)(f: (B, A) => B): B  
def reduceLeft [B >: A] (f: (B, A) => B): B  

A quick glance reveals some of the following differences:

• foldLeft has a paramaterized type of B while reduceLeft has a paramaterized type of B >: A
• foldLeft is a curried function where the first curried group takes the folds initial value and that reduceLeft is non curried and doesn't take an initial value at all
• In foldLeft the accumulator and the final return type (B) must be related to the item type (A).

So if reduceLeft doesn't take an initial value as an argument, then what is it's initial value? The initial value of reduceLeft is the initial value of the collection. So if you have a List[Int] and you reduceLeft over it, you will only ever be able to produce an Int (or a supertype of Int) from that operation. However, foldLeft is capable of producing any type you can pass into the initial value.

So we would be able to easily convert our sumList implementation from haskell to scala using reduceLeft like so:

def sum(inputs: List[Int]): Int = inputs.reduceLeft (_+_)  

It's impossible for us to implement filterList in terms of reduceLeft. However, we can easily implement filterList in terms of foldLeft like so:

def filter(inputs: List[Int], p: (Int) => Boolean) = {  
  inputs.foldLeft(List[Int]()) { (m, n) =>
    p(n) match {
      case true  => m ++ List(n)
      case false => m
    }
  }
}

Some interesting things about what can be represented in terms of reduceLeft and foldLeft outside of the type system are related to wether the parameter type for the iterable is a monoid or a semi-group. If the type parameter of your iterable is a monoid, meaning it has a zero value and an append operation, you can implement reduceLeft in terms of foldLeft. But if your type parameter is a semi-group, meaning it has an append operation but no zero value then there are a subset of reduceLeft operations that can not be implemented in terms of foldLeft.