I have nothing against Ruby’s image, despite the hipster-bashing that its name tends to invoke.

I think that the “Rails coding ninja” archetype the start-up world has conjured up is obnoxious, but I also think it’s strictly a product of the tech start-up world. Outside that limited circle, I doubt that anyone who uses Rails is any different from the people who were using PHP fifteen-odd years ago.

However, I cannot stand the language itself.

Ruby seems to offer roughly the same package as PHP (easy enough to code things up even for non-computer-science types like me, particularly well-suited to web development, slow, something of a mish-mash from a language-design perspective), just *improved*. Its niche, as far as I can tell, is the same. It’s avoided the mistakes PHP made, it’s a little slower, and it has the ability to do some clever cross-paradigm things (functional programming is a different paradigm because Ruby is object-oriented-turtles all the way down). It saves developer time, I guess, used right.

Meh. It doesn’t excite me, and I don’t learn anything new from it. I’m sure once I’m experienced enough with programming to be jaded I will find it utterly thrilling – but right now, all I see is a heap of syntactic sugar on top of a big ol’ mess of blah.

Let’s not go to Ruby, it is a silly place. Here is some more messing around with Lisp’s grandchild, Racket instead, along with explanations.

**Quicksort**

Quicksort is a decently fast sorting algorithm, as the name would imply. Here’s a simple way to implement a rough version in Racket, with explanations of what I’m doing as I go.

Comments are marked out with “;”, in case anyone reading doesn’t do Racket.

(define (quicksort xs) (if (null? xs) xs ;if the list we pass to quicksort is empty, return the list. (let* ;let* allows you to define multiple local bindings ([hd (car xs)] ;variable "hd" = the head of our list. [tail (cdr xs)] ;tail = list tail [smaller (filter (lambda (x) (< x hd)) tail)] [bigger (filter (lambda (x) (>= x hd)) tail)]) (append (quicksort smaller) (list hd) (quicksort bigger))))

This is pretty concise, but it’s not really that simple of course. I’ve used the simplest way of writing things without really examining why it works or how it will work in practice.

The “smaller” and “bigger” bindings are made by passing our anonymous function (the bit with the keyword “lambda”) to the library function “filter”. That’s a bit of a cop-out, although filter is fairly simple it is a pretty cool and useful function to know how to write. Let’s have a look at my understanding of how it works:

(define (filter-local fn xs) ;defined locally to avoid shadowing (letrec ([f (lambda (xs acc) ;introducing an accumulator (if (null? xs) (reverse acc) ;give back the consed list at end (in right order) (if (fn (car xs)) ;if our function is true for head of list (f (cdr xs) (cons (car xs) acc));recurse and cons head to accumulator (f (cdr xs) acc))))]);else recurse and do nothing (f xs null))) ;starting the recursive function

This is probably not how it’s done exactly, but it gives you the general idea of what we’re doing with it – grabbing a list of numbers smaller than the head of our list, and a list of numbers bigger than or equal to the head of our list. This illustrates that this seemingly simple function actually is doing more work than it looks like, filtering the same list twice for every call. We could definitely make this more efficient, if we needed to, with a more specific single local function:

(letrec ([f (lambda (x ys sml big) (if (null? ys) (append (quicksort sml) (list x) (quicksort big)) (if (> x (car ys)) (f x (cdr ys) (cons (car ys) sml) big) (f x (cdr ys) sml (cons (car ys) big)))))]) (f hd tail null null))

Feel free to check this function, it may be a little off as I’ve just written it in WordPress now. The idea, however, is that we do less work with each call to quicksort. This is not traditionally that important in algorithms (the Big O notation is *usually* more relevant, especially as if we’re not using the sort on large lists we’ll probably choose, say, an insertion-sort method instead) but it could probably knock at least some time off its run-time.

The way it works is by recursively calling quicksort on the lists of smaller and larger numbers, gradually sifting the big list blocks so that eventually we’re sorting (1) (2) and (3) rather than (213) (5) and (6559).

Now I run quicksort on a boring random list of 10000 numbers.

It’s super-fast! Awesome.

Just for kicks, I’ll run it again on the ordered list and -huh?

On ordered lists, this quicksort algorithm is slooooow. If we start with a pre-ordered list and use head/car as our “pivot”, quicksort runs at its worst-case performance, O(n^2). Usually, worst-case performance is very rare, but since ordered lists are pretty common we’ve just upped the chance that we’ll get a worst-case performance. Now, we could simply check to see if a list is ordered before we run the algorithm (boo!) or we could refactor the algorithm (yay!).

We can choose the middle-value by dividing the length of the list by two and using list-ref to choose the appropriate element – that’s the simplest way.

Further optimisations are a little more complicated (honestly, not much more complicated) and can be seen here: http://en.wikipedia.org/wiki/Quicksort

I’ve also written an implementation of merge sort[1] in Racket to make sure I understand that. It’s possible I’m a little over-excited about my upcoming Coursera course on algorithm design and analysis, and it’s definitely the case that I need to go write in some less pretty languages in the near future.

*As always, if you’ve seen something egregious in this post, please correct me. I make these posts primarily to learn, so anything you can let me know is gratefully accepted!*

[1] You can see how I created my merge sort here if you’re interested.