Discussion:
Convert Python to Haskell
(too old to reply)
leonadavinci
2009-05-19 16:54:20 UTC
Permalink
Hello,

I have created this code that generates Perfect Numbers in python. I
decided to learn Haskell so I would like to see if Haskel can create
more easily the same program. In addition how can I measure time in
Haskell. In python I have the timeit function which measure my code
for 9.6 seconds when n=9000.

Code follows:

def isdivisor(x,y):
if y!=0:
s=x%y
if s==0:
return True
else:
return False
else:
raise ZeroDivisionError




def isdivisableby2(x):
if x%2 == 0:
return True
else: return False

class perfectGenerator:
def __init__(self,n):
self.pinakas=list(range(1,n))

def sumdivisors(self,x):
return sum([_ for _ in self.pinakas[0:x-1] if isdivisor(x,_)])

def isPerfect(self,x):
if isdivisableby2(x) and self.sumdivisors(x)==x:
return True
else: return False

def generatePerfect(self):
return [x for x in self.pinakas if self.isPerfect(x)]
Mensanator
2009-05-19 17:41:25 UTC
Permalink
Post by leonadavinci
Hello,
I have created this code that generates Perfect Numbers in python. I
decided to learn Haskell so I would like to see if Haskel can create
more easily the same program. In addition how can I measure time in
Haskell. In python I have the timeit function which measure my code
for 9.6 seconds when n=9000.
        s=x%y
            return True
            return False
        raise ZeroDivisionError
        return True
    else: return False
        self.pinakas=list(range(1,n))
        return sum([_ for _ in self.pinakas[0:x-1] if isdivisor(x,_)])
            return True
        else: return False
        return [x for x in self.pinakas if self.isPerfect(x)]
The algorithm isn't going to work any better in Haskell.

Why not stay with Python and use a better algorithm?

import sympy
import time

t0 = time.time()
for n in xrange(2,9000):
d = sympy.divisors(n)
if sum(d[:-1])==d[-1]:
print '%6d perfect' % (n),d
t1 = time.time()

print t1-t0,'seconds'

## 6 perfect [1, 2, 3, 6]
## 28 perfect [1, 2, 4, 7, 14, 28]
## 496 perfect [1, 2, 4, 8, 16, 31, 62, 124, 248, 496]
## 8128 perfect [1, 2, 4, 8, 16, 32, 64, 127, 254, 508, 1016, 2032,
4064, 8128]
## 3.75 seconds

def isdivisor(x,y):
if y!=0:
s=x%y
if s==0:
return True
else:
return False
else:
raise ZeroDivisionError

def isdivisableby2(x):
if x%2 == 0:
return True
else:
return False

class perfectGenerator:
def __init__(self,n):
self.pinakas=list(range(1,n))

def sumdivisors(self,x):
return sum([_ for _ in self.pinakas[0:x-1] if isdivisor(x,_)])

def isPerfect(self,x):
if isdivisableby2(x) and self.sumdivisors(x)==x:
return True
else:
return False

def generatePerfect(self):
return [x for x in self.pinakas if self.isPerfect(x)]

print
print
print
t0 = time.time()
y = perfectGenerator(9000)
print y.generatePerfect()
t1 = time.time()
print t1-t0,'seconds'

## [6, 28, 496, 8128]
## 6.75 seconds
Ertugrul Söylemez
2009-05-19 18:24:04 UTC
Permalink
Post by Mensanator
Post by leonadavinci
Hello,
I have created this code that generates Perfect Numbers in python. I
decided to learn Haskell so I would like to see if Haskel can create
more easily the same program. In addition how can I measure time in
Haskell. In python I have the timeit function which measure my code
for 9.6 seconds when n=9000.
        s=x%y
            return True
            return False
        raise ZeroDivisionError
        return True
    else: return False
        self.pinakas=list(range(1,n))
        return sum([_ for _ in self.pinakas[0:x-1] if isdivisor(x,_)])
            return True
        else: return False
        return [x for x in self.pinakas if self.isPerfect(x)]
The algorithm isn't going to work any better in Haskell.
Why not stay with Python and use a better algorithm?
[...]
Because firstly the algorithm is much easier to express in Haskell than
in Python. Here it is:

divisors :: Integral i => i -> [i]
divisors n = filter (\d -> n `rem` d == 0) [1..n-1]

perfectNumbersUpTo :: Integral i => i -> [i]
perfectNumbersUpTo n = [ x | x <- [1..n], even x, sum (divisors x) == x ]

main :: IO ()
main = print $ perfectNumbersUpTo 9000

Secondly it runs much faster even than your "improved" variant, which is
even longer. The above program takes about 1.3 seconds with Integer
(i.e. big integers) and about 0.4 seconds if you replace the '9000'
above by '(9000::Int)', which makes it use machine words. Measurement
was done on my 2.7 GHz Athlon64 (in 32 bits mode) and I have not used
list parallelization. I could speed this up either by using the
single-threaded RTS or by using parallelization constructs.

However, your point that the algorithm is the tightest bottleneck of
course still holds, so here is my improved variant:

import Data.List

wheel :: Integral i => [i]
wheel = scanl (+) 2 $ [1,2] ++ cycle [2,4]

factorsFrom :: Integral i => [i] -> i -> [i]
factorsFrom (w:ws) n
| n == 1 = []
| rem n w == 0 = w : factorsFrom (w:ws) (div n w)
| otherwise = factorsFrom ws n

factors :: Integral i => i -> [i]
factors = factorsFrom wheel

divisors :: Integral i => i -> [i]
divisors = nub . map product . init . subsequences . factors

perfectNumbersUpTo :: Integral i => i -> [i]
perfectNumbersUpTo n = [ x | x <- [1..n], even x, sum (divisors x) == x ]

main :: IO ()
main = print $ perfectNumbersUpTo 9000

This variant uses wheel factorization to find the factors and then finds
the list of divisors through the list of products of all subsets of
factors (except the largest). On the same machine, again without
parallelization, it takes about 120 ms with Integer (i.e. bigint) and 77
ms using Int (i.e. machine int).

Yet the algorithm is much more concise than anything you could ever come
up with in Python.


Greets,
Ertugrul.
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/
Dirk Thierbach
2009-05-19 19:03:48 UTC
Permalink
Post by leonadavinci
I have created this code that generates Perfect Numbers in python. I
decided to learn Haskell so I would like to see if Haskel can create
more easily the same program. In addition how can I measure time in
Haskell. In python I have the timeit function which measure my code
for 9.6 seconds when n=9000.
Ok. Since this is for learning Haskell, here's a one-to-one translation
Post by leonadavinci
s=x%y
return True
return False
raise ZeroDivisionError
isDivisor x 0 = error "Division by Zero"
isDivisor x y = x `mod` y == 0
Post by leonadavinci
return True
else: return False
isDivisableBy2 x = x `mod` 2 == 0
Post by leonadavinci
self.pinakas=list(range(1,n))
return sum([_ for _ in self.pinakas[0:x-1] if isdivisor(x,_)])
sumDivisors x = sum [d | d <- [1..x-1], isDivisor x d]

(This will raise an error if d=0, so we start at 1 instead of 0).
Post by leonadavinci
return True
else: return False
isPerfect x = isDivisableBy2 x && sumDivisors x == x
Post by leonadavinci
return [x for x in self.pinakas if self.isPerfect(x)]
generatePerfect n = [x | x <- [1..n], isPerfect x]


Since all these functions are quite short, in more idiomatic Haskell
one would inline the first functions, and drop the unnecessary
division by 2 test:

isPerfect x = x == sum [d | d <- [1..x-1], x `mod` d == 0]

One can also generate an infinite (lazy) list of all perfect numbers:

perfect = [x | x <- [1..], isPerfect x]

Test:

*Main> take 3 perfect
[6,28,496]

For timing, interpreted Haskell is significantly slower than compiled
Haskell, so I usually only time compiled Haskell. On my old and slow
computer at home, with n=9000 get 55.1s for your python code and

$ time ./xxx
[6,28,496,8128]

real 0m30.862s
user 0m26.130s
sys 0m0.828s

using the Linux "time" command. If you insist on doing it in Haskell,
there's the System.Time module for the computer clock and the
System.Posix.Process module for the process timing info.

Of course, as already has been mentioned, using smarter algorithms
will make the whole thing significantly faster in any language,
especially for larger numbers.

- Dirk
Ertugrul Söylemez
2009-05-19 19:20:04 UTC
Permalink
Post by Dirk Thierbach
Since all these functions are quite short, in more idiomatic Haskell
one would inline the first functions, and drop the unnecessary
isPerfect x = x == sum [d | d <- [1..x-1], x `mod` d == 0]
The division by 2 made the algorithm almost twice as fast for me. But
since I haven't read about perfect numbers I'm not sure whether it
renders it incorrect. For the sake of benchmarking identical
algorithms, I have retained the evenness test.
Post by Dirk Thierbach
perfect = [x | x <- [1..], isPerfect x]
I really like to introduce the concept of higher order functions early
to beginning Haskell programmers. List comprehensions are fine, if you
have multiple guards, multiple lists or complicated formulas, but for
such simple cases I'd rather use:

perfectNumbers = filter isPerfect [1..]


Greets,
Ertugrul.
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/
Paul Rubin
2009-05-19 19:41:39 UTC
Permalink
Post by Ertugrul Söylemez
Post by Dirk Thierbach
isPerfect x = x == sum [d | d <- [1..x-1], x `mod` d == 0]
The division by 2 made the algorithm almost twice as fast for me.
OK:

isPerfect x = x == sum [d | d <- [2,4..x-1], x `mod` d == 0]
Dirk Thierbach
2009-05-19 20:31:33 UTC
Permalink
Post by Ertugrul Söylemez
The division by 2 made the algorithm almost twice as fast for me.
Of course, since you're only testing half as many numbers :-)
Post by Ertugrul Söylemez
But since I haven't read about perfect numbers I'm not sure whether
it renders it incorrect.
AFAIK it's unknown if there are odd perfect numbers.
Post by Ertugrul Söylemez
For the sake of benchmarking identical algorithms, I have retained
the evenness test.
Good point. Testing only even numbers, compiled Haskell is about 5
times faster than Python on my machine (which doesn't say a lot
because this is a toy example, but anyway).

Since we're now talking algorithms, I'd guess sieve-style calculation
of sigma_1 may be more efficient (though this uses array updates,
which is probably not the right topic for beginners).
Post by Ertugrul Söylemez
Post by Dirk Thierbach
perfect = [x | x <- [1..], isPerfect x]
I really like to introduce the concept of higher order functions early
to beginning Haskell programmers. List comprehensions are fine, if you
have multiple guards, multiple lists or complicated formulas, but for
perfectNumbers = filter isPerfect [1..]
I kept the list comprehension because Python programmers are already
familiar with that. There's enough time for HOFs later on, especially
since it looks like the OP hasn't written any Haskell at all yet.

- Dirk

Continue reading on narkive:
Loading...