I have been trying to learn haskell by trying to do some simple problems.

The Problem

Currently, I am trying to implement a function primeFactorization :: Integer -> [(Integer, Integer)] such that the output is a list of tuples containing the prime factor and the power it is raise to in the number.

Example Output

> primeFactorization 120
[(2,3), (3,1), (5,1)] since 120 = 2^3 * 3^1 * 5^1

My (Partial) Solution

primeFactorization :: Integer -> [Integer]
primeFactorization n = 
    let
        factors :: Integer -> [Integer]
        factors n = [x | x <- [2..n-1], n `mod` x == 0]

        isPrime :: Integer -> Bool
        isPrime n
            | n `elem` [0, 1] = False
            | n == 2 = True
            | n > 2 = null [ x | x <- [2..(ceiling . sqrt . fromIntegral) n], n `mod` x == 0]
            | otherwise = False
    in
        filter isPrime $ (factors n)

This is a working implementation to get the prime factors of a number. However as seen it only outputs the prime factors. I am not sure on how to store the number of times in haskell. Also, considering it is un-idiomatic to iterate in haskell I don't know how I would implement the solution. In python, I would do:

def pf(number):
    factors=[]
    d=2
    while(number>1):
        while(number%d==0):
            factors.append(d)
            number=number/d
        d =1
    return factors

So, the question: How to implement the powers of the prime factors?

NOTE:

1. I already saw: Prime factorization of a factorial however that does not answer my question.
2. This is NOT a homework problem, I am learning independently.

CodePudding user response：

You can always replace imperative-language loops (as long as they don't meddle with any global state) with recursion. That may not be the most elegant approach, but in this case it seems perfectly appropriate to imitate your inner Python loop with a recursive function:

dividerPower :: Integer -> Integer -> Int
dividerPower n d
  | n`rem`d == 0  = 1   dividerPower (n`quot`d) d
  | otherwise     = 0

(This counts “backwards” compared to the Python loop. You could also make it tail-recursive with a helper function and count forwards over an accumulator variable, but that's more awkward and I don't think there's a memory/performance benefit that would justify it in this case.)

You can either use that together with your Haskell code (for each of the factors you've already found, check how often it occurs), or extend it so the whole thing works like the Python solution (which is actually a lot more efficient, because it avoids for every number checking whether it's prime). For that you just need to give back the final n in the result. Let's use a where block for handling the pattern matching, and also make the rem and:

dividePower :: Integer -> Integer -> (Integer, Int)
dividePower n d
  | r == 0     = (nfin, p' 1)
  | otherwise  = (n, 0)
 where (n', r) = n `quotRem` d
       (nfin, p') = dividePower n' d

Then the equivalent to your Python code is

pf :: Integer -> Integer -> [(Integer, Int)]
pf = go 2
 where go d n
         | n>1        = (d, p) : go (d 1) n'
         | otherwise  = []
        where (n', p) = dividePower n d

This actually gives you, like in Python, the list including also non-dividers (with power 0). To avoid that, change the list-building to

         | n>1        = (if p>0 then ((d,p):) else id) $ go (d 1) n'