Sergey V. Mikhanov wrote:
factors :: Integer -> [Integer] factors n = doFactors n (eratosthenesFilter [1..n])
doFactors n primes | null newPrimes = [] | otherwise = let topPrime = head newPrimes in if topPrime == n then [topPrime] else topPrime : (doFactors (n `quot` topPrime) primes) where newPrimes = snd $ break (\x -> (n `rem` x) == 0) primes
eratosthenesFilter :: [Integer] -> [Integer] eratosthenesFilter [] = [] eratosthenesFilter (num : nums) | num == 1 = eratosthenesFilter nums | otherwise = num : (eratosthenesFilter $ doFilter num nums) where doFilter num nums = filter (\x -> x > num && (x `rem` num) /= 0) nums
What would you do different (including stylistic changes)? What are the general comments about efficiency (not of the algorithm, but of the implementation: for example, is it fine to use break at every invocation of doFactors?) and elegance of the solution?
Stylistically, one usually uses shorter variable names in Haskell. Also, the guards in doFactors are better expressed as pattern matching and the if can be turned into guards. factors :: Integer -> [Integer] factors n = go n $ eratosthenes [2..n] where go n [] = [] go n (p:ps) | n `mod` p == 0 = p : go (n `div` p) ps | otherwise = go n ps eratosthenes :: [Integer] -> [Integer] eratosthenes [] = [] eratosthenes (p:ps) = p : erathostenes ps' where ps' = filter (\x -> x > p && (x `mod` p) /= 0) ps Other than that, efficiency is best understood as algorithmic efficiency; there are not straightforward "tweaks" that give you the warm fuzzy feeling of "writing efficient code". Regards, apfelmus -- http://apfelmus.nfshost.com