列出除数的列表，而无需在Haskell中按顺序划分 [英] Making a list of divisors without dividing sequentially in Haskell

问题描述

我正在Haskell学习.

I am studying in Haskell.

我一直在实现一个列出除数列表的函数.
我的第一个代码在这里:

I have been implementing a function making a list of divisors.
My first code is here:

代码:

divisors :: Integral a => a -> [a]
divisors n
  | n < 1 = []
  | otherwise = filter ((== 0) . (mod n)) [1..n]

此代码几乎与在Haskell中列出除数 a>.
可以，但是很慢.

This code is almost same as Making a list of divisors in Haskell.
It works but slow.

我觉得除以每个[1..n]效率不高.
是否有另一种聪明的方法来列出除数的列表?

I feel it is not efficient to divide by each of [1..n].
Is there another smart way to making a list of divisors?

更新:

对于n < 1，[1..n]与[]相同.
因此，根本不需要警卫:

In the case of n < 1, [1..n] is the same as [].
So, guard is not required at all:

divisors :: Integral a => a -> [a]
divisors n = filter ((== 0) . (mod n)) [1..n]

推荐答案

强制性单子代码:

import Control.Monad

divisors = map product . mapM (scanl (*) 1) . group . factors

factors与您其他链接的问题相同.

The factors as in your other linked question.

您已经在使用List monad中的sequence，无需显式调用concatMap(mapM f等同于sequence . map f).

You are already using sequence from List monad, no need to invoke concatMap explicitly (mapM f is equivalent to sequence . map f).

不过，列表不会排序，就像原始的按顺序划分的 O(n)代码生成的列表是—一样.顺便说一句，您可以使用足够简单的技巧使其成为 O(sqrt(n))，尽管平均而言，它仍然比此代码慢得多.

The list won't be ordered though, like the one produced by your original sequentially-dividing O(n) code is — you could make it O(sqrt(n)) with a simple enough trick by the way, though it would still be much slower than this code, on average.

这篇关于列出除数的列表，而无需在Haskell中按顺序划分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！