在Haskell中的质因数分解函数

Question

我正在尝试创建一个函数，使用我提供的列表（无限）显示一个数字的质因数。以下是我目前的代码：

-- Here is a much more efficient (but harder to understand) version of primes.
-- Try "take 100 primes" as an example (or even more if you like)
primes = 2 : primesFrom3 where 
    primesFrom3 = sieve [3,5..] 9 primesFrom3
    sieve (x:xs) b ~ps@(p:q:_)
      | x < b     = x : sieve xs b ps
      | otherwise =     sieve [x | x <- xs, rem x p /= 0] (q^2) (tail ps)



-- Write a function that factors its first argument using the (infinite)
-- list of available factors given in its second argument
-- (using rem x p /= 0 to check divisibility)
primeFactsWith :: Integer -> [Integer] -> [Integer]
primeFactsWith n (p:ps) = if (rem n p /= 0) then
                                (primeFactsWith n ps)
                          else (primeFactsWith p ps)

上半部分不是我写的，但是可以正常工作。我正在尝试让下半部分工作，但它没有。请阅读代码中的注释，以更好地理解我要做什么。谢谢！顺便说一句，请不要直接给出答案。给我一些提示，告诉我如何做以及可能出了什么问题。

- eLemonnader

---

你也可以尝试使用 primes = 2 : 3 : sieve [5,7..] 9 primesFrom3 where ...，并比较在 main = print (primes !! n) 中增加 n 的 内存使用（以及时间）。使用优化开关 -O2 编译成独立可执行文件运行 ($> primes +RTS -s 查看统计信息)。 - Will Ness

Answer 1

问题所在

问题在于在两个分支中都进行了递归调用，因此函数永远不会停止。

一些提示

要构建一个递归生成列表的函数，您需要两个分支或情况：

• 基本情况没有递归调用，这将停止递归并返回结果的最终部分。
• 递归情况在这里，您修改函数的参数并使用修改后的参数再次调用它，可能还返回结果的一部分。

在递归分支中，您需要两个子分支。一个是如果找到了质数因子，另一个是当前数字不是质数因子。

这里是一个框架，您需要填写<>括号中的内容。

primeFactsWith :: Integer -> [Integer] -> [Integer]
primeFactsWith n (p:ps) = if <halt condition> then
                            <final result>
                          else if (rem n p /= 0) then
                            <not a factor - recursive call 1>
                          else 
                            <found a factor - return it, 
                             and make recursive call 2>

• 如果你已经找到一个质因数，你可以用它来除以这个数，得到一个没有该因数的更小的数。为了进行整数除法，Haskell提供了一个名为div的函数。

• 如果你到达了数字1，那么你已经生成了所有的质因数，可以停止了。质因数列表的最后一部分，在所有因数之后，是一个空列表。

• 如果你不再需要无限列表中的任何质数，你可以将其删除，但要注意一个数可能在因数列表中包含多个质数。如果你想删除p，你可以直接使用模式中的ps；如果你想保留p，你必须使用(p:ps)。

• cons运算符(:)可用于构建列表。你可以使用它来返回结果列表中的一个数字，并使用递归调用来查找剩余的数字，例如：

  x : foo y z

希望这有所帮助，如果您有任何问题，请随时问我。

- bmaderbacher

---

“p是一个整数，但n是一个整数列表。” 不对，根据primeFactsWith :: Integer -> [Integer] -> [Integer]，在primeFactsWith n (p:ps)中，n是一个Integer，p是一个Integer，而ps是[Integer]。 - rampion

你试图将p作为参数传递给primeFactors，但它期望的是[Integer]。OP确实将p作为参数传递给了primeFactsWith，但是在第一个位置。它期望的是一个Integer，而p就是一个Integer。 - rampion

我似乎误读了操作符的功能。关于类型不匹配的部分是无意义的，我会将其删除。我的回答的其他部分不应受到影响。 - bmaderbacher

Answer 2

这里有一个提示。

所以你正在进行递归，这是很好的。

在一个分支中，你继续寻找n的因子。在另一个分支中，你似乎在寻找p的因子，这有点奇怪，但无论如何。

你在哪里返回你找到的n的因子？

- rampion