Archive for October, 2010

Uncategorized

Less is More: Opinionated Software

For the uninitiated, opinionated software is software that works the way its authors think it should work, instead of trying to please everybody. That means a lot of people will not like it, but the ones that do will love it.

I first came across this term after reading Getting Real from 37 Signals.They strongly advocate the development of opinionated software. Quoting from their guide:

Your app should take sides

Some people argue software should be agnostic. They say it's arrogant for developers to limit features or ignore feature requests. They say software should always be as flexible as possible.

We think that's bullshit. The best software has a vision. The best software takes sides. When someone uses software, they're not just looking for features, they're looking for an approach. They're looking for a vision. Decide what your vision is and run with it.

Sounds like another case of the "Paradox of Choice".

Uncategorized

The Brevity of Functional Languages

QuickSort is a well-known, efficient, sort algorithm. In previous posts I've discussed the runtime and space complexity of this algorithm, but there are some other factors that are rather important: brevity and clarity of code. Let's examine this by looking at the implementation of quicksort in C#, Java, C++ and F#.

Here is my version of quick sort in non-generic Java:

   1:      public static void quickSort(int[] input, int start, int finish)
   2:      {
   3:          if (finish-start < 2)
   4:              return;
   5:          
   6:          //pick a pivot
   7:          int pivotIndex = (finish+start)/2;
   8:          
   9:          //partition about the pivot
  10:          int i=start, j=finish;
  11:          while(i<=j)
  12:          {
  13:              while(input[i] < input[pivotIndex])
  14:                  i++;
  15:              
  16:              while(input[j] > input[pivotIndex])
  17:                  j--;
  18:              
  19:              if(i<=j)
  20:              {
  21:                  int temp = input[i];
  22:                  input[i]=input[j];
  23:                  input[j]=temp;
  24:                  i++;
  25:                  j--;
  26:              }
  27:          }
  28:          
  29:          if (start < i-1)
  30:              quickSort(input, start, i-1);
  31:          
  32:          if (i < finish)
  33:              quickSort(input, i, finish);        
  34:      }

And here it is in a generic C# flavour:

   1:          public static void QuickSort<T>(T[] input)
   2:                      where T : IComparable<T>
   3:          {
   4:              QuickSort(input, 0, input.Length - 1);
   5:          }
   6:   
   7:          public static void QuickSort<T>(T[] input, int start, int finish)
   8:              where T:IComparable<T>
   9:          {
  10:              if (finish - start < 2)
  11:                  return;
  12:   
  13:              //pick a pivot
  14:              int pivotIndex = (finish + start) / 2;
  15:   
  16:              //partition about the pivot
  17:              int i = start, j = finish;
  18:              while (i <= j)
  19:              {
  20:                  while (input[i].CompareTo(input[pivotIndex]) < 0)
  21:                      i++;
  22:   
  23:                  while (input[j].CompareTo(input[pivotIndex]) > 0)
  24:                      j--;
  25:   
  26:                  if (i <= j)
  27:                  {
  28:                      T temp = input[i];
  29:                      input[i] = input[j];
  30:                      input[j] = temp;
  31:                      i++;
  32:                      j--;
  33:                  }
  34:              }
  35:   
  36:              if (start < i - 1)
  37:                  QuickSort(input, start, i - 1);
  38:   
  39:              if (i < finish)
  40:                  QuickSort(input, i, finish);
  41:          }

Here's my C++ code :

   1:  void quickSort(int arr[], int left, int right) {
   2:        int i = left, j = right;
   3:        int tmp;
   4:        int pivot = arr[(left + right) / 2];
   5:   
   6:        /* partition */
   7:        while (i <= j) {
   8:              while (arr[i] < pivot)
   9:                    i++;
  10:              while (arr[j] > pivot)
  11:                    j--;
  12:              if (i <= j) {
  13:                    tmp = arr[i];
  14:                    arr[i] = arr[j];
  15:                    arr[j] = tmp;
  16:                    i++;
  17:                    j--;
  18:              }
  19:        };
  20:   
  21:        /* recursion */
  22:        if (left < j)
  23:              quickSort(arr, left, j);
  24:        if (i < right)
  25:              quickSort(arr, i, right);
  26:  }

Here's some Erlang code to do the same:

qsort([]) -> [];
qsort([Pivot|T]) ->
	qsort([X || X <- T, X =< Pivot])
	++ [Pivot] ++
	qsort([X || X <- T, X > Pivot]).

And finally, here's my F# code, that admittedly does it slightly differently in that it selects the first items as the pivot:

#light
open System
 
let rec quickSort ls =
  match ls with
  | [] -> []
  | p::r -> 
     quickSort [for i in r do if (compare i p) <= 0 then yield i] 
     @ [p] 
     @ quickSort [for i in r do if (compare i p) > 0 then yield i]          
 

I know I've mentioned it before on this site, but despite my deep admiration for C++ , Java and C# - they are all great languages - it's painfully clear that, with their advanced list comprehension syntax, functional languages are great at producing succinct code that is very easy to turn into highly parallelized code! With multi-core servers the norm these days these features of functional languages are extremely attractive.