Создание экземпляров Ord с переносом нового типа

Учитывая такой тип данных, как

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

Неужели делегирование экземпляру Ord Int - это такое безумие? Это кажется более безопасным и намного менее трудоемким, чем писать сравнения n ^ 2 для compare.

Какие-нибудь очевидные недостатки, которые я мог упустить из виду с помощью этого "хака"? Это вообще "взлом"?


typeclass haskell newtype
person SimonF    schedule 01.08.2016    source источник

Ответы (3)


arrow_upward
5
arrow_downward

Вам нужно только 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 составляет половину (fromEnum) минимальной реализации экземпляра класса Enum, который затем можно использовать для определения своего 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
person chepner    schedule 01.08.2016
comment
Это фантастическая информация, спасибо. Замечание о взаимосвязи между моим f и Enum классом типов захватывает. - person SimonF; 01.08.2016

arrow_upward
7
arrow_downward

Это абсолютно разумно. Фактически, вы можете использовать функцию comparing из _2 _ чтобы сделать это еще более прямым:

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 может быть вам больше по вкусу.

person Alexis King    schedule 01.08.2016

arrow_upward
0
arrow_downward

Как насчет создания функции для генерации сопоставления от 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

Вы даже можете добавить утверждение, чтобы убедиться, что все элементы встречаются в списке ровно один раз.

person Thilo    schedule 01.08.2016
comment
Я думаю, что предпочитаю внутреннее сопоставление с образцом экземпляру, главным образом потому, что, хотя ваш fooOrdering сохраняет некоторые символы, он позволяет предоставить некоторые довольно бессмысленные значения, например, [Bar, Bar, Bar, Bar]. В то время как сопоставление с образцом будет предупреждать о таких вещах. Впрочем, я полагаю, вы могли бы полностью засадить Интов. - person SimonF; 01.08.2016
comment
@SimonF: Я думал, что вы предотвратите бессмысленные значения, добавив утверждение, чтобы убедиться, что все элементы встречаются в списке ровно один раз. Но вы правы, компилятор уже сделает это для сопоставления с образцом. - person Thilo; 01.08.2016
comment
Еще одна вещь, которая мне не нравится в моем решении, - это то, что оно должно перебирать список во время выполнения для каждого сравнения. Было бы неплохо иметь статическую карту, созданную во время компиляции (или, по крайней мере, запомненную после первого использования). - person Thilo; 01.08.2016