Блог

Главная - Вопросы по программированию - Сортировка списка с использованием функции «a -> a ->, возможно, упорядочение»

Сортировка списка с использованием функции «a -> a ->, возможно, упорядочение»

#sorting #haskell

#сортировка #haskell

Вопрос:

Есть ли вариант

 sortBy :: (a -> a -> Ordering) -> [a] -> [a]

(в Data.List) это позволяет мне использовать a -> a -> Maybe Ordering функцию сортировки вместо a -> a -> Ordering ?

Что этот вариант будет делать, так это:

 sortBy' :: (a -> a -> Maybe Ordering) -> [a] -> Maybe [a]

Если a -> a -> Maybe Ordering когда-либо возвращается Nothing , когда он вызывается во время сортировки, sortBy' вернется Nothing . В противном случае он вернет отсортированный список, завернутый в Just .

Если такой вариант еще не доступен, не могли бы вы помочь мне его создать? (Предпочтительно тот, который, по крайней мере, так же эффективен, как sortBy .)

Комментарии:

1. Я не думаю, что это хорошая идея. Будет ли результат Nothing зависеть от того, какие сравнения выполняются, и какие сравнения выполняются, будет зависеть от того, какой алгоритм сортировки используется. Чтобы проверить, что все возможные сравнения Just будут, потребуется O (n ^ 2) времени.

2. Я думаю, было бы полезно, если бы вы описали нам, чего вы пытаетесь достичь с помощью этого. Почему бы просто не убедиться, что вы передаете действительные данные sortBy заранее? Имеется ли в виду вариант использования? Если вы сделаете это, мы сможем помочь лучше.

3. Я мог бы представить себе использование такой функции для топологической сортировки, где, если возвращаемое значение было Nothing , вы могли бы произвольно выбрать одно или другое, чтобы прийти первым. Но в этом случае вы могли бы с таким же успехом использовать функцию return LT вместо Nothing , и все равно использовать sortBy .

4. @chepner, разве ты не можешь все испортить, пытаясь выполнить подобную топологическую сортировку? Вы могли бы сделать вывод x<y и позже y<x .

5. @leftaroundabout @Cirdec Я думаю, что достаточно иметь транзитивность: т.Е. Всякий раз, когда два сравнения x<y,y<z завершаются успешно ( isJust ) с LT , тогда сравнение x<z должно завершиться успешно с LT (то же самое для GT,EQ , включая смешанные случаи). Когда это произойдет и сортировка вернется Just , выполняемых сравнений sort должно быть достаточно, чтобы гарантировать, что сравнение всегда будет успешным.

Ответ №1:

Вы можете адаптировать быструю сортировку :

 quickSortBy :: (a -> a -> Maybe Ordering) -> [a] -> Maybe [a]
quickSortBy f [] = Just []
quickSortBy f (x:xs) = do
  comparisons <- fmap (zip xs) $ mapM (f x) xs
  sortLesser <- quickSortBy f . map fst $ filter ((`elem` [GT, EQ]) . snd) comparisons
  sortUpper <- quickSortBy f . map fst $ filter ((== LT) . snd) comparisons
  return $ sortLesser    [x]    sortUpper

По крайней мере, предположим, что ваш предикат сортировки f :: a -> a -> Maybe Ordering является антисимметричным: f x y == Just LT тогда и только тогда, когда f y x == Just GT . Затем, когда quickSortBy f возвращается Just [x1,...,xn] , я думаю, у вас есть такая гарантия: для всех i в [1 ..n-1] f xi x(i 1) равно Just LT or Just EQ .

Когда, в частности, f является частичным порядком (транзитивным), то [x1, …,xn] полностью упорядочен.

Метки: , ,