----------------------------------------------------------------
goldbach.lhs -- a halting haskell function.
----------------------------------------------------------------

Prove the function goldbach will halt for all inputs.

----------------------------------------------------------------
Find a pair of primes which sum equals an even input > 4
----------------------------------------------------------------

> goldbach :: Integer -> (Integer,Integer)
> goldbach x
>  | odd x = error "goldbach undefined for odd values"
>  | x < 4 = error "goldbach undefined for values < 4" 
>  | otherwise = goldbach' x primes
>  where
>    goldbach' :: Integer -> [Integer] -> (Integer,Integer)
>    goldbach' x (p:ps) 
>     | prime (x - p) = (p, (x - p))
>     | otherwise = goldbach' x ps

----------------------------------------------------------------
Auxiliary definitions
----------------------------------------------------------------

Sieve to find factors of values, 0 if it is a prime 

> sieve :: Integer -> Integer
> sieve n 
>  | n < 2 = error "sieve undefined for values < 2"
>  | otherwise = sieve' n sievel
>  where
>    sievel :: [Integer]
>    sievel = [ x | x <- 2:[3,5..]]
>    sieve' :: Integer -> [Integer] -> Integer
>    sieve' n [] = 0
>    sieve' n (l:ls)
>     | n < (l * l) = 0
>     | (n `mod` l) /= 0 = sieve' n ls
>     | otherwise = l

The list of primes.

> primes :: [Integer]
> primes = [ x | x <- [2..], sieve x == 0] 

Prove or disprove the primality of a number.

> prime :: Integer -> Bool
> prime x 
>  | x < 2 = False
>  | otherwise = sieve x == 0

-- end of file goldbach.lhs