Записки начинающего функциональщика: простые числа

Всё-таки функ­ци­о­наль­ные язы­ки – это со­всем па­рал­лель­ная все­лен­ная. И один из са­мых па­рал­лель­ных язы­ков в ней – Haskell.

За­хо­те­лось нам вве­сти в про­грам­му бес­ко­неч­ный спи­сок про­стых чи­сел:

Бу­дем поль­зо­вать­ся сле­ду­ю­щи­ми пра­ви­ла­ми:

• если чис­ло со­став­ное, то оно обя­за­тель­но име­ет де­ли­тель мень­ший либо рав­ный кор­ню это­го чис­ла.
• по­иск де­ли­те­лей оче­ред­но­го чис­ла бу­дем ве­сти сре­ди ра­нее най­ден­ных про­стых чи­сел.

Функ­ция про­вер­ки чис­ла на про­сто­ту (x – чис­ло, lst – спи­сок ра­нее най­ден­ных про­стых чи­сел):

prime x lst
    | x < (head lst)*(head lst) = True
    | mod x (head lst) == 0     = False
    | otherwise                 = prime x (tail lst)

И те­перь опре­де­ля­ем сам бес­ко­неч­ный спи­сок:

primesList = 2:[x | x <- [3,5..], prime x primesList]

Всё! Те­перь мо­жем поль­зо­вать­ся этим спис­ком, на­при­мер по­лу­чить спи­сок пер­вых два­дца­ти про­стых чи­сел:

> take 20 primesList
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]

По­тря­са­ю­щая гиб­ко­сти и вы­ра­зи­тель­ная мощь язы­ка!

Те­перь по­про­бу­ем на ос­но­ве это­го спис­ка со­здать бес­ко­неч­ный спи­сок пар­ных про­стых чи­сел (от­ли­ча­ю­щих­ся на 2):

isPair (a,b) =
    if b - a == 2 then True
    else False
primesPair = [(a,b) | (a,b) <- zip primesList (tail primesList), isPair (a,b)]

Пер­вые 5 пар­ных про­стых чи­сел:

> take 5 primesPair
[(3,5),(5,7),(11,13),(17,19),(29,31)]