haskell - 在列表上使用不同的排序

Question

在 Haskell 中，[a] 的默认排序(给定 a 的排序)似乎是字典顺序(附带问题:我在哪里可以找到是否确实如此)？我想要的是分级字典顺序(也称为“长度加字典顺序”)。

我如何指定我希望以分级词典编排方式进行比较？我只想要一种类型，而不是所有[a]。我试过这个:

instance Ord [Int] where
  compare xs ys = case compare (length xs) (length ys) of
                          LT -> LT
                          GT -> GT
                          EQ -> lexicographic_compare xs ys

但收到此错误消息:

> [1 of 1] Compiling Main             ( test.hs, interpreted )
test.hs:1:10:
    Illegal instance declaration for `Ord [Int]'
      (All instance types must be of the form (T a1 ... an)
       where a1 ... an are *distinct type variables*,
       and each type variable appears at most once in the instance head.
       Use -XFlexibleInstances if you want to disable this.)
    In the instance declaration for `Ord [Int]'
Failed, modules loaded: none.

感谢您的帮助!

Answer 1

这是 newtype 包装器的典型应用:

newtype GradedLexOrd a = GradedLexOrd { runGradedLexOrd :: [a] }

instance (Ord a) => Ord (GradedLexOrd a) where
  compare (GradedLexOrd xs) (GradedLexOrd ys) = gradedLexOrd xs ys

gradedLexOrd :: Ord a => [a] -> [a] -> Ordering
gradedLexOrd = comparing length <> compare -- Nice Monoid-based implementation,
                                           --due to Aaron Roth (see answer below)

或者，您可以公开使用列表，但不使用像 sort 这样的 Ord 约束函数，而是使用接受自定义比较函数的更通用的替代方法，例如按gradedLexOrd排序。