Fold Method Using List as Battery

Question

To find prime number factors, I used this piece of code:

def primeFactors(num: Long): List[Long] = { val exists = (2L to math.sqrt(num).toLong).find(num % _ == 0) exists match { case Some(d) => d :: primeFactors(num/d) case None => List(num) } } 

but this I found a cool and more functional approach to solve this problem with this code:

 def factors(n: Long): List[Long] = (2 to math.sqrt(n).toInt) .find(n % _ == 0).fold(List(n)) ( i => i.toLong :: factors(n / i)) 

I used to use foldLeft or fold just to get the sum of a list or other simple calculations, but here I can’t understand how the fold works and how it comes out of a recursive function. Can someone explain to you how the fold function works.

Answer 1

fold option

If you look at the signature of the Option fold function, it takes two parameters:

 def fold[B](ifEmpty: => B)(f: A => B): B 

What it does is, it applies f to the Option value if it is not empty. If Option empty, it simply returns ifEmpty output (this is a termination condition for recursion).

So, in your case, i => i.toLong :: factors(n / i) represents f , which will be evaluated if Option not empty. While List(n) is a termination condition.

fold used for collection / iterators

The other fold that you take to get the collection amount comes from TraversableOnce and has a signature like:

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

Here z is the starting value (suppose that the sum of the sum is 0 ) and op is the associative binary operator that is applied to z , and each collection value is from left to right.

Thus, both fold are distinguished by their implementation.