使用换行创建订单实例

Question

给定等数据类型

data Foo = Bar | Baz | Qux

我希望为这种类型有多个不同的订单，以下是实现这一点的最常见/标准方法吗？

newtype FooPriorityA = FooPriorityA { unFooPriorityA :: Foo }
instance Ord FooPriorityA where
    compare (FooPriorityA x) (FooPriorityA y) = f x `compare` f y
        where f :: Foo -> Int
              f Baz = 1
              f Bar = 2
              f Qux = 3
newtype FooPriorityB = FooPriorityB ... and so on

授权给Int的Ord实例是这样疯狂吗？这感觉比为compare写下n^2个比较更安全，工作量也小得多。

我可能忽略了这个"黑客"的任何明显缺陷？这甚至是"黑客"吗？

Answer 1

这是绝对合理的。事实上，您可以使用Data.Ord中的comparing函数使其更加直接：

instance Ord FooPriorityA where
  compare (FooPriorityA x) (FooPriorityA y) = comparing f x y
    where f :: Foo -> Int
          f Baz = 1
          f Bar = 2
          f Qux = 3

尽管根据您的喜好，带有compare的版本可能更符合您的喜好。

Answer 2

您只需要O（n）（确切地说，2​；n-1）定义即可指定总顺序，只要您按优先级递增的顺序指定案例即可：

instance Ord FooPriorityA where
    compare (FooPriorityA x) (FooPriorityA y) | x == y = EQ   -- Use the Eq instance
                                              -- Bar is the smallest
                                              | x == Bar = LT
                                              | y == Bar = GT
                                              -- Baz is the next smallest
                                              | x == Baz = LT
                                              | y == Baz = GT
                                              -- Proceed in the desired order.
                                              -- You don't need to say anything
                                              -- explicit about the largest value

第一种情况（x == y）涵盖了O（n）的可能性。后面的每一个案例看起来都可能不完整，但它隐含着前面每一个案件都是假的信息。例如，x == Bar = LT并不意味着其中x == Bar评估为LT的每个情况；已经处理了x == Bar && y == Bar的情况，所以第二种情况实际上是隐含的x == Bar && y /= Bar。

同样，情况4（x == Baz）承载y /= Baz（由情况1的匹配失败所暗示）和y /= Bar（由情况3的匹配失败而暗示）的假设。因此，y的任何剩余的可能值实际上都大于Baz。

列表越往下，未处理的案件就越少。最后，你不需要对最大的项目说任何明确的话；关于它与其他n-1项目的比较的所有信息都已经被前面的案例所捕获。

---

此外，请记住，您对f的定义是Enum类实例的最小实现的一半（fromEnum），然后您可以使用它来定义Ord实例。

instance Enum FooPriorityA where
     fromEnum Bar = 1
     fromEnum Baz = 2
     fromEnum Qux = 3
     toEnum 1 = Bar
     toEnum 2 = Baz
     toEnum 3 = Qux
instance Ord FooPriorityA where
    compare x y = compare (fromEnum x) (fromEnum y)
    -- compare = compare `on` Data.Function.fromEnum

Answer 3

如何制作一个函数，根据表示所需排序的列表生成从Foo到Int的映射：

import Data.List
data Foo = Bar | Baz | Qux deriving Eq
newtype FooPriorityA = FooPriorityA { unFooPriorityA :: Foo } deriving Eq
fooOrdering :: [Foo] -> Foo -> Foo -> Ordering
fooOrdering orderedList a b = f a `compare` f b
    where f x = elemIndex x orderedList
instance Ord FooPriorityA where
    compare (FooPriorityA x) (FooPriorityA y) = fooOrdering [Baz, Bar, Qux] x y

您甚至可以添加一个断言，以确保所有元素在列表中只出现一次。