# The Sieve of Eratosthenes in Haskell: A naive implementation

I have been learning Haskell for a while. The more I am exposed to this language, the more I am amazed by the elegance of the functional programming paradigm. List comprehension is one of the beautiful things that I like in Haskell. Coming from Python, I am familiar with it. But the list comprehension in Haskell feels more natural because it is closer to what you would write in mathematics.

For example, in Python, multiple predicates in a list comprehension expression must be connected with logical operators. I can understand that is designed to be intuitive. But when you have many predicates nested under several for-expressions and if-expressions within a list comprehension, it can be ugly and difficult to read. I’m not saying list comprehension isn’t good in Python; it is good and powerful if you keep it simple. But in comparison, Haskell connects multiple predicates with commas and allows parallel comprehension (saves your a line of import itertools). This allows Haskell to be capable of doing complicated list comprehensions well without losing clarity.

A Haskell example I’d like to show is a naive implementation of the Sieve of Eratosthenes. With list comprehension, everything can fit into one line excepting the type declaration.

sievePrime :: Int -> [Int]
sievePrime n = [x | x <- [2..n], and [x mod y /= 0 | y <- [2..floor(sqrt(fromIntegral x))]]]

The equivalent Python version would be

def sievePrime(n):
return [x for x in range(2, n + 1) if all([x % y != 0 for y in range(2, int(x ** 0.5))])]

I feel that <- in Haskell is more elegant than for ... in ... in Python. The Haskell and, when used on a list, is equivalent to Python all(). The only thing I’m still struggling to get used to in Haskell is the lack of C-like implicit type promotion, i.e., you cannot simply add an integer and a floating-point number, unless the integer is cast to a floating-point number first to match the type signature of the operator. This means that an explicit type conversion using fromIntegral must be performed when applying sqrt on an integer here.