Combinatorial Search and For Expressions

Here we will see how to handle nested-sequences.

The calculations which are usually expressed in loops can be expressed using higher order functions in sequences.
Eg. Given a positive integer n, find all pairs of positive integers i and j, ith 1 <= j < i < n such that (i+j) is prime. So if n = 7, we would get the below pairs:

i     |  2  3  4  4  5  6  6
j     |  1  2  1  3  2  1  5
------------------------------
i + j |  3  5  5  7  7  7  11

In a conventional way, we would use 2 for loops which are nested, 1 for i and 1 for j. How would you do this in functional programming?

Algorithm:

A natural way to do this is to:

• Generate the sequence of all pairs of integers (i, j) such that 1 <= j < i < n.
• Filter the pairs for which i + j is prime.

One natural way to generate the sequence of pairs is to:

• Generate all the integers i between 1 and n (excluded).
• For each integer i, generate the list of pairs (i, 1), ..., (i,i-1).

This can be achieved by combining until and map:

val xss = (1 until n) map (i => (1 until i) map (j => (i, j)))

This generates a vector of vectors (because range is a subtype of seq. We started with a range (1 until n) and transformed it using a map, which produced a seq. Pairs cannot be elements of range, so what the type inference chose IndexedSequence, essentially a sequence that uses random access and sits between Seq and Range. The prototypical default implementation of an IndexedSequence is just a Vector.

xss = Vector( Vector(), Vector((2,1)), Vector((3,1), (3,2)) ... , Vector((6,1), (6,2), (6,3), (6,4), (6,5)) )

This is not right as we generate a collection of pairs. So we want to concatenate the above list. Hence:

(xss foldRight Seq[Int]())( _ ++ _ )
// OR
xss.flatten // inbuilt method to flatten
// i.e. 
(1 until n) map (i => (1 until i) map (j => (i, j))).flatten

We know that the flatMap function works in a similar fashion, i.e.

s flatMap f = (xs map f).flatten

so we can simplify the above expression to:

(1 until n) flatMap (i => (1 until i) map (j => (i, j)))

Now that we have the desired pair sequence, we need to filter our sequence according to the criterion, that the sum of the pair is prime:

def isPrime(n: Int) = (2 until n) forall (n % _ != 0)
(1 until n) flatMap  (i => (1 until i) map (j => (i, j))) filter (pair => isPrime(pair._1 + pair._2))

Problem: is there a simpler way to organize this expression that makes it more understandable?

For-Expressions