Быстрая сортировка с предикатом


Я хочу передать предикат в быстрой сортировки. Вопрос я бегу в том, что предикат должен иметь два аргумента, стержень и элемент списка, хвост. Насколько я знаю, предикаты могут иметь только 1 аргумент. Вот что я так далеко (он работает, я просто хочу улучшить его):

import Data.List

quicksort :: [a] -> (a -> a -> Bool) ->  [a]
quicksort [] _ = []
quicksort (x:xs) pf = quicksort left pf ++ [x] ++ quicksort right pf
    where   pred = pf x
            pt = partition pred xs
            left = fst pt
            right = snd pt


Комментарии
3 ответа

Как 200 сказал, предикат должен быть первым. Думаю filter, takeWhile, dropWhile и аналогичные функции. Они занимают первое сказуемое.

Кроме того, это обычно хорошая идея, чтобы избавиться от аргументов, которые повторяются в каждом рекурсивном вызове. С GHC должны позаботиться об этом, но мы можем помочь ему немного:

quicksort :: (a -> a -> Bool) -> [a] -> [a]
quicksort pf = go
where
go [] = []
go (x:xs) = go left ++ [x] ++ go right
where (left, right) = partition (comp x) xs

Тем не менее, мы сортировки. Поэтому вызов функции сравнения предикат является неправильным. Предикат-это функция a -> Bool, в то время как a -> a -> Bool это сравнение. Но a -> a -> Bool не передать его смысл по своему типу. Мы возвращаемся True если первым придет первым в отсортированном договоренности? Или же мы возвращаемся False? Будет quickSort (>) сортировка по возрастанию или по убыванию?

Эти вопросы легче ответить, если мы используем a -> a -> Ord вместо. Эта подпись следующее compare'ы, у нас есть довольно хорошее чувство, что x `compare` y = LT средства, а именно: x < y справедливо.

Если мы помним об этом, мы можем написать следующие варианты:

quicksortBy :: (a -> a -> Ord) -> [a] ->  [a]
quicksortBy comp = go
where
go [] = []
go (x:xs) = go lesser ++ (x : equal) ++ go greater
where
(lesser, equal, greater) = partitionOrd (`comp` x) xs

quicksort :: Ord a => [a] -> [a]
quicksort = quicksortBy compare

Определение partitionOrd :: (a -> Ord) -> [a] -> ([a], [a], [a]) остается в качестве упражнения. Другие, чем, что хорошо сделано. Имейте в виду, что это не очень быстрой сортировки, хотя.

3
ответ дан 30 января 2018 в 06:01 Источник Поделиться

Чтобы облегчить карринг, вы должны устроить параметров с наименьшей вероятностью могут различаться, скорее всего, отличаться. Если вы ставите на первое место предиката, то вы могли бы написать эти частичные функции:

ascQuicksort = quicksort (>)
descQuicksort = quicksort (<)

Есть where статья должна быть упрощена.

import Data.List

quicksort :: (a -> a -> Bool) -> [a] -> [a]
quicksort _ [] = []
quicksort pf (x:xs) = quicksort pf left ++ [x] ++ quicksort pf right
where (left, right) = partition (pf x) xs

2
ответ дан 30 января 2018 в 12:01 Источник Поделиться

Я не написал Хаскелл в некоторое время, поэтому я не могу дать хороший отзыв, но я что-то вижу, что можно улучшить, на что мне кажется немного назад. Вы создаете where привязки left и right даже если вы только использовать каждый раз, но писать quicksort * pf дважды и не создавать привязки.

У меня есть личная любовь к используя локальные функции, чтобы привести в порядок код, так что я бы, наверное, написать свой код как-то ближе:

quicksort :: [a] -> (a -> a -> Bool) ->  [a]
quicksort [] _ = []
quicksort (x:xs) pf = recur (fst pt) ++ [x] ++ recur (snd pt)
where pred = pf x
pt = partition pred xs
recur sub = quicksort sub pf

Используя recurвы можете удалить дубликаты рекурсией звонки. Кроме того, ликвидация left и right привязки можно сократить до where что я лично считаю так.

1
ответ дан 30 января 2018 в 12:01 Источник Поделиться