https://wiki.haskell.org/api.php?action=feedcontributions&user=CliffyQS&feedformat=atomHaskellWiki - User contributions [en]2024-03-29T05:09:35ZUser contributionsMediaWiki 1.35.5https://wiki.haskell.org/index.php?title=Prime_numbers&diff=14649Prime numbers2007-07-24T15:31:51Z<p>CliffyQS: </p>
<hr />
<div>The following is an elegant (and highly inefficient) way to generate a list of all the prime numbers in the universe:<br />
<br />
<haskell><br />
primes = sieve [2..] where<br />
sieve (p:xs) = p : sieve (filter (\x -> x `mod` p > 0) xs)<br />
</haskell><br />
<br />
With this definition made, a few other useful (??) functions can be added:<br />
<br />
<haskell><br />
is_prime n = n `elem` (takeWhile (n >=) primes)<br />
<br />
factors n = filter (\p -> n `mod` p == 0) primes<br />
<br />
factorise 1 = []<br />
factorise n =<br />
let f = head $ factors n<br />
in f : factorise (n `div` f)<br />
</haskell><br />
<br />
(Note the use of <hask>takeWhile</hask> to prevent the infinite list of primes requiring an infinite amount of CPU time and RAM to process!)<br />
<br />
The following is a more efficient prime generator, implementing the sieve of<br />
Eratosthenes:<br />
<br />
<haskell><br />
merge xs@(x:xt) ys@(y:yt) = case compare x y of<br />
LT -> x : (merge xt ys)<br />
EQ -> x : (merge xt yt)<br />
GT -> y : (merge xs yt)<br />
<br />
diff xs@(x:xt) ys@(y:yt) = case compare x y of<br />
LT -> x : (diff xt ys)<br />
EQ -> diff xt yt<br />
GT -> diff xs yt<br />
<br />
primes, nonprimes :: [Int]<br />
primes = [2,3,5] ++ (diff [7,9..] nonprimes) <br />
nonprimes = foldr1 f . map g $ tail primes<br />
where f (x:xt) ys = x : (merge xt ys)<br />
g p = [ n*p | n <- [p,p+2..]]<br />
</haskell><br />
<br />
<hask>nonprimes</hask> effectively implements a heap, exploiting Haskell's lazy evaluation model. For another example of this idiom see the Prelude's <hask>ShowS</hask> type, which again exploits Haskell's lazy evaluation model<br />
to avoid explicitly coding efficient concatenable strings. This is generalized by the [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/dlist-0.3 DList package].<br />
<br />
<br />
== Bitwise prime sieve ==<br />
<br />
Count the number of prime below a given 'n'. Shows fast bitwise arrays,<br />
and an example of Template Haskell to defeat your enemies.<br />
<br />
<haskell><br />
{-# OPTIONS -O2 -optc-O -fbang-patterns #-}<br />
<br />
module Primes (pureSieve) where<br />
<br />
import Control.Monad.ST<br />
import Data.Array.ST<br />
import Data.Array.Base<br />
import System<br />
import Control.Monad<br />
import Data.Bits<br />
<br />
pureSieve :: Int -> Int<br />
pureSieve n = runST ( sieve n )<br />
<br />
sieve n = do<br />
a <- newArray (3,n) True :: ST s (STUArray s Int Bool)<br />
let cutoff = truncate (sqrt (fromIntegral n)) + 1<br />
go a n cutoff 3 1<br />
go !a !m cutoff !n !c<br />
| n >= m = return c<br />
| otherwise = do<br />
e <- unsafeRead a n<br />
if e then<br />
if n < cutoff<br />
then let loop !j<br />
| j < m = do<br />
x <- unsafeRead a j<br />
when x $ unsafeWrite a j False<br />
loop (j+n)<br />
<br />
| otherwise = go a m cutoff (n+2) (c+1)<br />
<br />
in loop ( if n < 46340 then n * n else n `shiftL` 1)<br />
else go a m cutoff (n+2) (c+1)<br />
<br />
else go a m cutoff (n+2) c<br />
<br />
<br />
</haskell><br />
<br />
And places in a module:<br />
<br />
<haskell><br />
{-# OPTIONS -fth #-}<br />
<br />
import Primes<br />
<br />
main = print $( let x = pureSieve 10000000 in [| x |] )<br />
</haskell><br />
<br />
Run as:<br />
<br />
<haskell><br />
$ ghc --make -o primes Main.hs<br />
$ time ./primes<br />
664579<br />
./primes 0.00s user 0.01s system 228% cpu 0.003 total<br />
</haskell><br />
<br />
<br />
== Yet another set of prime functions == <br />
<br />
I'm sure this isn't the most efficient, but it is good enough for many applications and it is simple enough for a beginning Haskeller like me to create. It only checks prime numbers as factors when trying to factor a new candidate and only checks odd candidates, otherwise it is pretty straightforward. Working more on efficiency wasn't worth it for the program that used it. Uses integral instead of int to allow for bigger numbers. Thanks to this, I now know that none of my (10-digit) phone numbers are prime numbers. Now to find the factors of my phone numbers...<br />
<br />
<haskell><br />
--| Simple prime functions<br />
--| Produces an infinite list of primes.<br />
myprimelist :: Integral a => [a]<br />
myprimelist = 2 : [x | x <- [3,5..], myprimecheck x (takeWhile (<x) myprimelist)]<br />
<br />
--| simple nth prime using the list<br />
mynthprime :: (Integral a, Integral b) => a -> b<br />
mynthprime 1 = 2<br />
mynthprime n = head $ drop (fromIntegral (n-1)) myprimelist<br />
<br />
--| Check a number for primeness.<br />
myisprime :: Integral a => a -> Bool<br />
myisprime n | n<2 = False<br />
| n<4 = True<br />
| even n = False<br />
| otherwise = myprimecheck n (takeWhile (<n) myprimelist)<br />
<br />
--| Used by myisprime and myprimelist to check for primeness.<br />
myprimecheck :: Integral a => a -> [a] -> Bool<br />
myprimecheck n [] = True<br />
myprimecheck n (f:fs) = if f*f <= n <br />
then<br />
if (n `mod` f)==0 <br />
then False<br />
else myprimecheck n fs<br />
else True<br />
</haskell><br />
<br />
[[Category:Code]]</div>CliffyQShttps://wiki.haskell.org/index.php?title=Windows&diff=13934Windows2007-07-02T20:17:03Z<p>CliffyQS: </p>
<hr />
<div>== Editors ==<br />
<br />
* [http://www.textpad.com/ TextPad]<br />
* Emacs, Vi(m), etc<br />
* [http://www.haskell.org/visualhaskell/ Visual Haskell]<br />
* [http://eclipsefp.sourceforge.net/ Eclipse]<br />
* [http://notepad-plus.sourceforge.net Notepad++]<br />
<br />
== Compilers ==<br />
<br />
* [[WinHugs]]<br />
* GHC : Special note for Cygwin users - http://www.haskell.org/ghc/docs/latest/html/building/platforms.html<br />
<br />
== Libraries ==<br />
<br />
* GUI : [[WxHaskell]] (new release in progress, goal < 2007-01). Note, see also [[WxHaskell Install]]<br />
* GUI : [[Gtk2Hs]] - A binding of GTK in Haskell. Note this requires installing [http://www.gtk.org GTK] on windows.<br />
* Win32 - low levelish bindings to Windows API. Comes with ghc and non-minimal hugs distribution. [http://darcs.haskell.org/ Win32 darcs repo]<br />
* [[HDBC-ODBC under Windows]] for database access.<br />
<br />
== Special tips and tricks for Windows ==<br />
<br />
* darcs : http://wiki.darcs.net/index.html/WindowsConfiguration (although darcs send seems to be broken for now [2006-08-30])<br />
* Make sure your Haskell compiler (e.g. GHC) and tools are on your system path: http://www.computerhope.com/issues/ch000549.htm<br />
* GHCi: Using GHCi from a DOS box sucks. Using it from withing shell mode in Emacs sucks a lot less - do 'M-x shell' in emacs, then type 'ghci'.<br />
* GHCi on cygwin: When running GHC under a Cygwin shell on Windows, Ctrl-C sometimes doesn't work. A workaround is to use the rlwrap program to invoke ghci : In addition to proper Ctrl-C, you also get emacs (or vi) key bindings and command history across sessions, which saves you a load of typing.<br />
<br />
== Direct downloads ==<br />
<br />
=== Haskell ===<br />
<br />
[http://www.haskell.org/alex/dist/alex-2.0.1-win32.zip Alex 2.0.1] [http://www.haskell.org/alex/ (website)] ; [http://www.cs.york.ac.uk/fp/cpphs-1.2-win32.zip Cpphs 1.2] [http://haskell.org/cpphs/ (website)] ; [http://zooko.com/darcsdir-w32-1.0.7.zip Darcs 1.0.7] [http://darcs.net/ (website)] ; [http://haskell.org/hoogle/other/drift-Sep2006.zip Drift Sep 2006] [http://repetae.net/john/computer/haskell/DrIFT/ (website)] ; [http://haskell.org/ghc/dist/6.4.2/ghc-6-4-2.msi GHC 6.4.2] [http://haskell.org/ghc/ (website)] ; [http://haskell.org/haddock/haddock-0.7-Win32.zip Haddock 0.7] [http://haskell.org/haddock/ (website)] ; [http://www.cs.york.ac.uk/fp/temp/hat-win32-05_jul_2006.zip Hat July 2006] [http://haskell.org/hat/ (website)] ; [http://www.haskell.org/happy/dist/1.13/happy-1-13.msi Happy 1.13] [http://www.haskell.org/happy/ (website)] ; [http://www.haskell.org/hoogle/other/hoogle-win32.zip Hoogle June 2006] [http://www.haskell.org/hoogle/ (website)] ; [ftp://ftp.cs.york.ac.uk/pub/haskell/contrib/hscolour-1.3-win.zip HsColour 1.3] [http://www.cs.york.ac.uk/fp/darcs/hscolour/ (website)] ; [http://haskell.org/hoogle/other/lambdashell-0.3.zip Lambda Shell 0.3] [http://www.eecs.tufts.edu/%7Erdocki01/lambda.html (website)] ; [http://cvs.haskell.org/Hugs/downloads/2006-05/WinHugs-May2006.exe WinHugs May 2006] [http://www.haskell.org/hugs/ (website)] ;<br />
<br />
<br />
=== Development ===<br />
<br />
[ftp://ftp.gnu.org/gnu/non-gnu/cvs/binary/stable/x86-woe/cvs-1-11-22.zip CVS 1.11.22] [http://www.nongnu.org/cvs/ (website)] ; [http://www.python.org/ftp/python/2.4.3/python-2.4.3.msi Python 2.4.3] [http://www.python.org/ (website)] ; [http://kent.dl.sourceforge.net/sourceforge/scons/scons-0.96.1.win32.exe Scons 0.96.1] [http://www.scons.org/ (website)] ; [http://subversion.tigris.org/files/documents/15/32856/svn-1.3.2-setup.exe SVN 1.3.2] [http://subversion.tigris.org/ (website)] ; [ftp://download.textpad.com/pub/textpad4.7/txpeng473.exe TextPad 4.7.3] [http://www.textpad.com/ (website)] ; [http://unxutils.sourceforge.net/UnxUtils.zip Unix Utils 14-04-03] [http://unxutils.sourceforge.net/ (website)] ;<br />
<br />
<br />
<br />
[[Category:OS]]</div>CliffyQS