CODEWITHSUNDEEP
haskellprimes
NatureShade
NatureShade

Reputation: 2237

Why does my prime factorization function append 1 to the result?

I am creating a function to factorize any given number in haskell. And so i have created this:

primes :: [Integer]
primes = 2:(sieve [3,5..])
    where
        sieve (p:xs) = p : sieve [x |x <- xs, x `mod` ((p+1) `div` 2 ) > 0]


factorize 2 = [2]
factorize x
    | divisible x = w:(factorize (x `div` w))
    | otherwise   = [x]
    where
          divisible :: Integer -> Bool
          divisible y = [x |x <- (2:[3,5..y]), y `mod` x == 0] /= []

          firstfactor :: Integer -> [Integer] -> Integer
          firstfactor a (x:xs)
              | a `ifdiv` x = x
              | otherwise   = firstfactor a xs
          firstfactor a _ = a

          ifdiv x y = mod x y == 0

          w = firstfactor x primes

The function works fine, but appends 1 to the end of the list, for example factorize 80 would give this list: [2,2,2,2,5,1] My question is, why does this happen?

Upvotes: 3

Views: 103

Answers (1)

Tikhon Jelvis
Tikhon Jelvis

Reputation: 68152

This comes up from two parts of the code. Firstly, factorize 1 is [1]. Secondly, since x is always divisible by itself, your very final call will always have w == x, so the recursion will be w:(factorize (w `div` w)) which is always w:(factorize 1).

To solve this, you can just add an extra base case to throw out the factors of 1:

factorize 1 = []
factorize ...

Also, you can drop the factorize 2 = [2] case because it gets subsumed by the otherwise case you already have.

factorize 1 = [] makes sense mathematically, because 1 has no prime factors (remember that 1 is not a prime number itself!). This follows the same logic behind product [] = 1—1 is the identity for multiplication, which makes it the "default" value when you have nothing to multiply.

Upvotes: 4

Related Questions