Haskell中的主要分解要返回赋予数字和功率的元素列表

Question

我一直在尝试通过尝试一些简单的问题来学习Haskell。

;

目前，我正在尝试实现函数 primeFactorization :: Integer - ＆gt [（整数，整数）] ，使输出是包含质量因子及其在数字中提高功率的元组列表。

示例输出

＆gt; PrimeFactorization 120
[（2,3），（3,1），（5,1）] 自120 = 2^3 * 3 * 3^1 * 5^1

我的（部分）解决方案

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)

这是一个工作实现获得数字的主要因素。但是，如下所见，它仅输出主要因素。我不确定如何将次数存储在Haskell中。另外，考虑到在Haskell中进行迭代是不合时宜的，我不知道如何实施该解决方案。在Python中，我会这样做：

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

因此，问题：如何实现主要因素的功能？

注意：

1. 我已经看到了：阶乘分解，但这并没有回答我的问题。
2. 这不是家庭作业问题，我正在独立学习。

Answer 1

您始终可以用递归替换命令式循环（只要它们不介入任何全球状态）。这可能不是最优雅的方法，但是在这种情况

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

下辅助功能并在累加器变量上向前计算，但这更尴尬，我认为在这种情况下没有记忆/性能的好处可以证明它是合理的。）

您可以将其与您的Haskell代码（对于您已经找到的每个因素，检查一次发生的频率）或扩展它，以便整个事情都像Python解决方案一样工作（实际上更有效，因为它避免了每个数字检查是否检查是否检查这是PRIME）。为此，您只需要在结果中回馈最终 n 。让我们使用一个 where 块来处理模式匹配，还可以使 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

然后：与您的python代码相等的是，

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

这实际上为您提供了，例如在Python中，列表还包括非各个人（具有功率0）。为了避免这种情况，将列表构建更改为

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