Haskell - Functional Programming Help

Tag: haskell Author: lirentian Date: 2009-08-26

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.

I really enjoyed working with Haskell in college - for some reason it clicked with me. Good memories...
Nice answers lads - thats exactly what i was looking for - cheers!
An additional question for others: what is the major weakness with this algorithm?
@Kathy: It doesn't sort in place. Now this does feel like school :)
@Shaun: No, thats just a minor inefficiency. Think about its behaviour when faced with [1..100].

Best Answer

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".

Other Answer1

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.

comments:

"The end result is an ordered set." - It's not a set, it's a list. quicksort [1,2,3,1,2,3] will return [1,1,2,2,3,3]. Note the duplicate entries.

Other Answer2

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

Other Answer3

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

Other Answer4

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

Other Answer5

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