Functional ruby – a simple example

Today I’d like to present the implementation of the quicksort algorithm, starting from a naive imperative solution and improving it for elegance and clarity.

Why quicksort? Well, it’s a quite good sorting algorithm which can be effectively implemented on modern architectures and also very easy to understand, making it a nice test subject. To learn about the algorithm itself, look here. The short description of the algorithm goes like this:

1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

Based on this description, here we go with a straight-forward naive implementation in ruby:

def partition(items, left, right, pindex)
   pvalue = items [pindex]
   swap(items, pindex, right)
   sindex = left
   for i in left .. right-1
       if items[i] <= pvalue
          swap(items, sindex, i)
          sindex = sindex + 1
       end
   end
 
   swap(items, right, sindex)
   return sindex
end
 
def swap (arr, l, r)
  tmp = arr [l]
  arr[l] = arr[r]
  arr[r] = tmp
end
 
def qsort(items, left, right)
	if (right > left)
	    pIndex = left
	    newPindex = partition(items, left, right, pIndex)
	    qsort(items, left, newPindex-1)
	    qsort(items, newPindex+1, right)
	end
 
end
 
def quicksort(items) 
  qsort(items, 0, items.size - 1)
end

Well, not particularly nice. Isn’t ruby supposed to be a terse language? Wait and see. First what bothers me the most is the ‘swap’ function there. There’s no need for that, in ruby you can use parallel assignment, so :

   items[sindex], items[right] = items[right], items[sindex]
   #swap(items, right, sindex)

Also, do we really need that ‘partition’ function? Nope. Ruby’s Enumerable module has it already. It says:

^?View Code RUBY

enum.partition {| obj | block } => [ true_array, false_array ]

Returns two arrays, the first containing the elements of enum for which the block evaluates to true, the second containing the rest.

Nice. Let’s write an alternative version using this knowledge:

def quicksort2(items)
   return items if items.nil? or items.length <= 1
   less, more = items[1..-1].partition { |i| i < items[0] }
   quicksort(less) + [items[0]] + quicksort(more)
end

So much nicer! Another alternative could be this, using Enumerable#select:

def quicksort(items)
  if not items or items == [] then 
    []
  else
    x, *xs = items
    quicksort(xs.select { |i| i <  x }) + [x] + quicksort(xs.select { |i| i >= x })
  end
end

Notice the line ‘x, *xs = items’ – it’s just like head and tail in functional languages! Beautiful. It works like this:

irb(main):007:0> a = ['first','second','third','fourth']
=> ["first", "second", "third", "fourth"]
irb(main):008:0> x, *xs = a
=> ["first", "second", "third", "fourth"]
irb(main):009:0> x
=> "first"
irb(main):010:0> xs
=> ["second", "third", "fourth"]

For a comparison, here is my Haskell version:

quicksort :: (Ord a) => [a] -> [a]    
quicksort [] = []    
quicksort (x:xs) = quicksort (filter (< x) xs) ++ [x] ++ quicksort (filter (>= x) xs)

Almost the same, right? The difference again is that the Ruby version says how to do the sort while the Haskell version is describing the algorithm, the method itself, it’s closer to saying what quicksort is. It has no ‘do it next’ and ‘return this’.

Today I'd like to present the implementation of the quicksort algorithm, starting from a naive imperative solution and improving it for elegance and clarity. Why quicksort? Well, it's a quite good sorting algorithm which can be effectively implemented on modern architectures and also very easy to understand, making it a nice test subject. To learn about the algorithm itself, look here. The short description of the algorithm goes like this: Pick an element, called a pivot, from the list. Reorder the list so that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation. Recursively sort the sub-list of lesser elements and the sub-list of greater elements. Based on this description, here we go with a straight-forward naive implementation in ruby: def partition(items, left, right, pindex) pvalue = items [pindex] swap(items, pindex, right) sindex = left for i in left .. right-1 if items[i] left) pIndex = left newPindex = partition(items, left, right, pIndex) qsort(items, left, newPindex-1) qsort(items, newPindex+1, right) end end def quicksort(items) qsort(items, 0, items.size - 1) end Well, not particularly nice. Isn't ruby supposed to be a terse language? Wait and see. First what bothers me the most is the 'swap' function there. There's no need for that, in ruby you can use parallel assignment, so : items[sindex], items[right] = items[right], items[sindex] #swap(items, right, sindex) Also, do we really need that 'partition' function? Nope. Ruby's Enumerable module has it already. It says: enum.partition {| obj | block } => [ true_array, false_array ] Returns two arrays, the first containing the elements of enum for which the block evaluates to true, the second containing the rest. Nice. Let's write an alternative version using this knowledge: def quicksort2(items) return items if items.nil? or items.length = x }) end end Notice the line 'x, *xs = items' - it's just like head and tail in functional languages! Beautiful. It works like this: irb(main):007:0> a = ['first','second','third','fourth'] => ["first", "second", "third", "fourth"] irb(main):008:0> x, *xs = a => ["first", "second", "third", "fourth"] irb(main):009:0> x => "first" irb(main):010:0> xs => ["second", "third", "fourth"] For a comparison, here is my Haskell version: quicksort :: (Ord a) => [a] -> [a] quicksort [] = [] quicksort (x:xs) = quicksort (filter (< x) xs) ++ [x] ++ quicksort (filter (>= x) xs) Almost the same, right? The difference again is that the Ruby version says how to do the sort while the Haskell version is describing the algorithm, the method itself, it's closer to saying what quicksort is. It has no 'do it next' and 'return this'.

Tagged as: functional, haskell, ruby