Prime factorization of an integer

Question

I have just started learning functional programming (Haskell) for fun after using imperative languages my whole life. I am looking for quick and simple tips from pros on how the particular code I just wrote (a simple program solving a simple task - factoring an integer) can be simplified and made more beautiful.

-- FactorInt: Factoring n to prime integers
import Data.Maybe
-- Takes the head maybe
headMaybe :: [t] -> Maybe t
headMaybe [] = Nothing
headMaybe (x:_) = Just x
-- Takes the first available divizor
takeDivizor :: Int -> Maybe Int
takeDivizor n = headMaybe $ filter (\i -> n `mod` i == 0) $ takeWhile (\i -> i^2 <= n) [2..]
-- Takes the maximum power of k in n
maxPower :: Int -> Int -> Int
maxPower n k
 | (n `mod` k) /= 0 = 0
 | otherwise = 1 + maxPower (n `div` k) k
-- Factors an integer to a list of divizors
factorInt :: Int -> [(Int, Int)]
factorInt 1 = []
factorInt n = case (takeDivizor n) of
 Nothing -> [(n, 1)]
 Just a -> (a, k) : factorInt (n `div` a^k) where k = maxPower n a
-- Pretty printing powers
prettyPowers :: (Int, Int) -> String
prettyPowers (a, 1) = show a
prettyPowers (a, b) = (show a) ++ "^" ++ (show b)
-- Pretty printing factors
prettyFactors :: [(Int, Int)] -> String
prettyFactors factors = foldl1 (\ a b -> a ++ "*" ++ b) $ map prettyPowers factors
-- Program
main = do
 nStr <- getLine
 let n = read nStr :: Int
 putStrLn $ prettyFactors $ factorInt n

Answer 1

takeDivizor is not only misspelled, it is unnecessary and inefficient. It's unnecessary because maxPower is more general. (maxPower returning 0 is also preferable as it avoids the unwieldy Maybe.) It's inefficient because it tests factors starting from 2 with each call.

Here is a small-scale rewrite that eliminates takeDivizor.

factorInt :: Int -> [(Int, Int)]
factorInt 1 = []
factorInt n = factorInt' n (2 : [3, 5..])
 where
 factorInt' 1 _ = []
 factorInt' n a = case maxPower n a of
 0 -> factorInt' n as
 k -> (a, k) : factorInt' (n `div` a^k) as

---

If you are willing to decompose the problem differently, you can simplify it further by eliminating maxPower in favour of some list processing:

import Data.List (group, intercalate)
factorInt :: Int -> [Int]
factorInt 1 = []
factorInt n = factorInt' n (2 : [3, 5..])
 where
 factorInt' 1 _ = []
 factorInt' n a = case n `divMod` a of
 (d, 0) -> a : factorInt' d (a:as)
 (_, _) -> factorInt' n as
prettyFactors :: [Int] -> String
prettyFactors factors = intercalate "*" $ map prettyFactor $ group factors
 where
 prettyFactor [f] = show f
 prettyFactor fs = (show $ head fs) ++ "^" ++ (show $ length fs)

Note that this version produces an empty string when factoring 1.

Answer 2

The biggest issues I see look like unfamiliarity with base.

headMaybe already exists in Data.Maybe as listToMaybe.

takeDivisor is poorly named (take from what?) and not very Haskell-y. A well realized Haskell version would be defined as listToMaybe . divisors where divisors is a function that returns all of the divisors of a number. However this still isn't quite the right definition because every number is divisible by at the very least 1 and itself (and you skip returning 1) so you're really looking for the first prime factor.

divisors :: Int -> [Int]
divisors n = filter (\i -> n `mod` i == 0) [1..n]
firstPrimeFactor :: Int -> Maybe Int
firstPrimeFactor = listToMaybe . init . tail . divisors

Note that the divisors now start at 1 and end at n, so firstPrimeFactor includes init . tail in its function composition pipeline. The inclusion of tail should be obvious, it causes 1 to be excluded from the list of divisors. init is there in case n is prime, that way n itself isn't included in the list and we get back Nothing.

Note also that in your original version using takeWhile caused many evaluations of i^2 <= n. Instead of testing the elements of the list of possible divisors an important optimization is to cap the list range to floor (sqrt n). Of course if we start getting mathematically rigorous in our optimizations there are many better ways to calculate prime factors (including starting with a list of actual primes), so let's not get lost in the weeds.

An alternate way to implement firstPrimeFactor that is closer to your original takeDivisor would be to use find from Data.List. I think this version is important for two reasons. One, there really is a function for everything in base; learn it, love it, live it. And two, this implementation reads the most like prose to me, readable code is maintainable and beautiful.

firstPrimeFactor :: Int -> Maybe Int
firstPrimeFactor n = find (\d -> n `rem` d == 0) [2..floor (sqrt n)]

(It would be even better with "primes" in place of the range, given a top-level list of prime values by that name.)

• 200_success: You need [2..floor $ sqrt $ fromIntegral n], else you get the error No instance for (Floating Int) arising from a use of ‘sqrt’.

Answer 3

Your code all looks clear and readable to me. This is basically all performance-related.

It's "divisor"

since you're not dealing with negatives, you can use the more efficient rem and quot instead of the more mathematically correct mod and div.
factorInt 1 should be [(1,1)].

In your prettyFactors method you're creating a bunch of left-nested ++'s. This leads to a quadratic complexity printing method. You can use foldr1 to switch them to right-nested ++'s and get linear time, or you could look into the showS trick. (this won't really matter since by the time your printing takes a noticeable amount of time the factorization will be taking ages.)
Addendum: In most cases foldl and foldl1 are not what you want. You usually use foldr or foldr1 when you want laziness and foldl' or foldl1' when you want strictness.

Every time you use factorInt you start takeDivizor at 2, despite the fact that you might have already tried 2,3,4.. on previous iterations. The simplest way to remedy this would be to just add a parameter to each of them telling them where to start looking for factors.

You check a lot of numbers you don't have to in your takeDivizor function, you really only need to look at a list of primes, not [2..]

You could modify maxPower to make it tail-recursive.

If I were to write this, I would probably leave out the headMaybe and takeDivizor and write factorInt something like this.

primes = 2 : [ p | p <- [3,5..], all (\x -> rem p x /= 0) (takeWhile (\x -> x^2 <= p) primes ]
factorInt :: Int -> [(Int,Int)]
factorInt 1 = [(1,1)]
factorInt n = f n primes where
 f n (p:ps) | n < x = []
 | otherwise = let mp = maxPower n p in (p, mp) : f (quot n (p^mp)) ps

Note that my implementation of primes is far from optimal, you can find better implementations on the haskell wiki page for primes.