Making a list of divisors without dividing sequentially in Haskell

Question

I am studying in Haskell.

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

Code:

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

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

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

Update:

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]

Answer 1

With this code:

import Data.List (group)
import Control.Arrow ((&&&))

divisors n = foldr go [1] . map (head &&& length) . group $ fac n 2
    where
    go (_, 0) xs = xs
    go (p, k) xs = let ys = map (* p) xs in go (p, pred k) ys ++ xs
    fac n i
        | n < i * i      = if n == 1 then [] else [n]
        | n `mod` i == 0 = i: fac (n `div` i) i
        | otherwise      = fac n $ succ i

you will get:

\> -- print timing/memory stats after each evaluation
\> :set +s
\> length $ divisors 260620460100
2187
(0.01 secs, 0 bytes)
\> length $ divisors 1000000007  -- prime number
2
(0.08 secs, 13,678,856 bytes)

you may compare with your implementation.

Answer 2

My own implementation uses power set of prime factors now.

For example, to get list of divisors of 30, which prime factor is [2,3,5],

1. make the power set of prime factors, [[],[2],[3],[5],[2,3],[2,5],[3,5],[2,3,5]]
2. product each elements and get result [1,2,3,5,6,10,15,30], which is list of divisors of 30

Code:

divisors :: Integral a => a -> [a]
divisors n
  | n < 1 = []
  | otherwise = distinct $ map product $ (powerset . factors) n

-- | remove duplicated element in a list
distinct :: Eq a => [a] -> [a]
distinct [] = []
distinct (x : xs)
  | x `elem` xs = distinct xs
  | otherwise = x : distinct xs

-- | generate power set of a list
powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (x : xs) = xss ++ map (x :) xss where xss = powerset xs

-- | generate prime factors of a integer
factors :: Integral a => a -> [a]
factors m = f m (head primes) (tail primes) where
  f m n ns
    | m < 2 = []
    | m < n ^ 2 = [m]
    | m `mod` n == 0 = n : f (m `div` n) n ns
    | otherwise = f m (head ns) (tail ns)

-- | prime sequence
primes :: Integral a => [a]
primes = 2 : filter (\n-> head (factors n) == n) [3,5..]

In this code, duplicated divisors appear if duplicated prime factors exist.
I remove duplicated divisors at last step, but it does not fix basic cause of duplication.
I feel sure that there are more smart ways.

Note:

• primes and factors are referred from Prime factors in Haskell.
• powerset is referred from powerset.

---

Update:

Thanks to comingstorm's advice, I studied more about Data.List module and update my code:

import Data.List (group, subsequences)

divisors :: Integral a => a -> [a]
divisors = map product . concatMap sequence . subsequences . map (scanr1 (*)) . group . factors

primes = ...    -- same as before

factors m = ... -- same as before

I noticed that distinct and powerset in original code are same with nub and subsequences in Data.List module.
It becomes simple but behzad.nouri's code is much faster.

Answer 3

The obligatory monadic code:

import Control.Monad

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

The factors as in your other linked question.

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

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.