[Haskell-beginners] Re: Integer factorization

[Heinrich Apfelmus]

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