Prime Factoring Function in Haskell

Question

I am trying to make a function that will display a number's prime factors with a list (infinite) that I give it. Here is what I have so far:

-- Here is a much more efficient (but harder to understand) version of primes.
-- Try "take 100 primes" as an example (or even more if you like)
primes = 2 : primesFrom3 where 
    primesFrom3 = sieve [3,5..] 9 primesFrom3
    sieve (x:xs) b ~ps@(p:q:_)
      | x < b     = x : sieve xs b ps
      | otherwise =     sieve [x | x <- xs, rem x p /= 0] (q^2) (tail ps)



-- Write a function that factors its first argument using the (infinite)
-- list of available factors given in its second argument
-- (using rem x p /= 0 to check divisibility)
primeFactsWith :: Integer -> [Integer] -> [Integer]
primeFactsWith n (p:ps) = if (rem n p /= 0) then
                                (primeFactsWith n ps)
                          else (primeFactsWith p ps)

The top half was not written by me and works just fine. I am trying to get the second half to work, but it isn't. Read the comments in the code to better understand exactly what I am trying to do. Thanks! Oh and please don't just spout the answer. Give me some hints on how to do it and maybe what is wrong.

Answer 1

What's wrong

The problem is that you do a recursive call in both branches, therefore the function will never stop.

Some Hints

To build a recursive list-producing function, you'll need two branches or cases:

• Base case no recursive call, this stops the recursion and returns the final part of the result.
• Recursive case here you modify the parameters of the function and call it again with the modified parameters, possibly also returning a part of the result.

You need two sub branches at the recursive branch. One if you've found a prime factor, and another if the current number is no prime factor.

Here is a skeleton, you need to fill in the parts in the <> brackets.

primeFactsWith :: Integer -> [Integer] -> [Integer]
primeFactsWith n (p:ps) = if <halt condition> then
                            <final result>
                          else if (rem n p /= 0) then
                            <not a factor - recursive call 1>
                          else 
                            <found a factor - return it, 
                             and make recursive call 2>

• If you have found a prime factor, you can divide the number by it, to get a smaller number, without that factor. To perform integer division Haskell provides a function named div.

• If you reach the number 1, you have generated all prime factors and you can stop. The final part of a prime factors list, that comes after all its factors, is an empty list.

• You can drop any prime from your infinite list if you no longer need it, but be aware that a number could contain a prime several times in the factors list. If you want to drop p you can just use ps, from the pattern; if you want to keep p you must use (p:ps).

• The cons operator (:) can be used to build a list. You can use it to return one number of the result list, and use a recursive call to find the remaining numbers, e.g.

  x : foo y z

I hope that helps, if you have any questions don't hesitate to ask.