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.

I really enjoyed working with Haskell in college - for some reason it clicked with me. Good memories... — Mayo
– Mayo, Commented Sep 11, 2009 at 20:27
Nice answers lads - thats exactly what i was looking for - cheers! — Donal.Lynch.Msc
– Donal.Lynch.Msc, Commented Sep 11, 2009 at 20:29
An additional question for others: what is the major weakness with this algorithm? — Kathy Van Stone
– Kathy Van Stone, Commented Sep 11, 2009 at 21:09
@Kathy: It doesn't sort in place. Now this does feel like school :) — Shaun
– Shaun, Commented Sep 12, 2009 at 3:04
@Shaun: No, thats just a minor inefficiency. Think about its behaviour when faced with [1..100]. — Paul Johnson
– Paul Johnson, Commented Sep 17, 2009 at 20:08

sepp2k · Accepted Answer · 2009-09-12 11:12:04Z

13

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

edited Sep 12, 2009 at 11:12

answered Sep 11, 2009 at 20:10

sepp2k

372k56 gold badges687 silver badges687 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Mayo · Accepted Answer · 2009-09-11 20:25:50Z

4

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.

edited Sep 11, 2009 at 20:25

answered Sep 11, 2009 at 20:19

Mayo

10.8k7 gold badges48 silver badges91 bronze badges

1 Comment

sepp2k Over a year ago

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

Don Stewart · Accepted Answer · 2009-09-12 09:06:48Z

2

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

answered Sep 12, 2009 at 9:06

Don Stewart

138k36 gold badges372 silver badges472 bronze badges

Comments

MrHus · Accepted Answer · 2009-09-12 11:15:39Z

2

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

answered Sep 12, 2009 at 11:15

MrHus

33.5k6 gold badges33 silver badges31 bronze badges

Comments

yairchu · Accepted Answer · 2009-09-12 20:44:43Z

2

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

answered Sep 12, 2009 at 20:44

yairchu

25k7 gold badges72 silver badges117 bronze badges

Comments

Rich Seller · Accepted Answer · 2009-09-11 20:16:58Z

0

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

answered Sep 11, 2009 at 20:16

Rich Seller

84.3k23 gold badges176 silver badges179 bronze badges

Collectives™ on Stack Overflow

Haskell - Functional Programming Help

6 Answers 6

Comments

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Comments

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related