haskell:自然数的因数

Question

我正在尝试在 Haskell 中编写一个函数来计算给定数字除自身以外的所有因数。

结果应该是这样的:

factorlist 15 => [1,3,5]

我是 Haskell 和整个递归主题的新手，我很确定我应该在这个例子中应用它，但我不知道在哪里或如何应用。

我的想法是将给定数字与从 1 到 n div2 的列表的第一个元素进行比较使用 mod 函数，但以某种方式递归，如果结果为 0，则我将数字添加到新列表中。 (我希望这是有道理的)

我将不胜感激在这件事上的任何帮助

到目前为止，这是我的代码:(它不起作用..但以某种方式来说明我的想法)

 factorList :: Int -> [Int]
 factorList n  |n `mod` head [1..n`div`2] == 0 = x:[]

Answer 1

有几种方法可以处理这个问题。但首先，让我们写一个小 helper :

isFactorOf :: Integral a => a -> a -> Bool
isFactorOf x n = n `mod` x == 0

这样我们就可以写12 `isFactorOf` 24并获得 True或 False .对于递归部分，假设我们使用一个带有两个参数的函数:一个是我们要分解的数字，第二个是我们当前正在测试的因子。我们只测试小于或等于 n `div` 2 的因素，这导致:

createList n f | f <= n `div` 2 = if f `isFactorOf` n
                                     then f : next
                                     else next
               | otherwise      = []
    where next = createList n (f + 1)

所以如果第二个参数是n的因数，我们将它添加到列表中并继续，否则我们就继续。只要 f <= n `div` 2 我们就这样做.现在为了创造factorList ，我们可以简单地使用 createList具有足够的第二个参数:

factorList n = createList n 1

递归隐藏在createList中.因此，createList是 worker , 你可以将它隐藏在 where 中factorList 内部.

请注意，可以很容易地定义 factorList使用过滤器或列表理解:

factorList'  n = filter (`isFactorOf` n) [1 .. n `div` 2]
factorList'' n = [ x | x <- [1 .. n`div` 2], x `isFactorOf` n]

但在这种情况下，您不会自己编写递归。

进一步练习:

• 尝试实现 filter自己发挥作用。
• 创建另一个函数，它只返回质数 个因子。您可以使用之前的结果并编写一个质数过滤器，或者编写一个递归函数来直接生成它们(后者更快)。