Why does my first factorization function add 1 to the result?
I am creating a function to factorize any given number in haskell. And so I 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 adds 1 to the end of the list, for example factorize 80
will provide this list: [2,2,2,2,5,1]
My question is: why is this happening?
source to share
This comes from two pieces of code. First, factorize 1
- [1]
. Second, since it x
always divides on its own, your final call will always have w == x
, so the recursion will w:(factorize (w `div` w))
always be w:(factorize 1)
.
To fix this problem, you can simply add an extra base case to throw out the factors 1
:
factorize 1 = []
factorize ...
Alternatively, you can opt out of the case factorize 2 = [2]
because it is added to the case otherwise
you already have.
factorize 1 = []
makes sense mathematically because it 1
has no primary factors (remember that 1 is not a prime number!). This follows the same logic as product [] = 1
- 1
- this is the identity for multiplication, which makes it the default when you have nothing to multiply.
source to share