исправление только части куска кода «Фильтр» быстрой сортировки в Haskell - PullRequest
Новая
       16

исправление только части куска кода «Фильтр» быстрой сортировки в Haskell

0 голосов
/ 15 апреля 2019 
Filter :: (Ord a) => [a] -> [a]
 Filter [X:XS] = [[c|c<X, c<-XS ] ++ [X] ++ [c| c >X , c<-XS ]]
 quickSort :: Ord a => [a] -> [a]
 quickSort [] = []
 quickSort [x:xs] = quickSort mini ++ [x] + quickSort maxi
       where
           mini = filter xs
           maxi = filter xs

Корректна ли функция «Фильтр» с пониманием списка? Я знаю, что есть встроенная функция «Фильтр» в Haskell-библиотеках. Но я пытался написать код сам ...

1 Ответ

5 голосов
/ 15 апреля 2019

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

Всегда строчные буквы первой буквы идентификаторов.Это правило синтаксиса в Haskell, а не просто соглашение.

filter принимает в качестве параметра функцию типа (a -> Bool).Для него не требуется экземпляр Ord a.

В понимании списка термин генератора x <- xs должен идти слева от любых терминов, использующих x (то есть p x). 

filter :: (a -> Bool) -> [a] -> [a]
filter p xs = [x | x <- xs, p x]

quickSort :: Ord a => [a] -> [a]
quickSort [] = []
quickSort (x:xs) = quickSort mini ++ [x] ++ quickSort maxi
    where
        mini = filter (< x) xs
        maxi = filter (>= x) xs
...