3

Haskell では、[a] のデフォルトの順序付けは、a の順序付けが与えられた場合、辞書式の順序付けのようです (副次的な質問: これが実際に当てはまるかどうかはどこで確認できますか)? 私が欲しいのは、段階的な辞書式順序付け (「長さと辞書式」順序付けとも呼ばれます) です。

段階的な辞書式の方法で比較を行うように指定するにはどうすればよいですか? すべての [a] ではなく、1 つのタイプのみに使用したい。私はこれを試しました：

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 に答える