Hacker News Reader

Comment by madog | Hacker News Reader

I definitely agree with the documentation side of things, particularly lack of concrete examples.

I found that overall however, learning Haskell made me a better programmer, even if it's more useful as more of an academic than practical language.

Dealing with pure functions, no access to loops so recursion is paramount and it is rather beautiful and useful some of the tail recursion and pattern matching stuff.

The Haskell quicksort is the classic example of this:

  quicksort [] = []
  quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser = filter (< p) xs
        greater = filter (>= p) xs

View on HN

> The Haskell quicksort is the classic example of this:

The Haskell quicksort is also classic example of something that is small, beautiful and still misses the point. Yes, it contains the core idea of quicksort (partion the list and divide and conquer) but it completely fails on the quick part, because the Haskell lists are are leaky abstraction of real computer memory.

A real quicksort in Haskell is much more convoluted.

What's a real quicksort anyway? You could argue that a reasonably fast implementation of quicksort is much more convoluted, which it most certainly is, but that doesn't make this implementation any less real.

> What's a real quicksort anyway?

A key aspect of quicksort is that it sorts the list in-place. If you dont sort in-place, you dont have quicksort and if you dont need in-place sort, then quicksort is the wrong choice anyway.

Of course, canonical Haskell does not have a concept of in-place, which makes showing quicksort in Haskell also a questionable idea.

> You could argue that a reasonably fast implementation of quicksort is much more convoluted, which it most certainly is, but that doesn't make this implementation any less real.

A reasonably fast implementation of quicksort is straight-forward in any language that has arrays/vectors with destructive updates. This implementation will have issues with pathological cases, but that's a problem of the quicksort algorithm, not of the implementation (whereas the Haskell one shown above has problems in the implementation).

Sounds like a hardware issue.

Which hardware does not have this issue?

One cann do this in Python, or any other language for that matter:

  def quicksort ( xs ):
   if len(list) == 0:
    return []
   else:
    less = [x for x in xs[1:] if x <= xs[0]]
    more = [x for x in xs[1:] if x >  xs[0]]
    return less + [xs[0]] + more

Not the most efficient implementation in either.

And IMO, that python version is one million % more readable. In particular, because you defined more and less before using them, vs after in the Haskell example. I don't know if there's a way that could be achieved in Haskell too though.

Edit: you forgot the recursive calls though.

Haskell has a `let ... in` syntax. Quoting from (1):

    quicksort1 :: (Ord a) => [a] -> [a]
    quicksort1 [] = []
    quicksort1 (x:xs) =
      let smallerSorted = quicksort1 [a | a <- xs, a <= x]
          biggerSorted = quicksort1 [a | a <- xs, a > x]
      in  smallerSorted ++ [x] ++ biggerSorted

1: http://learnyouahaskell.com/recursion

I used to think so as well, until I realised at some point that defining things like this means you focus on the actual "business logic" up front, but the applicable definitions are never far (visually, spatially and logically). In my opinion it lets you get to grips on the overall logic before hassling you with certain specifics.

The term "business logic" itself tends to be somewhat controversial:

https://adsharma.github.io/flattools-programs/

@wheybags I recommend achieving defined-before-use quicksort by throwing in some unnecessary Haskell syntax extensions:

  qs :: Ord a => [a] -> [a]
  qs = \case
    [] -> []
    (x : (partition (< x) -> (qs -> as, qs -> bs))) -> as <> [x] <> bs

True, although you forgot the recursion. The Haskell filter expression is much nicer as well. You could perhaps be terser by using ternary conditionals:

  def quicksort ( xs ):
   return [] if len(list) == 0 else quicksort([x for x in xs[1:] if x <= xs[0]]) + xs[0] + quicksort([x for x in xs[1:] if x > xs[0]])

It's worth noting though that in-place quicksort really doesn't play to Haskell's strengths - there are some examples of the code for it here: https://stackoverflow.com/questions/7717691/why-is-the-minim...

That is quite elegant for that variant, which is a great fit for Haskell's features. How easy is it to write a different variant, like using a different pivot, or sorting in place?

> I found that overall however, learning Haskell made me a better programmer

I had the same experience, but with ML. It almost feels like Haskell with the annoying parts removed.

Quicksort in one line:

    Quicksort = { []->[], [p,,m]->this(m??<p) + (m??==p) + this(m??>p) }

> I found that overall however, learning Haskell made me a better programmer,

I definitely had that experience, too!

Reply on news.ycombinator.com