使用“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 一样高效。）

- haskellHQ

---

我不认为这是个好主意。结果是否为“Nothing”将取决于进行哪些比较，而进行哪些比较取决于使用哪种排序算法。检查所有可能的比较是否都是“Just”需要O(n^2)的时间。 - Cirdec

如果您描述一下您试图通过这样做达到什么目的，那将是有益的。为什么不事先确保向 sortBy 传递有效数据？是否有特定的应用场景？如果您这样做，我们可能能够更好地提供帮助。 - dkasak

我可以想象在拓扑排序中使用这样的函数，如果返回值是Nothing，那么你可以任意选择其中一个先出现。但在这种情况下，你也可以让函数返回LT而不是Nothing，仍然可以使用sortBy。 - chepner

@chepner，你这样尝试做拓扑排序不会搞砸吗？你可能会得出 x<y，然后又得出 y<x。 - dfeuer

@Cirdec 如果比较函数具有一些额外的属性，例如仅在元素足够接近时失败，但是始终保持一致，则此过程可以定义良好且与算法无关。在这种情况下，在排序过程中中止是最有效的方法：排序将相邻元素越来越靠近，但如果您已经在列表完全排序之前某个点上获得了失败（在这里您最终会遇到失败），则可以避免不必要的工作。 - leftaroundabout

@leftaroundabout @Cirdec 我认为具有传递性就足够了：即当两个比较 x<y,y<z 都成功（isJust）且结果为 LT 时，比较 x<z 必须成功（对于 GT,EQ 也是如此，包括混合情况）。当发生这种情况并且排序返回 Just 时，sort 执行的比较应该足以保证比较始终成功。 - chi

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

特别地，当f是一个偏序（传递）时，[x1,...,xn]是完全有序的。

- V. Semeria