-
Notifications
You must be signed in to change notification settings - Fork 16
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?
A natural way to do this is to:
- Generate the sequence of all pairs of integers
(i, j)
such that1 <= 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
between1 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:
(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.
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:
((1 until n) map (i => (1 until i) map (j => (i, j))) foldRight Seq[Int]())( _ ++ _ )
// OR
(1 until n) map (i => (1 until i) map (j => (i, j))).flatten // inbuilt method to 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?
Week 1
Week 2
- Higher Order Functions
- Classes and Objects
- Substitution Model (CBV, CBN) with Classes
- Operators, Precedence and Types
Week 3
- Class Hierarchies and Dynamic Binding
- Organizing Classes and Scala Class Hierarchy
- Polymorphism (Subtyping and Generics)
Week 4
- Objects-Everywhere
- Subtyping and Generics (Bounds and Covariance)
- Decomposition
- Pattern Matching
- Collections (Lists)
Week 5
- Collections (List Methods)
- Pairs and Tuples
- Collections (Lists - Applying functions to elements)
- Collections (Lists Reduction)
- Collections Theory (Lists concat and reverse)
Week 6