Search code examples
listhaskelllist-comprehensionprimesgoldbach-conjecture

Implementing Goldbach's conjecture in Haskell, lots of restrictions

The point of this assignment is to understand list comprehensions.

Implementing Goldbach's conjecture for some natural number (otherwise the behavior does not matter) using several pre-defined functions and under the following restrictions:

  • no auxiliary functions
  • no use of where or let
  • only one defining equation on the left-hand side and the right-hand side must be a list comprehension
  • the order of the pairs in the resulting list is irrelevant
  • using functions from Prelude is allowed
-- This part is the "library" 

dm :: Int -> [ Int ] -> [ Int ]
dm x xs = [ y | y <- xs , y `mod ` x /= 0]

da :: [ Int ] -> [ Int ]
da ( x : xs ) = x : da ( dm x xs )

primes :: [ Int ]
primes = da [2 ..]

-- Here is my code
goldbach :: Int -> [(Int,Int)]

-- This is my attempt 1
goldbach n = [(a, b) | n = a + b, a <- primes, b <- primes, a < n, b < n]

-- This is my attempt 2
goldbach n = [(a, b) | n = a + b, a <- takeWhile (<n) primes, b <- takeWhile (<n) primes]

Expected result: a list of all pairs summing up to the specified integer. But GHC complains that in the comprehension, n is not known. My gut tells me I need some Prelude function(s) to achieve what I need, but which one?

Update

parse error on input ‘=’
    Perhaps you need a 'let' in a 'do' block?
    e.g. 'let n = 5' instead of 'n = 5'
Solution

  • Disregarding the weird error you are talking about, I think that the problem you actually have is the following:

    As mentioned by @chi and me, you can't use a and b in your final comprehension before you define a and b. so you have to move it to the and.

    Also: equality of integers is checked with (==) not (=) in haskell. So you also need to change that.

    This would be the complete code for your final approach:

    goldbach n = [(a, b) | a <- takeWhile (<n) primes, b <- takeWhile (<n) primes, n == a + b]

    A small test yields:

    *Main> goldbach 5
[(2,3),(3,2)]

    Update

    If you want to achieve what you wrote in your comment, you can just add another condition to your comprehension

    n `mod` 2 == 0

    or even better: Define your funtion with a guard like this:

    goldbach n
  | n `mod` 2 == 0 = [(a, b) | a <- takeWhile (<n) primes, b <- takeWhile (<n) primes, n == a + b]
  | otherwise = []

    However, if I am not mistaken this has nothing to do with the actual Godbach conjecture.