[Haskell-beginners] Perfect numbers
Ben Deane
haskell at elbeno.com
Thu Oct 2 03:14:23 EDT 2008
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
>
More information about the Beginners
mailing list