Быстрая сортировка с пользовательским фильтром

Question

Мне нужно сделать быструю сортировку, но с пользовательским фильтром. Во время компиляции я получаю сообщение об ошибке 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]

Что не так?

Answer 1

Есть две проблемы, которые, я думаю, могут беспокоить вас.

Прежде всего, загружая файл с вашими определениями в ghci, я пытаюсь

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

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

Как вы написали, f принимает два параметра. И действительно, x здесь не входит в сферу применения. Так что пользовательская функция фильтра должна быть просто (>=).

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

Теперь настоящая проблема: неисчерпывающие закономерности. Что это значит? Вы написали определение, как сортировать список хотя бы с одним элементом. Но как вы сортируете список без элементов? Проще говоря, вы игнорируете пользовательскую функцию фильтра и просто создаете пустой список. Поскольку в пустом списке нет элементов, он уже "отсортирован".

csort _ [] = []

Как только я добавил эту строку в исходный файл, она неожиданно заработала. Шаблон [] дополняет шаблон (x:xs), и эти два шаблона вместе являются исчерпывающими (список либо пуст, либо содержит хотя бы один элемент).

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.

---

Вот мой файл sort.hs:

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]

Понятия не имею, почему у вас все еще будут ошибки; это прекрасно работает для меня.