使用 "a -> a -> Maybe Ordering"函数对列表进行排序

Question

是否有变体

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 一样高效。)

Answer 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 ==只是GT。然后，当 quickSortBy f 返回 Just [x1,...,xn] 时，我认为您有这样的保证:对于 [1..n-1] 中的所有 i， f xi x(i+1) 是Just LT 或Just EQ。

特别当 f 是偏序(传递)时，则 [x1,...,xn] 是全序的。