Imperative vs Functional: Finding prime numbers (Part 2)

Last time we looked at a very basic program that computed whether a number is prime in an imperative way. Before we start, we should look at three important notions for the functional style:

map, fold (and reduce) and filter.

Map

Imagine you have a list of acquaintances:

var acquaintances = List(Arnie, Nigel, Christopher, Jose)

and a function which tells you if a person is a friend:

def isFriend(acquitance: Person): Boolean

Now, you want to know who your friends are, so you want to apply isFriend to each acquaintance. This is exactly what map does. It takes a function and applies it to every element of a list.

acquaintances.map(isFriend) =

List(isFriend(Arnie), isFriend(Nigel), isFriend(Christopher), isFriend(Jose)) =

List(true, false, true, true)

Because Nigel is a douche.

Fold (and reduce)

Fold may look a bit more difficult at first, but it's not that bad. Fold traverses the list and picks up elements as it goes through. To go back to the acquaintances example, imagine you want to traverse your acquaintances list and ask each how much money they owe you in order to establish a grand total. For this we need a function:

def addToBalance(partialDebt: Int, acquaintance: Person): Int

This takes the amount acquaintance owes to you and adds it to your partial debt. Also, assume you start with -1000 since that's how much money you owe to the bank since you bought that pig on credit. This situation is perfect for using fold! You'll need 2 parameters: the starting value and the function that you are going to apply:

acquaintances.fold(-1000)(addToBalance) =

List(Arnie, Nigel, Christopher, Jose).fold(-1000)(addToBalance) =

List(Nigel, Christopher, Jose).fold(addToBalance(-1000, Arnie))(addToBalance) =

//note how we have replaced -1000 with the new overall debt after we've added the money

//Arnie owes you

List(Nigel, Christopher, Jose).fold(-970)(addToBalance) =

List(Christopher, Jose).fold(addToBalance(-970,Nigel))(addToBalance) =

List(Christopher, Jose).fold(1030)(addToBalance) =

//I guess we know why Nigel was pretending to be friends with you now

//I bet you regret lending him that 2k

List(Jose).fold(addToBalance(1030, Christopher))(addToBalance) = ...

1045

Reduce is very similar, except for the fact that it doesn't work with lists that have less than 2 elements and it doesn't have any starting value. For example: Let's say now you're depressed because Nigel just ran away with the money he owed you and your wife so you want to see if you have any friends. Look again at the list in the map section:

acquaintances.map(isFriend)

This is a list of booleans at this point. To see if you have any friends you can traverse the list and see if there exists an element that equals "true". Basically, by applying the `or` operator(in Scala, the operator is || ):

acquaintances.map(isFriend).reduce((a,b) => a || b) = true //yay!

This works just like fold, except it starts directly with the two starting elements of the list.

Filter

At this point, you want to move on with your life and forget about anyone who isn't your friend. Say hello to filter! Filter takes a function that returns a boolean and drops any elements that don't fullfil that function. In our case:

var friends = acquaintances.filter(isFriend)

friends = List(Arnie, Christopher, Jose)

Nigel fails to appear in this new list, as he is a douche.

Cool, now, we can work out that isPrime function:

def functionalIsPrime(n: Int){

(2 to (n-1)).filter(k => n%k == 0).isEmpty

}

Simply take the whole list of numbers from 2 to (n-1) and throws away all the ones that do not divide n. At the end, we simply check if the resulting list is empty. If it is, n is prime, otherwise there exists a divisor for n.

Moreover, this is rather efficient, as it is lazy, but more on that later.