Output of a list of Maybe Int with Just in every element in Haskell

Question

I have this function which takes an integer n and returns a list of type Maybe Int, containing the unique prime factors. I don't understand why it returns them with Just inside every element of the list.

I expect an output like this:

primeFactors 75 = Just [3,5]

But I have one that looks like this:

primeFactor 75 = [Just 5,Just 3,Just 1]

Here is my code:

divides :: Int -> Int -> Bool
divides m n = rem m n == 0

transform :: Int -> Int
transform n = (n*2) + 1

isComposite :: Int -> Bool
isComposite n = foldl (||) (divides n 2) (map (divides n) (map (transform) [1..(div n 4)]))

isPrime :: Int -> Bool
isPrime n
 | n <= 0 = error "Makes no sense"
 | n < 4 = True
 | otherwise = not (isComposite n)

primeFactors :: Int -> [Maybe Int]
primeFactors 0 = [Nothing]
primeFactors n = primeFactors2 n ((div n 2)+1)

primeFactors2 :: Int -> Int -> [Maybe Int]
primeFactors2 n 0 = []
primeFactors2 n x
    | divides n x && isPrime x = Just x:primeFactors2 n (x-1)
    | otherwise = primeFactors2 n (x-1)

Answer 1

Here is a version of your code that I think will do what you want:

primeFactors :: Int -> Maybe [Int]
primeFactors n 
    | n <= 0 = Nothing
    | otherwise = Just $ primeFactors2 n n

primeFactors2 :: Int -> Int -> [Int]
primeFactors2 n p
    | n <= 1 || p <= 1 = []
    | divides n p && isPrime p = p : primeFactors2 (n `div` p) p
    | otherwise = primeFactors2 n (p-1)

isPrime :: Int -> Bool
isPrime n
 | n <= 1 = False
 | otherwise = not (isComposite n)

isComposite :: Int -> Bool
isComposite n = 
    any (divides n) [2..n-1]

divides :: Int -> Int -> Bool
divides m n = 
    rem m n == 0

Please note that (for clarity's sake I hope) I did remove some of your optimizations and made a major change: this one will report Just [2,2] as prime-factors for 4 (IMO you want product <$> primeFactors n == Just n).

If not (as your example indicates) it shouldn't be too hard to fix this (just take your version).

Anyway the only really interesting contribution is how primeFactor handles primeFactors2 to get you the Maybe result.