3

在 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.

感谢您的任何帮助！

4

3 回答 3

10

这是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.

于 2013-11-10T12:39:52.980 回答
6

这里有两个问题：

Ord [a]长得怎么样？

当然，您可以在 内进行试验GHCi，但也许您想要更可靠的东西。这非常困难，尤其是列表的定义（由于它们的特殊语法）内置于编译器中。让我们问 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]而且只能有一个。使用FlexibleInstancesand OverlappingInstances，您可以让它使用替代实例，例如[Int]，但它的风格很糟糕。正如 leftaroundabout 所写，使用 aNewtypeWrapper或使用参数化函数，如sortBy.

于 2013-11-10T12:45:56.190 回答
5

为 s 列表创建一个全新的Ord实例对Int我来说似乎有点重量级（更不用说您可能会造成混乱：稍后出现您的代码的人可能会期望默认的、未分级的词典比较行为）。

如果您只是希望不必在每次使用时都复制自定义比较代码sortBy等，那么实际上有一种相当轻量级的方法可以在现场定义像您这样的链式比较函数。Ordering碰巧是 的一个实例Monoid，这意味着您可以根据一系列标准比较两个事物，然后使用函数（最近缩写为）组合Ordering这些比较的结果。这一切都在Learn You a Haskell 关于 Monoids 等的章节中进行了详细解释，这就是我学习技巧的地方。所以：Monoidmappend<>

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 idis just compare，但为了统一起见......）然后写这样的东西就变得相对轻松了

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

这也具有您的继任者会立即看到您正在使用自定义比较功能的优点。

更新：leftaroundabout 在下面指出，我们可以实现更高的优雅——毕竟这是 Haskell，在 Haskell 中，我们总是可以实现更高的优雅——通过使用 monoid 实例，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 。（请注意，我们没有使用from (1)。）将所有内容写在一个大链中，我们有mappendOrderingMonoidmappend

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

漂亮的。

于 2013-11-11T11:58:21.713 回答