Sorting the list using the function "a & # 8594; a & # 8594; Maybe Ordering"

Question

Is there an option

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

(in Data.List) which allows me to use the sort function a -> a -> Maybe Orderinginstead a -> a -> Ordering?

What this option will do is:

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

If a -> a -> Maybe Orderingit ever returns Nothingwhen it called during sorting, it sortBy'returned Nothing. Otherwise, it will return a sorted list enclosed in Just.

If this option is not yet available, can you help me build it? (Preferably one that is at least effective as sortBy.)

Answer 1

You can adapt quickSort:

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], , : [1..n-1], f xi x(i+1) Just LT Just EQ.

f (), [x1,..., xn] .