Download code

Jump to: navigation, search

Back to Goldbach's_Conjecture_(Haskell)

Download for Windows: zip

Download for UNIX: zip, tar.gz, tar.bz2

goldbach.hs

  1 {- The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Goldbach's_Conjecture_(Haskell)?oldid=18656
 14 -}
 15 
 16 module Main (goldbach, main) where
 17 
 18 import Prelude
 19 import System.Environment
 20 import System.IO (hFlush, stdout)
 21 import Primes (primes)             -- Updated 10/19/09, Added module (see below)
 22 
 23 {- The Goldbach Conjecture: An Implementation
 24    James Brannan (irregularexpression@gmail.com)
 25 -}
 26     
 27 
 28 -- For convenience
 29 type Pair = (Integer, Integer)
 30 
 31 {- showPList: Prints a list of Pairs and formats them as a
 32               set into columns between braces. -}
 33 showPList :: [Pair] -> IO ()
 34 showPList [] = putStr "{ }\n"
 35 showPList plist = do
 36     putStr "{ " 
 37     fmt 1 plist
 38     putStr " }\n"  where
 39         showPair (x, y) = "(" ++ show x ++ "+" ++ show y ++ ")"
 40         fmt n (y:ys) = do
 41             putStr (showPair y)
 42             -- Every 4 elements, start a new column.
 43             if n `mod` 4 == 0 then 
 44                 if ys == [] then return () else putStr "\n  "
 45              else putStr "   "
 46             fmt (n+1) ys
 47         fmt _ [] = return ()
 48                 
 49                 
 50 {- findsum: Finds a sum x by zipping a list (of primes) less than
 51             x with itself (excluding repeats) and checking for 
 52             pairs that add up to x. I remove a lot of the garbage
 53             by throwing away values
 54             of z greater than y (to remove [x,y] == [y,x]). -}
 55 findsum :: Integer -> [Integer] -> [Pair]
 56 findsum x plist = [(y,z) | y <- plist, z <- plist, y+z == x, y<=z]
 57 
 58 
 59 {- goldbach: Takes a positive even integer x and exhaustively checks
 60              pairs of primes less than that integer that add up to
 61              precisely x. Note we chop off half the list -- each 
 62              pair has a non-unique equivalent => (a,b) = (b,a) -}
 63 goldbach :: Integer -> [Pair]
 64 goldbach x | odd x || x < 3 = error "Must be a positive even integer greater than 2"
 65            | otherwise = findsum x plist where
 66                 -- Find list of primes smaller than x.
 67                 plist = takeWhile (< x) primes
 68 
 69 
 70 {- main: Driver interface for the defined functions. On first run,
 71          an introduction message will be displayed, otherwise only
 72          the prompt will be shown. -}
 73 main :: IO ()
 74 main = do
 75     args <- getArgs
 76     let args_num = [(read x::Integer) | x <- args]
 77     case args of
 78         [] -> helper True                 -- No arguments, run interactive
 79         _  -> mapM_ showvalue args_num    -- Arguments given, run through
 80     
 81     where
 82     -- I *hate* nested paren's (too much lisp...) Use $!
 83     showvalue x = do putStr $ resultMsg x $ length l
 84                      showPList l
 85         where l = goldbach x
 86         
 87     helper b = do
 88         intro b    -- Show intro message depending on b
 89         {- I have to import some IO functions here
 90            because by default the output is buffered
 91            and won't print until an \n is found, meaning
 92            user input can't be on the same line as the
 93            prompt. Without flushing the output first, 
 94            the program executes out of order (when compiled).
 95         -}
 96         putStr "[Number or 0] -> "
 97         hFlush stdout
 98         x <- readLn :: IO Integer -- Get input and calculate or exit
 99         exec x
100     
101     -- Intro message to be shown when the program is first run
102     intro True = putStr ("The Goldbach Conjecture states that any positive, " ++
103                          "even integer (>2) can be expressed as the sum of " ++
104                          "two prime numbers. This application is an " ++
105                          "algorithmic solver for the Goldbach Conjecture. " ++
106                          "Begin by entering values, and the appropriate sets " ++
107                          "of prime numbers will be returned. You may quit at " ++
108                          "any time by typing the number 0.\n\n")
109     intro False = return ()
110 
111     resultMsg int res = "\nGoldbach(" ++ show int ++ ") = " ++ show res ++ " unique sets:\n"
112         
113     -- Allow user to quit by typing 0
114     exec 0 = putStr "\tQuitting...\n"
115     exec y = do showvalue y
116              putStr "\n"
117              helper False -- Call without intro msg until user quits.
118 
119 
120 -- James Brannan (irregularexpression@gmail.com) 9/18/09
121 
122 
123 


hijacker
hijacker
hijacker
hijacker

primes.hs

 1 {- The authors of this work have released all rights to it and placed it
 2 in the public domain under the Creative Commons CC0 1.0 waiver
 3 (http://creativecommons.org/publicdomain/zero/1.0/).
 4 
 5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 
13 Retrieved from: http://en.literateprograms.org/Goldbach's_Conjecture_(Haskell)?oldid=18656
14 -}
15 
16 module Primes (primes) where
17 
18 primes :: [Integer]
19 primes = 1:2:3:primes'
20   where
21 	{- Throw away first value (always 1), capture prime, and candidates
22 	   (using that fact that all *candidate* primes but 2 and 3 are of
23 	   the form [6k+1] and [6k+5] for any integer k (but not all) -}
24     1:p:candidates = [6*k+r | k <- [0..], r <- [1,5]]
25 	-- Create list of primes by adding the found prime p to the list of 
26 	-- candidates after they have been filtered for primes
27     primes' = p : filter isPrime candidates
28 	-- Finds if n is prime by testing all elements p where (p^2) is not
29 	-- greater than n from the list of generated primes
30     isPrime n = all (not . divides n) $ takeWhile (\p -> p*p <= n) primes'
31 	-- Divides is true if the remainder between n and p is 0
32     divides n p = n `mod` p == 0	
33 
34 


hijacker
hijacker
hijacker
hijacker