CODEWITHSUNDEEP
haskellquicksort
Артём Царионов
Артём Царионов

Reputation: 1037

Quicksort with custom filter

I need to make quicksort but with a custom filter. During compilation I get an error on filter (>=x) xs.

--sort with two filters
quicksort (x:xs) = (quicksort lesser) ++[x] ++ (quicksort greater)
                  where lesser  = filter (<x) xs
                        greater = filter (>=x) xs

--sort with custom filter
csort f (x:xs) = (csort f lesser) ++ [x] ++ (csort f greater)
                    where lesser  = [e | e <- xs, f x e]
                          greater = [e | e <- xs, not $ f x e]

What is wrong?

Upvotes: 2

Views: 776

Answers (1)

Dan Burton
Dan Burton

Reputation: 53665

There are two problems I think might be troubling you.

First of all, loading a file with your definitions into ghci, I try

ghci> csort (>= x) [2,1,3]

<interactive>:1:10: Not in scope: 'x'

The way you wrote it, f takes two parameters. And indeed x is not in scope here. So the custom filter function should be simply (>=).

ghci> csort (>=) [2,1,3]
***Exception: blahblah: Non-exhaustive patterns in function csort

Now the real problem: non-exhaustive patterns. What does this mean? You've written a definition of how to sort a list with at least one element. But how do you sort a list with no elements? Simple, you ignore the custom filter function, and simply produce an empty list. Since an empty list has no elements, it is already "sorted".

csort _ [] = []

Once I added that line to the source file, it suddenly worked. The pattern [] compliments the pattern (x:xs), and those two patterns, together, are exhaustive (a list is either empty, or it has at least one element).

ghci> csort (>=) [2,1,3]
[1,2,3]
ghci> csort (<) [2,1,3]
[3,2,1]
ghci> quickCheck (\xs -> csort (<) xs == (reverse $ csort (>) xs))
+++ OK, passed 100 tests.

Here's my sort.hs file:

csort _ [] = []
csort f (x:xs) = csort f lesser ++ [x] ++ csort f greater
  where lesser  = [e | e <- xs, f x e]
        greater = [e | e <- xs, not $ f x e]

I have no idea why you would still have errors; this works perfectly well for me.

Upvotes: 2

Related Questions