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

This doesn't directly answer your question, but hoogle may help your learning in general, you can use it to search the standard api libraries by either function name, or by approximate type signature.

Here's examples of the search terms it supports:

map
(a -> b) -> [a] -> [b]`
Ord a => [a] -> [a]
Data.Map.insert

Answer 3

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.

Answer 4

It's a declarative language, so you just read off what you see. sepp2k does a good example above.

Answer 5

Check http://learnyouahaskell.com/recursion#quick-sort it explains exactly what quicksort does.

Answer 6

In case your problem was in-familiarity with list comprehensions, here's some alternative versions which are more or less the same:

quicksort []     = []
quicksort (x:xs) =
  quicksort (filter (< x) xs) ++
  [x] ++
  quicksort (filter (>= x) xs)

quicksort []     = []
quicksort (x:xs) =
  quicksort smaller ++ [x] ++ quicksort bigger
  where
    (smaller, bigger) = partition (< x) xs