Prime factorization of an integer 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] -&gt; Maybe t
headMaybe [] = Nothing
headMaybe (x:_) = Just x

-- Takes the first available divizor
takeDivizor :: Int -&gt; Maybe Int
takeDivizor n = headMaybe $ filter (\i -&gt; n `mod` i == 0) $ takeWhile (\i -&gt; i^2 &lt;= n) [2..]

-- Takes the maximum power of k in n
maxPower :: Int -&gt; Int -&gt; 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 -&gt; [(Int, Int)]
factorInt 1 = []
factorInt n = case (takeDivizor n) of
    Nothing -&gt; [(n, 1)]
    Just a  -&gt; (a, k) : factorInt (n `div` a^k) where k = maxPower n a

-- Pretty printing powers
prettyPowers :: (Int, Int) -&gt; String
prettyPowers (a, 1) = show a
prettyPowers (a, b) = (show a) ++ "^" ++ (show b)

-- Pretty printing factors
prettyFactors :: [(Int, Int)] -&gt; String
prettyFactors factors = foldl1 (\ a b -&gt; a ++ "*" ++ b) $ map prettyPowers factors

-- Program
main = do
    nStr &lt;- getLine
    let n = read nStr :: Int
    putStrLn $ prettyFactors $ factorInt n
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 &lt;- [3,5..], all (\x -&gt; rem p x /= 0) (takeWhile (\x -&gt; x^2 &lt;= p) primes ]

factorInt :: Int -&gt; [(Int,Int)]
factorInt 1 = [(1,1)]
factorInt n = f n primes where
  f n (p:ps) | n &lt; 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.