在列表上使用不同的排序

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)

或者,您可以公开使用列表,但不是Ord像受约束的函数那样sort使用接受自定义比较函数的更通用的替代函数,例如sortBy gradedLexOrd.

Answer 2

这里有两个问题:

Ord [a]看起来怎么样？

当然你可以在里面试验GHCi,但也许你想要更可靠的东西.这是非常困难的,特别是因为Lists的定义(由于它们的特殊语法)内置于编译器中.我们问GHCi:

Prelude> :info []
data [] a = [] | a : [a]    -- Defined in `GHC.Types'
instance Eq a => Eq [a] -- Defined in `GHC.Classes'
instance Monad [] -- Defined in `GHC.Base'
instance Functor [] -- Defined in `GHC.Base'
instance Ord a => Ord [a] -- Defined in `GHC.Classes'
instance Read a => Read [a] -- Defined in `GHC.Read'
instance Show a => Show [a] -- Defined in `GHC.Show'

它说明了实例的定义GHC.Classes,我们在GHC的git repo中找到了它,它说:

instance (Ord a) => Ord [a] where
        {-# SPECIALISE instance Ord [Char] #-}
        compare []     []     = EQ
        compare []     (_:_)  = LT
        compare (_:_)  []     = GT
        compare (x:xs) (y:ys) = case compare x y of
                                    EQ    -> compare xs ys
                                    other -> other

所以是的,确实是词典排序.

如何覆盖订购？

别.有一个实例,[a]只有一个.使用FlexibleInstances和OverlappingInstances,你可以让它使用替代实例,比方说[Int],但它是糟糕的风格.就左下角写道,使用NewtypeWrapperfor,或使用参数化函数sortBy.

Answer 3

Ord为Ints 列表创建一个全新的实例似乎对我的品味有点重要(更不用说你可能会播下混乱:后来遇到你的代码的人可能会期望默认的,非分级的词典比较行为).

如果您只是希望每次使用时都不必复制自定义比较代码sortBy,那么实际上有一种相当轻量级的方法来定义像您这样的链式比较函数.Ordering事实上,它是一个实例Monoid,这意味着你可以根据一系列标准比较两件事,然后Ordering使用Monoid函数mappend(最近缩写为<>)组合这些比较的结果.这一点都在关于Monoids等的Learn You a Haskell章节中进行了详细解释,这是我从中汲取的技巧.所以:

import Data.Monoid ((<>))
import Data.Ord (comparing)

gradedLexicographicCompare :: (Ord a) => [a] -> [a] -> Ordering
gradedLexicographicCompare xs ys = comparing length xs ys <> comparing id xs ys

(当然,comparing id只是compare,但为了统一......)然后写出类似的事情变得相对繁琐

f = ... sortBy s ...
  where
    ...
    s xs ys = comparing length xs ys <> compare xs ys
    ...

而且这也有你的继任者会立即看到你正在使用自定义比较功能的优点.

更新:左下方指出我们可以实现更高的优雅 - 毕竟这是Haskell,而在Haskell中我们总是可以通过利用幺半群实例来实现更高的优雅instance Monoid b => Monoid (a -> b).也就是说,其结果是幺半群的函数本身可以被认为是幺半群.该实例由.给出

instance Monoid b => Monoid (a -> b) where
  mempty _ = mempty
  mappend f g x = f x `mappend` g x   (1)

现在让我们沉迷于一个小的等式推理,看看comparing length <> compare根据这个例子扩展到什么.应用(1)一次,我们有

comparing length <> compare
    = mappend (comparing length) compare
    = \xs -> mappend ((comparing length) xs) (compare xs)   (2)

但是,((comparing length) xs) :: [a] -> Ordering和(compare xs) :: (Ord a) => a -> Ordering本身的功能,其结果是类群,即OrderingS,所以我们可以应用(1)第二次获得

mappend ((comparing length) xs) (compare xs)
    = \ys -> mappend (((comparing length) xs) ys) ((compare xs) ys)   (3)

但现在(((comparing length) xs) ys)和((compare xs) ys)完全应用的功能.具体来说,它们是Orderings,从原始答案我们知道如何结合两个Orderings使用mappend的Ordering实例Monoid.(请注意,我们没有使用mappend(1).)在一个大链中写下所有内容,我们有

comparing length <> compare
    = mappend (comparing length) compare   [definition of <>]
    = \xs -> mappend ((comparing length) xs) (compare xs)   [by (1)]
    = \xs -> (\ys -> mappend (((comparing length) xs) ys) ((compare xs) ys))   [substituting (3) in (2)]
    = \xs -> \ys -> mappend (comparing length xs ys) (compare xs ys)   [function application is left associative]
    = \xs -> \ys -> comparing length xs ys <> compare xs ys   [definition of <>]

而这次扩张的最后一行就是我们的原创gradedLexicographicCompare!经过长时间的漫长讨论之后,我们可以写出优雅无分数的优点

gradedLexicographicCompare = comparing length <> compare

漂亮.