On 10/2/2008, "Ben Deane"
On Thu, 2008-10-02 at 05:45 +0100, Matthew Williams wrote:
Hi Guys,
I'm new to Haskell and I was wondering if you can help me:
One of the first program's I tend to write when I'm looking at a new language is a program to generate a list of perfect numbers:
--My First Perfect Number Generator factors :: Integer -> [Integer] factors x = [z | z <- [1..x-1], x `mod` z == 0]
Hi Matthew,
A big optimization for larger numbers is that you only need to go up to the square root of x here and add both z and x/z to the list. (Where x is a perfect square you need to avoid adding the root twice.) It's late and there is probably a better way to do this, but:
import List
semi_factors :: Int -> [Int] semi_factors x = takeWhile (\n -> n * n <= x) [z | z <- [2..x-1], x `mod` z == 0]
factors n = let xs = semi_factors n in nub (1 : (xs ++ (map (n `div`) xs)))
is_perfect :: Integer -> Bool is_perfect x = if sum(factors x) == x then True else False
"if <something> then True else False" should ring alarm bells! Immediately replace with simply "<something>":
is_perfect x = sum (factors x) == x
you could also use
is_perfect x = foldl' (+) 0 (factors x) == x
(strict foldl from Data.List)
do_perfect :: [Integer] -> [Integer] do_perfect x = [z |z <- x, is_perfect z ]
Then to run it:
do_perfect [1..9000]
I think more idiomatic would be:
do_perfect x = filter is_perfect [2..x]
All this speeds it up a bit. But I can't think any more - time to sleep.
thanks Ben
I'm using GHC to run it. My problem / question is this: It's running
quite a lot slower than equivalent programs in erlang and python. I suspect it's down to the way I've written it. Any thoughts (or comments in general)
Many thanks
Matt
This isn't really important for this application, because the numbers being factored are relatively small, but there are some inefficiencies in the factors function that Ben presented that are fairly easy to overcome. Here's my version: factors :: (Integral a) => a -> [a] factors n = let p1 = [x | x <- [1 .. floor $ sqrt $ fromIntegral n], n `mod` x == 0] p2 = map (div n) (tail p1) in p1 `concatNoDupe` (reverse p2) where concatNoDupe :: (Eq a) => [a] -> [a] -> [a] concatNoDupe [] ys = ys concatNoDupe [x] (y:ys) = if x == y then (y : ys) else (x : y : ys) concatNoDupe (x:xs) ys = x : (concatNoDupe xs ys) Since my two lists of factors are ordered, I can exploit this to avoid calling nub and instead call 'concatNoDupe' which is more efficient. The other thing I optimized was the creation of the list of potential factors. Ben's solution required the evaluation of a predicate for each element in the list. My solution simply computes the maximum value of the list up front. To demonstrate how these changes affect performance, when I run this on my computer: main = print $ sum $ concat $ map factors [1..80000] Matthew's version: 194 seconds Ben's version: 32 seconds My version: 1 second I don't mean to suggest that my version is optimal. I just want to point out that seemingly small changes to an algorithm can have large consequences. David