CODEWITHSUNDEEP
haskellsemantics
paulgavrikov
paulgavrikov

Reputation: 1891

Haskell: what does this method do

In my test-exam a question was, what this method does.

dos a = ([x | x <- [2..div a 2], mod a x == 0] == [])

I am new to Haskell but as far as I can say, it checks if the result of dos a = ([x | x <- [2..div a 2], mod a x == 0]) is an empty list. Also x are all numbers of a divided by 2 which have %number == 0. Thus this are all even numbers? It seems like it checks if the number is dividable through 2, if yes -> false, else otherwise. Could anyone explain to me the semantic in detail?

Upvotes: 2

Views: 170

Answers (2)

sabauma
sabauma

Reputation: 4253

You are close to what is going on. There are several components to understand.

First, [2 .. div a 2] generates a list of numbers from 2 to floor(a / 2).

Next, mod a x == 0 filters out the values from 2 to floor(a / 2) which divide a (e.g. it finds all the factors of a). Thus, the list generated by

[x | x <- [2 .. div a 2], mod a x == 0]

contains all the numbers that divide a.

Finally, the == [] checks that this list is empty (e.g. a has no factors). So, what this function actually does is to determine whether or not a number is prime by attempting to generate its factors, which is easy to see when you use dos as the predicate for filter:

Prelude> let dos a = ([x | x <- [2..div a 2], mod a x == 0] == [])
Prelude> :t dos
dos :: Integral t => t -> Bool
Prelude> filter dos [2 .. 100]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97] -- Prime goodness

Upvotes: 9

Satvik
Satvik

Reputation: 11218

It is the basic algorithm to check if a number is prime or not. It traverses over all the numbers from 2 to a/2 and checks if any of it divides a, if the list is empty then it means it has no factors between 2 and a/2 which implies the number is prime.

Upvotes: 5

Related Questions