Archive

Archive for August, 2010

GPS and Golf

I haven’t played much golf in my life. In fact, excluding a few rounds of pitch and putt, I’ve only played two rounds of golf. Both of these have been within the last few weeks at Ramsdale Park.

On the second of these occasions I decided to take a GPS log of my round. Here are two different views of the round as shown in Google Earth:

A round at Ramsdale Park Golf ClubA round at Ramsdale Park Golf Club

These pictures don’t quite give the course the justice it deserves. The front nine are nice and flat, but the the back nine start up on a big ridge which is only just visible above the green start marker in the first picture.

Anyway, my golfing may have improved very slightly, and I’m looking forward to my next round!

Categories: GPS Logs

Radix Sort in F#

August 13, 2010 1 comment

I have spent many years programming in Haskell, but have also recently started dabbling in F# and Ocaml. I would count myself as a big proponent of the Functional Programming paradigm.

Just as a practice I thought I would implement a Radix sort algorithm in F# for unsigned 32bit integers. Radix sort algorithms use a Radix in order to sort the elements in a list or array. This means that you must be able to define a Radix for the data type which you are trying to sort, but has the advantage that the time complexity of the algorithm is only linear in the number of elements to be sorted (multiplied by a constant that relates to the size of the radix), compared to O(n log n) for most partition sort algorithms.

For this implementation, I shall use the bits as the Radix. This means that each step of the sort algorithm splits the list into two, depending on the value of a single bit in each element, keeping all the elements in these sublists in the same order they appeared in the original list. The algorithm works by splitting the list depending on the least significant bit of each element, and then joining the resultant sublists, before repeating the process depending on the next least significant bit… this repeats until the last step where the splitting depends on the most significant bit of the elements, and the final joined list is ordered. I am sure there are much better definitions of a radix sort on the web, but I thought this would be an interesting initial experiment with F#.

Some of these functions my well be in the library, but my current knowledge of the library is lacking slightly, so I have implemented everything I don’t know about.

The first definition is a function that simply returns a Boolean value of whether the input integer is equal to zero. This achieved using pattern matching.

let is0 x =
  match x with
    0 -> true
  | n -> false

The next function defines how the list is split depending on the Radix. The first argument is the position of the bit which is the current Radix, and the second argument is the input list. The recursive sub-function actually does the work using a pair of accumulators.

// splits a list of integers in half depending on the value of the nth bit of the integers
let splitBy n xxs =
   let rec splitBy' n' xxs' (oz,iz) =
      match xxs' with
        [] -> (oz,iz)
      |  x :: xs -> splitBy' n' xs (if is0 ((x >>> n') &&& 1) then (x::oz,iz) else (oz,x::iz))
   splitBy' n xxs ([],[])

You’ve probably noticed that the lists returned by the previous function actually contain the elements in the reverse order in which they appear in the input list. So, we will need a function that reverses a list. This can also be achieved using an accumulator.

//simple reverse list implemented using an accumulator e.g. extra list to move elements into
let reverse ls =
   let rec reverse' (xs,scratch) =
      match xs with
        [] -> scratch
      | x :: xs -> reverse' (xs,x :: scratch)
   reverse' (ls,[])

We can use the reverse function when we want to join the two lists that are created at each step of the algorithm. I have used the list concatenation function from the library.

let join (oz,iz) = List.concat [reverse oz;reverse iz]

Each step of the algorithm can now be defined. The first argument still defines which bit you’re working with, and the second argument is the input list.

let sortBy n xs = join (splitBy n xs)

The algorithm is completed by running the algorithm recursively over all 32 bits in the unsigned 32 bit integers.

// recursive algorithm to sort depending on LSB upto MSB e.g. bits 0 to 31
let sort xs =
   let rec sort' n xs' =
      match n with
        0 -> xs'
      | i -> sortBy (i-1) (sort' (i-1) xs')
   sort' 32 xs

and that is it… An implementation of Radix sort in F#.
Comments Please.

Categories: FUN

Rugby and Me…

I was privileged enough to attend a school in which Rugby Union was taught as part of P.E. I trained and played with St. Katherine’s rugby team for most of time I was at the school. Despite being rather less than adept at the sport, I always enjoyed it. It wasn’t until quite a few years later that I decided I wanted to get back into playing rugby, and also take the sport seriously and play at the highest level possible.

The change in attitude came about after being invited to play in a 7s tournament whilst I was in my third year of university. A friend of mine had entered a team into the intramural 7s, and the night before the event, was short of a few players. So, in steps myself and a couple of my other house mates at the time. Needless to say, we didn’t do very well in the competition, and I only managed 5 minutes on the pitch before injuring my ankle, in what turned out to be quite a bad way! In fact, after trying to hobble around on what I thought was a badly sprained ankle for the next three days, a quick exchange of emails with my Mum persuaded me to get it checked out by a doctor. Well… the doctor sent me straight to the X-Ray department of the A&E, where they discovered I’d fractured the ankle pretty badly. Badly enough in fact to warrant surgery, and a 10 day stint bed bound in hospital until they could put metal plates into my ankle to fix it. This may not sound like a event that would make me want to play rugby, but it did, and it made me determined to train my ankle back up to strength a join a local rugby club.

My Broken Ankle

It was a year or so later that I felt confident enough on my ankle, and so I went along to train with Nottingham Casuals. I am still playing for Casuals, and the beginning of my 6th season with them is just around the corner. In fact our first game is a week tomorrow! It took a few years, but I am now even playing first team level rugby quite often. We play in the Midlands 3 East (North) division, and are always looking for new players as well as promotion!

Casuals Team PhotoCasuals Team Photo

I have had a few other injuries, including a broken wrist and many broken fingers (one of which needed surgery and even more metal fixtures), but I still enjoy the game.

I plan to blog about memorable games, as well as any new club i may join if the inevitable happens and I move away from Nottingham.

Nottingham Casuals in a very friendly club, with plenty of social activities, including the annual Solstice Sevens tournament, as well as club tours.

My Solstice Seven TeamCasuals on Tour

Categories: Rugby

In The Beginning…

So, I have decided to start a blog… The main question at this stage might well be “Why?”.

Well, my name is Alexander S. Green, and I was born 27 years ago, on the 21st of February 1983. I grew up in Long Ashton, which is a prosperous village close to Bristol, just inside what is now North Somerset. Up until recently in my life, I have spent most of my time in education. Starting at Birdwell primary school in Long Ashton.

Me in my Birdwell uniformMe in my Birdwell uniformMe in my Birdwell uniformMe in my Birdwell uniformMe in my Birdwell uniform

I left in 1994 to move onto St. Katherine’s secondary school in Pill, a short coach journey from Long Ashton. I stayed on at St. Katherine’s for my GCSEs and A Levels, eventually leaving in 2001.

Me in my St. Katherine's uniform

At this point, I started my university education at the University of Nottingham, and finished my BSc. in Computer Science with an upper second in 2005. The same year, I started a PhD. still at Nottingham as part of what is now the Functional Programming Laboratory. My thesis “Towards a Formally Verified Functional Quantum Programming Language” was finally submitted towards the end of 2009, and I was able to graduate at the July 2010 ceremonies.

Me at GraduationMe at Graduation

So, thats a very brief run down of my life so far, or at least my life in education. I am now headed out into the big bad world, and looking for jobs in which I can use all the skills I have been working towards for so many years!

Well, the point is that until this time, I have felt too busy to blog, and have had success in propagating my research through publications. Such as a chapter on the Quantum IO Monad in the book Semantic Techniques in Quantum Computation (link). With lots of spare time on my hands, whilst i search for a job, i have more free time in which to establish a blog.

My plan is to blog about my work, which will hopefully include various forms of Functional Programming, as well as more general happenings in my life. I shall categorise my posts as best I can, and look forward to adding more blog posts, maybe with a little more history about myself, but more looking into the present and the future…

Alexander S. Green

13/08/2010

Categories: Life