(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. 

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.

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.

Catching a spy and Infinity

I apologize for the hiatus, but I have been buried under overwhelming quantities of work lately. I'll take a break from the regular expression program to show you a puzzle I've found quite interesting:

(You can find more such puzzles here.)

Catching a spy

A spy is located on a one-dimensional line. At time 0, the spy is at location A. With each time interval, the spy moves B units to the right (if B is negative, the spy is moving left). A and B are fixed integers, but they are unknown to you. You are to catch the spy. The means by which you can attempt to do that is: at each time interval (starting at time 0), you can choose a location on the line and ask whether or not the spy is currently at that location. That is, you will ask a question like "Is the spy currently at location 27?" and you will get a yes/no answer. Devise an algorithm that will eventually find the spy.

 

Whoa, that looks quite difficult. Not only do you not know where A is (and there's a lot of places where it could be) but you don't know the spy's velocity either (or direction!). Do not fret, let's make baby steps.

First step: Since the numbers of unknowns and cases is quite large, let's answer a simple version of the question. Set A at 0 and let B only be positive. This means that we know that the thief starts from A = 0 and he's only moving towards the right. What now? Well, let's systematically try and eliminate values of B. Assume B = 1. Then, to rule this option out just ask at t = 1 “Is the spy at position 1?”. If he's not, that means that B ≠ 1. Ok, what about B = 2? At t = 2 ask “Is the spy at position 4?” as this is where he would be if B = 2. If he's not, that means that B ≠ 2. Keep going this way and at moment t ask “Is the spy at position B*t?”. Since we are systematically working our way up through the possible values of B, we know that after B questions we will find the thief!

Second step: Let's look at a more general case. Let B be negative as well. We have more possibilities to worry about (actually, it's just as many as before. Infinity is weird like that.). We can't try and be done with the positive values first and then start working on the negative ones, as we will never get there. Instead, we need to creep our way both directions at the same time. Alternate the positive and negative values of B that we are eliminating with each question. That is eliminate: 1, -1, 2, -2, 3, -3 etc. (Can you work out what positions you have to inquire about at each t?)

Third step: Great, now that we know how to check for all B, we can start worrying about the values of A which, until now, has been fixed. Oh dear, it looks like too many things are moving at the same time! Let's take a look at this (simple) table. Each row lists a value of A and each column a value of B. What we have to do now is find a way to traverse this table by making sure we hit each cell after only a finite amount of time. 

 

Note: We can work out a formula which tells us about which position to enquire at a given time. So, at moment t, if we want to eliminate value a for A and value b for B we can ask about position s(t,a,b) = a + t*b, since that is where the spy would be at that time.

How should we walk around the table? Trying to check the first row first would not work as we will never start checking the second row. Trying to go for the first column would not work either, for the same reason. Fear not, for there is a solution, given by Cantor. Simply take the following path. I'll let you figure out why each cell will be reached after a finite amount of time.

Here's some generalizations you might want to think about. It would help if you have some notions of infinity before thinking about some of these:

1. What if the spy runs around in 2 dimensions? That is, he is either moving up, down, left or right.
2. What about 3 dimensions? 4? Countably infinite ones?
3. What if A = 0 and B can take real values?
4. What if A = 0 and B can take positive real values, but at any given time t you can ask “Is the spy in the vicinity of x?” where x is a real number and by “vicinity” you mean in the interval (x-d, x+d) for a given, fixed d.
5. Same as above, but B can also be negative.
6. Same as above again, but now both A and B can take real values?

Turning NFAs into DFAs (the actual code)

See previous post.


Right, so now, given the bfs function we can convert a given NFA into a DFA. First off, think of the types. We use integers to represent the states of the NFA. The set of states for the DFA, however is the powerset of the set of states of the NFA. Then:

toDFA :: NFA Integer ab → DFA [Integer] ab

If the NFA is M(Q,S,d,q₀,F) then the equivalent DFA will be M'(Q',S,d',q₀',F') . Let's take them one by one. To obtain Q' we need a powerset function:

powerSet :: [a] → [[a]]

powerSet [] = [[]]

powerSet (x:xs) = ps ++ map (x:) ps

where ps = powerSet xs

The alphabet stays the same.

The initial state is the set of all the states that can be reached by epsilon transitions from q0. We need to write a function that will return this set. This is where we need to use the bfs we designed earlier:

--needs trans function, initial state

newInitialState :: Eq st => (Maybe ab -> st -> [st]) -> st -> [st]

newInitialState f q = bfs q (f Nothing)

By passing f Nothing as an argument to bfs we are only allowing epsilon transitions.

To compute F' we need:

That is:

--needs set of states OF THE DFA, final states OF THE NFA

newFinalStates :: Eq(st) => [[st]] -> [st] -> [[st]]

newFinalStates dfaqs nfafqs = [q | q <- dfaqs, not $ null $ intersect q nfafqs]

Next up, let's compute d'. This is going to be slightly more difficult to do. According to the definition of d', given a state and a symbol we need to return the list of all the states that can be reached by any number of epsilon transitions and only one s transition. Let's define a function that, given a node and a function returns that exact list. We'll call it neighbourStates:

neighbourStates :: Eq(st) => st -> ab -> (Maybe ab -> st -> [st]) -> [st]

neighbourStates q0 s f = ana (f Nothing) (nub$concat$map (f (Just s)) (nub((nub$concat$map (f Nothing) (dfs q0 (f Nothing))) ++ f (Just s) q0)))

Wow, that's a big definition. Here's the idea:

1. get a list of all the nodes reachable by only epsilon transitions
2. perform ONE s transition from each of the states in the list
3. for each state in the new list, find all the reachable nodes by epsilon transitions.

Turning into code:

1. Perform bfs by using only epsilon transitions. The problem with bfs, however, is that it includes the original node, regardless of whether there exists a path to it, or not. To avoid this problem, simply do another epsilon transition from all of the nodes in the list. That is:
   
   
   nub((nub$concat$map (f Nothing) (dfs q0 (f Nothing))) ++ f (Just s) q0))
   
   
2. Now, perform one s transition from all the odes in the list. Remember however, that we need to take care of q0, namely we need to take into account the s transitions that start straight from q0. Then:
   
   
   (nub$concat$map (f (Just s)) (nub((nub$concat$map (f Nothing) (dfs q0 (f Nothing))) ++ f (Just s) q0)))
   
   
3. From the new list, just do bfs using epsilon transitions from all the states in the list. We could just map bfs on the list, then do concat and nub, but we already have a function that does this for us: bfsaux
   
   
   bfsaux (f Nothing) (nub$concat$map (f (Just s)) (nub((nub$concat$map (f Nothing) (dfs q0 (f Nothing))) ++ f (Just s) q0)))

So that's the neighbourStates function. Then, we can build the actual transformation function! Here it is:

toDFA :: NFA Integer ab -> DFA [Integer] ab

toDFA (NFA voc sA fA s0A finA) = DFA voc sB fB (newInitialState fA s0A) (newFinalStates sB finA)

where sB = powerSet s

fB sym state = nub (concat [neighbourStates q sym fA | q <- state]);

Breath First Search in Haskell

Programming languages are, more or less, created equal. Despite different syntax and concepts, all decent languages are Turing complete. This means that they are part of the same class. There is no program that one can write in one language that one cannot write in another.

We know that we can perform Breath First Searches (BFS) in linear time in imperative languages. Intuitively, then, we should be able to write a linear time BFS in Haskell as well. Turns out we can, but it's too much of an effort. We'll settle for the next best thing.

Now, we are writing this bfs function for our Complementing Regular Expressions program, so we will choose a slightly odd way of representing the data. BFS works on a graph and a starting node and returns a list of all the reachable nodes from the start node. Instead of defining something like:

data Graph a = Node a [Graph a]

We will keep track of all the edges in the graph through a function f. Then, if q is a node then f q returns a list of all the reachable nodes from q.

f :: a → [a]

bfs :: a → (a → [a]) → [a]

The rather inelegant way we shall go about this is the following: At each step, we will maintain a list of all the nodes that we have visited so far called xs. At every iteration, for each visited node (so for every node in xs) we will try and add all its neighbours to xs. The iteration stops when no new nodes can be added. This is precisely what the bfsaux function does:

bfsaux :: Eq(a) => (a -> [a]) -> [a] -> [a]

bfsaux f xs = if next == [] then xs

               else bfsaux f (next ++ xs)

 where next = nub [y | x <- xs, y <- f x, (not . elem y) xs]

Note: nub ys is simply a function that deletes repeats in the list ys. Also, Eq(a) is required for elem y xs to work.

This is not efficient! One of the problems here is that, for most nodes in xs, we try adding their neighbours to xs at every iteration and we fail each time. All the checking and calling of f costs us time. One way to improve it is to split the information we carry from recursive call to recursive call into a pair (xs,ys) such that at every step we only try and add the neighbours of ys to xs and then we merge ys and xs. That is (xs , ys) → (nub(xs++ys) , next). However, our current implementation is sufficient for now. We can come back and change it if we wish so.

Then bfs is defined as:

bfs q f = bfsaux f [q]

Turning NFAs into DFAs

See previous post. | See next post

The first bit we are going to write is concerned with converting the NFA into a DFA. I am not going to prove that the two are actually equivalent, I'll only show the construction of the DFA. The idea here is that any NFA can be simulated by a DFA with an exponentially increased number of states. Think about it, when the NFA starts consuming the word it's been fed at each step it maintains active a number of sets. Upon consuming each letter, the set of active states changes according to the transition function:

If A is the set of active states at one point then, after one step the set of active positions will be:

We can simulate this by constructing a DFA which represents every possible combination of active NFA states. Then the number of states will be at least 2ⁿ, as any subset of the set of states in the NFA has to be represented.

The DFA transition rule will be the transition from A to A' shown above.

Let's express this formally so we'll be able to convert it to Haskell easily. If the NFA is M(Q,S,d,q₀,F) then the equivalent DFA will be M'(Q',S,d',q₀',F'):

• Q' is the set of all subsets of Q. That is the power set of Q
• S stays the same
• d' tells us where we can go from a state given a symbol. Then:
  

  

  Where q -> p means there exists a transition from q to p that involves only the symbol s and possibly some epsilon transitions.
  Note that this acts on sets of states from the NFA. This will prove to be a slight hindrance later on.
• q₀' will represent the starting position of the NFA. When M starts processing the word, the only active state is the initial state q₀. Then q₀' = {q₀}
• F' requires a bit of thought. When do we consider a word accepted by the NFA? When there is a path we can take through M such that we end up in an accepting state. However, our DFA keeps track of all the active states. Then, to consider a state as an accepting one in the DFA it must only accept words that are accepted in the NFA a well. So they must contain an accepting state of the NFA. Then:
  
  

  

Converting this to Haskell code will be fairly easy, baring some concerns about types. Before we get started on that, let us take a look at a DFS search on a graph in Haskell.