В чем разница между OrderedList и SortedList - PullRequest
Новая
       42

В чем разница между OrderedList и SortedList

3 голосов
/ 08 июня 2019

Test.QuickCheck.Modifiers обеспечивает как OrderedList, так и SortedList.

Документация для SortedList гласит:

Sorted xs: гарантирует сортировку xs.

Документация для OrderedListговорит:

Ordered xs: гарантирует, что заказано xs.

(я предполагаю, что те должны сказать SortedList xs и OrderedList xs соответственно).

В чем разница между упорядоченным списком и отсортированным списком?

1 Ответ

3 голосов
/ 08 июня 2019

tl; dr: я думаю, OrderedList следует считать устаревшим, а его shrink реализация перенесена на SortedList.

Они оба определены как 

newtype FooList a = Foo { getFoo :: [a] }

, но сразличные варианты Foo.(В дополнение: это объясняет, почему в документации написано Sorted xs и Ordered xs, а не SortedList xs и OrderedList xs - это термины уровня вычисления, а не уровня типа, поэтому документация верна!)

Нет никаких специальных вспомогательных функций, кроме экземпляров, поэтому, если есть разница, они должны быть в экземплярах.Оба получают (Eq, Ord, Read, Show, Typeable), поэтому нет никакой разницы.

OrderedList имеет экземпляр Functor, а SortedList - нет, но я думаю, что OrderedList тоже не должен иметь его: его fmap не сохраняет инвариант, обещанный документацией заказа.Этот факт является моим желанием для того, чтобы осудить SortedList или OrderedList: осудить тот с плохим экземпляром Functor, чтобы у вас было только одно несовместимое с обратным изменением удаление типа, вместо того, чтобы отменить его и удалитьплохой Functor экземпляр от другого.

Arbitrary экземпляры практически идентичны: 

instance (Ord a, Arbitrary a) => Arbitrary (OrderedList a) where
  arbitrary = Ordered `fmap` orderedList

  shrink (Ordered xs) =
    [ Ordered xs'
    | xs' <- shrink xs
    , sort xs' == xs'
    ]

orderedList :: (Ord a, Arbitrary a) => Gen [a]
orderedList = sort `fmap` arbitrary

instance (Arbitrary a, Ord a) => Arbitrary (SortedList a) where
  arbitrary = fmap (Sorted . sort) arbitrary

  shrink (Sorted xs) =
    [ Sorted xs'
    | xs' <- map sort (shrink xs)
    ]

Таким образом, единственное различие в поведении состоит в том, что OrderedList выполняет проверку на равенство, в то время как SortedList нет.Это означает, что экземпляр SortedList выполняет меньше работы внутри shrink, но создает больше дублирующих элементов.Выбор OrderedList - лучший компромисс, если проверка на равенство дешевле, чем проверка свойства, для которого вы пытаетесь найти минимальное обоснование;мне кажется, что в большинстве ситуаций это так.

(Почти наверняка можно создать более эффективную реализацию shrink, чем любую из них.)

...