Haskell - Functional Programming Help

Question

Trying to get a feel for haskell. Am a seasoned programmer with PHP, JAVA, VB and many other languages, but am finding haskell slightly more difficult to follow. Can anyone give me an english translation for the following haskell function, to get me started...

quicksort []     = []
quicksort (x:xs) = quicksort [y | y <- xs, y<x ]
                   ++ [x]
                   ++ quicksort [y | y <- xs, y>=x]

An example of english translation is in the comments below:

// --- FOR_LOOP ->
// --- $abc goes from 1 to 10 ->
// --- If $abc is even - print $abc is even ->
// --- else if $abc is odd - print $abc is odd ->
// --- END_FOR_LOOP

for( $abc = 1 ; $abc <= 10 ; $abc++ ){

  if( $abc % 2 == 0 ){
    echo $abc . " is even";
  }
  else{
    echo $abc . " is odd";
  }
}

The first line is straightforward enough, reading: "Function quicksort on an empty list yields an empty list as the result"... If you can translate the remainder of the haskell into english that would be very helpfull.

Answer 1

The result of quicksorting the empty list is the empty list.

The result of quicksorting a non-empty list, where we call the first element of the list x and the remaining elements xs is: The result of quicksorting all the elements of xs that are smaller than x (*), followed by x, followed by the result of quicksorting all the elements of xs that are greater than x.

(*) To elaborate a bit: [y | y <- xs, y<x ] can be read as "the list of all y where y is in xs and y<x".

Answer 2

Haven't done this since college...

It's recursive - the first line is the case for an empty set.

quicksort []     = []

The next few lines operate on a non-empty set. The (x:xs) syntax breaks it up into a single element (x) and the remaining elements (xs).

quicksort (x:xs) = quicksort [y | y <- xs, y<x ]
  ++ [x]
  ++ quicksort [y | y <- xs, y>=x]

The first line, quicksort [y | y <- xs, y<x ], calls quicksort against the set of all elements from xs that are less than x (i.e. each y from xs that is less than x). If xs is the empty set, then quicksort [] will return [].

The middle line is simply the set containing x.

The last line, quicksort [y | y <- xs, y>=x], calls quicksort against the set of all elements from xs that are greater than or equal to x (i.e. each y from xs that is greater than or equal to x). If xs is the empty set, then quicksort [] will return [].

The end result is an ordered set.