Functional ruby – a simple example

Posted by ochronus on Feb 18, 2010 in Featured Articles, haskell, ruby, theory | 21 comments

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:

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

 

Related posts:

  1. Ruby vs. Haskell – project Euler #25 deathmatch
  2. Drawing the Mandelbrot set in Ruby and Haskell

5 Comments 12 Tweets

21 comments

  1. Kevin
    February 18, 2010

    Why try to fit a square in a round hole.
    If you want functional go to Erlang.

    [Reply]

    ochronus Reply:
    February 18th, 2010 at 19:23

    @Kevin, Erlang isn’t the only functional kid around.

    [Reply]

  2. homoiconic
    February 18, 2010

    There is a difference between *writing a method that implements a function over first-class entities* and *functions being first-class entities*. I think this post does a good job of showing the former but alas, says nothing of the latter.

    This comment was originally posted on Reddit

    [Reply]

  3. ochronus
    February 18, 2010

    Hm, neat point there! Thanks for bringing it up :)

    This comment was originally posted on Reddit

    [Reply]

  4. Vidar
    February 18, 2010

    Neat, but you also highlight one of my pet peeves with the quicksort example:

    You start out with a naive (because of the poor pivot selection) but reasonable version that does the sort in-place with reasonable space use, and then quickly discard it for one that gleefully waste memory by returning the partitions as two separate arrays….

    I appreciate that this is an example, I just hope any Ruby programmers will think writing Ruby this way is something to strive for outside of doing it to see if it can be done – it’s hard enough to get functional languages to handle this kind of waste of space efficiently with highly optimizing compilers. In current Ruby implementations it’s an approach that is just brutally inefficient.

    [Reply]

    ochronus Reply:
    February 18th, 2010 at 22:00

    @Vidar, what you point out is a good and fair point, but I wasn’t trying to implement the most efficient ruby quicksort version :) I wrote the first version to use in-place sorting on purpose, but my primary point was emphasizing ruby’s semi-functional side – maybe I chose the wrong example for this. Thanks for emphasizing the inefficiency of the last solution though, it’s a great addition to the whole picture.

    [Reply]

  5. homoiconic
    February 18, 2010

    I look forward to the next post, this one was good. I especially liked showing a progression of versions to the code. Thanks!

    This comment was originally posted on Reddit

    [Reply]

  6. luikore
    February 19, 2010

    I can tell a lot more practical functional tricks: # currying (1.9 only) plus4 = :+.to_proc.curry[4] # function as object (1.9 or 1.8 with activerecord) xs = [' a ', ' b ', ' c '] xs.each &:strip! # a short hand for "&:strip!.to_proc" # pattern matching x, *xs = ['a', 'b', 'c'] # pattern matching in proc params (1.9 only) # 1*2 + 3*4 + 5*6 + … (1..100).to_a.each_slice(2).inject(0) do |sum, (a, b)| sum + a*b end and everything is a Maybe Monad …

    This comment was originally posted on Reddit

    [Reply]

  7. ochronus
    February 19, 2010

    :)) Wow, really nice, thanks!

    This comment was originally posted on Reddit

    [Reply]

  8. Chad
    February 19, 2010

    I had given this some thought last month for one reason or another.

    Here’s my interpretation. The main difference being I make use of the handy partition method, also arguably functional in its own right.

    http://gist.github.com/288019

    [Reply]

  9. ochronus
    February 19, 2010

    @Chad, if you take a closer look, I also used the ‘partition’ method :) Thanks for the contribution!

    [Reply]

  10. yk
    March 2, 2010

    The lisp version is also beautiful
    (defun quicksort (lis) (if (null lis) nil
    (let* ((x (car lis)) (r (cdr lis)) (fn (lambda (a) (< a x))))
    (append (quicksort (remove-if-not fn r)) (list x)
    (quicksort (remove-if fn r))))))

    [Reply]

Trackbacks/Pingbacks

  1. Csaba Okrona - A simple example of how close to functional ruby can be: http://is.gd/8F51L
  2. Atamert Ölçgen - RT @ochronus: A simple example of how close to functional ruby can be: http://is.gd/8F51L
  3. uberVU - social comments - Social comments and analytics for this post... This post was mentioned on Twitter by ochronus: A simple example of how close ...
  4. bunny_car - http://tinyurl.com/yayzb5n Functional ruby – a simple example | implements Developer {
  5. Ruby News - Functional ruby – a simple example http://bit.ly/dsUMZz
  6. Tiago Fernandes - RT @ruby_news: Functional ruby – a simple example http://bit.ly/dsUMZz
  7. Jérémy Lecour - Functional ruby – a simple example http://bit.ly/dsUMZz /via @ruby_news
  8. Richard Laksana -
  9. leo - RT @ruby_news: Functional ruby – a simple example http://bit.ly/dsUMZz
  10. Rajesh - Functional ruby - a simple example http://bit.ly/d3GZdr
  11. ??????? - Functional ruby - a simple example http://bit.ly/d3GZdr
  12. Queiroga - "Functional ruby – a simple example" http://is.gd/8QGLE #Ruby … Our old nemesis from college: The Quicksort algorithm.
  13. yangliulin -

Leave a Reply

Additional comments powered by BackType