1

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'
Fabian Schneider
  • 799
  • 1
  • 13
  • 40
mushishi
  • 141
  • 1
  • 10

1 Answers1

2

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.

Fabian Schneider
  • 799
  • 1
  • 13
  • 40
  • *Foo> goldbach 23 [] – mushishi May 14 '19 at 08:34
  • 1
    According to wikipedia the goldbach conjecture states `Every even integer greater than 2 can be expressed as the sum of two primes.` which implies that it is only defined for even numbers; which implies that it does not hold for 23 – Fabian Schneider May 14 '19 at 08:45
  • Still ```goldbach 25``` yields ```[(2,23),(23,2)]``` even though it should be [] for any positive odd integer. And thanks for pointing out the importance of the order of conditions in the comprehension! – mushishi May 14 '19 at 09:04
  • 3
    @mushishi: no, this works as an implication, not as an equivalence. Any even integer greater than 2 can be expressed as a sum of two primes, that does not say anything about the odd numbers. It can happen that it is impossible, as well as it can happen that it is possible. – Willem Van Onsem May 14 '19 at 10:48