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

有没有变种

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

最佳答案

您可以调整 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] 中的所有 i，f xi x(i+1) 是 Just LT 或 Just EQ 。

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

关于使用 "a -> a -> Maybe Ordering"函数对列表进行排序，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40053153/