Prime Factorization using Unfold in Haskell


I randomly yesterday started thinking about the unfoldr function in Haskell while working out at the gym (how nerdy is that, I am lifting iron but thinking of functional programming). Unfoldr take a single and an unfolding function and turns it into a list (the opposite of fold).  At the gym I was thinking about an application where I can use this and I decided that when I got home I would use it to write a prime factorization function.  This is a method that when given a number returns the list of its prime factors.


It was easy to write the only part I am not pleased about is the code I used to deal with tuples.  It seems clumsy and I am still looking for a way to clean that up.


One note: The code below references a list of prime numbers called primes , which is not shown.


Here is the code:



   1: primeFactors x = unfoldr findFactor x
   2:                  where
   3:                    first (a,b,c) = a
   4:                    findFactor 1 = Nothing
   5:                    findFactor b = (\(_,d,p)-> Just (p, d))
   6:                                   $ head $ filter ((==0).first) 
   7:                                   $  map (\p –> (b `mod` p, b `div` p, p))  primes

This function will take any number which is greater than 1 and return a list of its prime factors.  But don’t take my word for it, I wrote a quickcheck property to ensure the prime factors multiply back to the original number:



   1: prop_factors num =  num > 1 ==> num == (foldr1 (*) $ primeFactors num)

When running quickcheck on this property you see the following: 


quickCheck prop_factors
OK, passed 100 tests.


 

Comments (3)

  1. Matt Bauman says:

    I'm just learning Haskell, picking it up as I go through Project Euler.  I absolutely love the idea of using unfoldr, but I'm still learning what is good style and such.  I do think this is a bit more elegant:

    <pre>primeFactors :: (Integral a) => a -> [a]

    primeFactors x = unfoldr findFactor x

       where

           findFactor 1 = Nothing

           findFactor x = Just (nextFactor, x `div` nextFactor)

               where nextFactor = head $ filter (f -> f `divides` x) primes

    </pre>

  2. MattManela says:

    Ah, yes.  I didn't think of using the "divides" function.  Most of my extra work was to replicate that functions behavior.

    Nice job.