Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Quicksort is the new Hello World

blog.rmontanaro.com

Post reply on HN
Print view View original

61–64 of 64 posts

Re: Quicksort is the new Hello World

#61

Post by [deleted] »

hristov wrote: post #44
l0stman wrote: post #9

qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater where lesser = filter ( = p) xs I know nothing about Haskell but I don't think this code implements the original quicksort algorithm which sorts the input in-place. Moreover the two-pass of filter over the list and the concatenations cause unnecessary overhead. Thus, even if the sample code is simple and elegant, a real-wor…

Ok, I am still learning Haskell, but I thought I would try to fix the above so that there is only one filter pass: qsort :: Ord a => [a] -> [a] qsort [] = [] qsort [x] = [x] qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater where (lesser, greater) = foldl split ([],[]) xs where split (left, right) x = if x Does this work?

[deleted]

Re: Quicksort is the new Hello World

#62

Post by fleitz »

dshankar wrote: post #3

For a veteran programmer learning a new language like Haskell, I agree completely. For a novice programmer learning their first language, they probably don't understand the quicksort algo and probably have no concept of arrays or any data structure. Visually displaying "Hello World" is very simple and teaches you two basic parts of a language: - Syntax - Printing stuff On another note, someone learning HTML for the f…

I don't believe HTML is Turing complete, and thus it's difficult to argue that it is indeed a language for computing.

Re: Quicksort is the new Hello World

#63

Post by l0stman »

hristov wrote: post #44
l0stman wrote: post #9

qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater where lesser = filter ( = p) xs I know nothing about Haskell but I don't think this code implements the original quicksort algorithm which sorts the input in-place. Moreover the two-pass of filter over the list and the concatenations cause unnecessary overhead. Thus, even if the sample code is simple and elegant, a real-wor…

Ok, I am still learning Haskell, but I thought I would try to fix the above so that there is only one filter pass: qsort :: Ord a => [a] -> [a] qsort [] = [] qsort [x] = [x] qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater where (lesser, greater) = foldl split ([],[]) xs where split (left, right) x = if x Does this work?

I had to look up what the `:' operator does and it adds an element to the beginning of the list. So the last line should be

    split (left, right) x = if x

Re: Quicksort is the new Hello World

#64

Post by merijnv »

sizzla wrote: post #58
merijnv wrote: post #53

Earlier quoted context omitted.

> That means there is a lot of overhead for doing something simple like an in-place qsort Well, the problem not so much that there is a lot of overhead for doing an in-place qsort. The problem is that "in-place" anything is impossible in Haskell, it violates referential transparency. Merge sort however needs no in-place update and can trivially (in Haskell world) be parallelized (merge sort is associative, you can us…

If you want to be terse, you can just use typedefs but most of ISO C++03 libraries just assume your editor can autocomplete quickly. The culture is different and absolute clarity is preferred over terseness. There's a lot of infrastructure behind MapReduce and I bet you any implementation is going to have a lot more code in it than what is in Data.List. Once things are in RAM (say, less than 1 GB), quicksort is the f…

Well, I didn't mean an actual MapReduce cluster, that's just silly. I was just pointing out that Haskell compilers can convert trivially convert these sorts of things to multicore code. Parallel Haskell basically does this, converting normal code to easy multicore code.

My point wasn't about using Haskell for high performance computing, my point was that Haskell's compiler can convert normal Haskell code to multicore code without (much, if any) work from the programmer. There is a large gap in between sequential single threaded program and a full MapReduce cluster and I think there is a significant amount of software written in this gap where Haskell-like languages could help with the parallelism/concurrency. The only reason I referenced MapReduce is since its a well known example even for people who are not well versed in functional programming (its a very common concept in functional programming).

Post reply on HN