Premature optimization is the root of all evil (or at least most of it) in programming.

Donald Knuth

Functional Style Sorting in Ruby

Last week I was discussing with @romandreg about how sort algorithms could be so intuitive when you are thinking in a functional style. They become very succinct and expressive. After some thinking I implemented a version of insertion sort and quicksort in ruby following a functional style. First let’s see an example of insertion sort in a classic imperative style:
class Array
  def insertionsort!
    1.upto(length - 1) do |i|
      value = self[i]
      j = i - 1
      while j >= 0 and self[j] > value
        self[j+1] = self[j]
        j -= 1
      end
      self[j+1] = value
    end
    self
  end
end
n a functional style, you could think that there are two functions involved when you are doing insertion sort. One that inserts a given value where it belongs and another that reduces the original array using this function:
class Array
  def insertion_sort
    # Function to insert a value where it belongs
    # in an ordered array.
    insert_in_place = -> (array, new_elem) do
      head, *tail = array
      return [new_elem]  unless head
      if head > new_elem
        [new_elem] + array
      else
        [head] + insert_in_place.call(tail, new_elem)
      end
    end

    self.reduce([], &insert_in_place)
  end
end
Lets see how this same of kind of thinking applies to quicksort:
def quicksort(array)
  pivot, *tail = array
  return [] unless pivot
  left = tail.select { |elem| elem < pivot }
  right = tail.select { |elem| elem > pivot }
  quicksort(left) + [pivot] + quicksort(right)
end
I don’t know about you, but I think this is super awesome.

You should also be careful to not have addresses which are valid
alternate syntaxes to the inet_ntoa() library call. For example 0xe
is a valid name, but if you were to type “telnet 0xe”, it would try
to connect to IP address 0.0.0.14. It is also rumored that there
exists some broken inet_ntoa() routines that treat an address like
x400 as an IP address.

RFC 1912, Common DNS Operational and Configuration Errors