Problem Description

Problem: Given a positive integer $n$, find all ordered pairs of distinct positive integers $i$ and $j$, where $ 1 \leq i \leq j \leq n $, such that $ i + j $ is prime.

Implementation in Haskell

isDivisible :: Int -> Int -> Bool 
isDivisible x y 
    | mod x y == 0  = True 
    | otherwise     = False 

isPrime :: Int -> Bool
isPrime x 
    | x <= 2    = True 
    | otherwise = not (foldr (||) False (map (isDivisible x) [2..((floor . sqrt . fromIntegral) x)]))


genPairs :: Int -> [((Int, Int), Int)]
genPairs n = do 
    x <- [1..n]
    y <- [1..(x-1)]
    return ((y, x), (x + y))

sumPrimePairs :: Int -> [((Int, Int), Int)]
sumPrimePairs = (filter (\(_, s) -> (isPrime s))) . genPairs

About List Monad: Context, Nested lambda and do-notation

Context of List Monad : nondeterministic result.

The title of this section is Nested Mappings, represented in code with nested lambdas. In Haskell, do notation is syntactic sugar for nested lambdas.

And flatMap defined in this chapter is actually Haskell >>= (bind) in Haskell.

For further details, consult Learn You a Haskell for Great Good: A Fistful of Monads - the List Monad

Another Example: The List Monad for Permutation

An intuitive way to understand this is that nondeterministic results are well-suited for solving permutations.

permutations :: Eq a => [a] -> [[a]]
permutations [] = [[]]
permutations xs = do
    x <- xs 
    perm <- permutations $ removeByElem x xs
    return (x: perm)

removeByElem :: Eq a => a -> [a] -> [a]
removeByElem x = filter (/= x)