Monday 18 July 2011

(Almost) A way to extend existing Enumerations in Scala

I've ran into this problem a while ago and it took a bit of thinking before I came to a solution.

Say you have an enumeration:

object BasicAnimal extends Enumeration{
    val Cat, Dog = Value
}

and a function:

def noise(animal:BasicAnimal) = println("It's an animal!")

Say you want to extend the enumeration to include other animals as well:

object FourLeggedAnimal extends BasicAnimal{
    val Dragon = Value
}

So then Cat, Dog and Dragon would all be FourLeggedAnimal, yet only Dog and Cat will be BasicAnimal. Sadly, this wouldn't work as BasicAnimal is an object, not a class or a trait. So what's a guy to do? Try this for a size:

abstract class BasicAnimalAbstract extends Enumeration{
    type BasicAnimal = Value
    val Cat, Dog = Value
}
 
abstract class FourLeggedAnimalAbstract extends BasicAnimalAbstract{
    type FourLeggedAnimal = Value
    val Dragon = Value
}
 
object BasicAnimal extends BasicAnimalAbstract{}
object FourLeggedAnimal extends FourLeggedAnimalAbstract{}
 
 
def f(animal: FourLeggedAnimal) = println("It's an animal!")
 

Then you get:
 
    scala> f(Dragon)
    It's an animal!
    
    scala> f(Cat)
    It's an animal!
 
So it would seem that this is the solution. Sadly, this is only a partial solution. One of the issues is that
BasicAnimal.Cat != FourLeggedAnimal.Cat.
Moreover, not even casting would work!
FourLeggedAnimal.Cat.asInstanceOf[BasicAnimal] != BasicAnimal.Cat
 
So this only works to a certain extent. If you're desperate, you can do this in order to get equality
between elements of BasicAnimal and FourLeggedAnimal:

def findCorrespondent(animal: FourLeggedAnimal){
     BasicAnimal.withName(animal.toString)
}
 
Not ideal, but works. 

Thursday 14 July 2011

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.

Monday 4 July 2011

Imperative vs Functional: Finding prime numbers

It's always seemed to me that, while imperative programming means having a more intimate relation with your machine (at the most basic level, the programming language is imperative), functional programming has a certain pure elegance to it that makes it even more appealing than the former. Sadly, languages have usually been separated into imperative vs. functional in such a way that, even though scripting languages like python might offer a bit of a functional flavour, they fail to offer the elegance of functional languages in an imperative context.

Enter Scala. I've only played around for a bit with this new language, but it does seem to have the best of both worlds. Weather Scala will end up being as widespread as Java et al. Only time will tell (although my bet is that it most definitely will).

Anyway, let us take a look at what Scala can do.

Finding a prime number

This is a classic. Write a simple algorithm that computes weather a given number is prime or composite. Note that I won't cover setting up the environment to work with Scala; the Scala webpage does a great job at that.

One way to check if a number is prime is by checking if anything less that itself and larger than 1 divides it:

for i from 2 to (n-1):
    if(i%n == 0) return “is not prime”
return “is prime”

You can easily see this is correct; the second return statement is only reached when all of the values less than n have been checked as divisors of n.
Here's how one would express it in Scala:

val n = args(0).toInt
def imperativeIsPrime(x: Int): Unit =
{
   for(i <- 2 to (n-1))
   {
     if(n%i == 0)
     {
     println(x + " is not prime. It is divisible by " + i)
     return
     }
   }
println(x + " is prime")
}

Add this into a file called imperativePrime.scala. This script can be run by using

scala impertivePrime.scala [your number]

e.g.:

scala imperativePrime.scala 13

at the command prompt. Again, check the tutorials on the Scala website.

Let's go through this code line by line.

val n = args(0).toInt

This simply takes the first argument passed at command line and stores it into n.

def imperativeIsPrime(x: Int): Unit

This defines a new function called imperativeIsPrime which takes one argument of form Int and has return type Unit. Type Unit is very similar to void in Java, so we'll just leave it at that.

Next up, the loop:

for(i <- 2 to (n-1))

2 to (n-1) means the same as 2.to(n-1). 2 is an object and to is a method of this object which returns something called a Range: Range(2,3,4,...,n-1).
i <- 2 to(n-1) means that i takes every value in the range and executes the body of the loop, which checks for divisibility, which is pretty obvious.

So this is the imperative approach. Now onto the functional one, which I shall cover tomorrow.