# 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.