[Haskell-beginners] Re: Integer factorization
Heinrich Apfelmus
apfelmus at quantentunnel.de
Tue Mar 10 14:50:11 EDT 2009
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
More information about the Beginners
mailing list