Monday, September 7, 2009

Collection/Iterable/Iterator reduceRight and reduceLeft

Folding and reducing are two types of operations that are both very important when dealing with collections in Scala (and other functional languages). This topic covers the reduce operations. The fold topic will be covered shortly.

A simplistic (probably over-simplistic) explanation is they allow processing of the collections. One can consider foldRight and foldLeft to be very similar to a visitor that visits each element and performs a calculation. It does not change the values of the collection, instead it calculates a result from visiting each element. In Java you might see the following pattern:

  1. class Collection {
  2.   pubic Result op( Result startingValue, Op operation){...}
  3. }
  4. interface Op{
  5.   public Result op( Object nextCollectionElem, Result lastCalculatedResult)
  6. }


To a Java programmer this is pretty obvious how you use it. Reduce operations are similar but very narrow in scope. They only return values that are of the same type as the original collection (IE a list of Int will return an Int from reduce) and there is no initial seed value. The first two inputs are the first and second elements of the collection. If there is only one element then that element is returned.

Reduce might look like the following in Java:

  1. class Collection {
  2.   pubic Integer op(Op operation){...}
  3. }
  4. interface Op{
  5.   public Integer op( Integer nextElem, Int lastCalculatedResult)
  6. }

One last point before examples. For fold and reduce operations there are both foldLeft and foldRight and similarly reduceLeft and reduceRight. These indicate the order that a collection is processed. Note that for certain collections one direction is more performant that the other. Lists, for example, are better to process left to right because of the datastructure used.

Some problems that are ideally suited to reduce:
  • Calculate the minimum value of a collection
  • Calculate the sum of a collection
  1. scala> val list = List("one", "two", "three")
  2. list: List[java.lang.String] = List(one, two, three)
  3. scala> list reduceRight ((elem, result) => {if (elem.length < result.length ) elem else result})
  4. res2: java.lang.String = two
  5. // reduce left has the order of parameter reversed.
  6. scala> list reduceLeft ((result, elem) => {if (elem.length < result.length ) elem else result})
  7. res4: java.lang.String = one
  8. // if only 1 element that element is returned
  9. scala> List("one") reduceRight ((elem, result) => {if (elem.length < result.length ) elem else result})
  10. res3: java.lang.String = one
  11. // the two following are equivalent.  _ indicates one arguement.  If there are two arguments the first _ is the first argument and the second _ is the second argument
  12. scala> List(1,2,3) reduceRight ((elem, result) => {elem + result})
  13. res6: Int = 6
  14. scala> List(1,2,3) reduceRight ( _ + _ )
  15. res5: Int = 6
  16. // find minimum.  Four equivalent ways to write it
  17. scala> List(1,2,3) reduceRight ((elem, result) => {elem.min(result)})
  18. res11: Int = 1
  19. scala> List(1,2,3) reduceRight ((elem, result) => {elem min result})
  20. res12: Int = 1
  21. scala> List(1,2,3) reduceRight (_.min(_))
  22. res10: Int = 1
  23. scala> List(1,2,3) reduceRight ( _ min _ )
  24. res9: Int = 1

No comments:

Post a Comment