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.

Uncategorized

List Comprehension in F#

List comprehension collectively refers to language features that make it easy to define lists. Often the creation of lists is based on modifications to an existing list (such as filtering it, or transforming it).

Prior to the introduction of Linq in the .NET 3.0 Framework there wasn't any real support for list comprehensions. However, since Linq came along you have all the standard query operators to query existing lists assigning the result to a new list. That all fine and dandy but the creation/initialization of lists (or arrays) was and still is rather limited in C#. There is the Enumerable class that offers the Range() and Repeat() methods but that's not at all overwhelming. Just to summarize, these Enumerable static methods can be used to perform array initialisation using fairly terse syntax as follows:

// array initialisation (for small arrays)
int[] x = Enumerable.Repeat(-1, 10).ToArray();
int[] y = Enumerable.Range(0, 10).ToArray();
int[] perfectSquares = Enumerable.Range(1, 10).Select(f => f*f).ToArray();


However, as many people found out this doesn't run nearly as fast as a simple for-loop to do the same thing. Why? Probably because Linq is iterating over the collection element by element and passing them through a lambda expression, dynamically allocation items to an array as it goes.

In F#, there is an elegant syntax called sequence expressions for generating lists, arrays and sequences (an IEnumerable is called "Seq" in F#). To create a sequence/list/array of consecutive integers you can do the following:

let seqOfLetters = seq {'A' .. 'Z'} // a sequence
let seqOfNumbers = seq {1 .. 10}    // a sequence
let listOfNumbers = [1 .. 10]       // a list
let arrayOfNumbers = [|1 .. 10|]    // an array
 


Note that the type of sequence generated is dependent on the bracket syntax you use.

To create non-consecutive numeric sequences (it won't work for character sequences) you can introduce a skip parameter as follows:

let seqOfEvenNumbers = seq {2 .. 2 .. 100}    // 2,4,6,8,...


Much like Linq in C#, you can also apply a filter to an existing sequence by using syntax of the following form:

seq { for pattern in container -> expr }

For example:

let listOfSquare = [ for i in 1..10 -> i*i ]


This is equivalent to the following:

let listOfSquare = [ for i in 1..10 do yield i*i ]


Don't get me wrong - I'm a big fan of C#, but there are some things that F# is better at, and list comprehension is one of them.

Uncategorized

Project Euler: Problem 25

This puzzle requires that we find the first Fibonacci number with 1000 digits.

Given what we have already created in problem 2 it is a fairly simple problem to solve. All we need to do is to introduce a new function that checks the digit count:

let hasYdigits x y =

    let upperLimit = BigInteger.Pow(10I,y-1)

    x >= upperLimit

 

let has1000digits (x : BigInteger) =  hasYdigits x 1000

Note that I'm being explicit about the type of the parameter because I want it to use BigIntegers.

Now the problem is solved by filtering out all elements in the infinite list that don't have 1000 digits and with the resulting sequence taking the first element (Seq.head) and then bailing out.

let euler25 = fibSet

                |> Seq.filter (fun x -> has1000digits x)

                |> Seq.head 

 

printfn "%A" euler25

Console.ReadLine() |> ignore

Next »