What's the difference between OrderedList and SortedList

Question

Test.QuickCheck.Modifiers provides both OrderedList and SortedList.

The documentation for SortedList says:

Sorted xs: guarantees that xs is sorted.

The documentation for OrderedList says:

Ordered xs: guarantees that xs is ordered.

(I'm guessing those should say SortedList xs and OrderedList xs respectively).

What is the difference between a list that is ordered and a list that is sorted?

Answer 1

tl;dr: I think OrderedList should be deprecated, and its shrink implementation ported to SortedList.

They are both defined as

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

but with different choices of Foo. (As an aside: this explains why the documentation says Sorted xs and Ordered xs not SortedList xs and OrderedList xs -- these are computation-level terms, not type-level ones, so the documentation is correct!)

There are no special helper functions available other than instances, so if there is a difference it must be in the instances. Both derive (Eq, Ord, Read, Show, Typeable), so no difference there.

OrderedList has a Functor instance while SortedList doesn't, but I think OrderedList shouldn't have one either: its fmap does not preserve the invariant promised by the documentation of being ordered. This fact is my desiderata for whether to deprecate SortedList or OrderedList: deprecate the one with the bad Functor instance, so that you have just one backwards-incompatible change of removing a type, rather than deprecating one and removing a bad Functor instance from the other.

The Arbitrary instances are nearly identical:

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)
    ]

So the only difference in behavior is that OrderedList does an equality check while SortedList doesn't. This means that the SortedList instance does less work inside shrink but produces more duplicate elements. The OrderedList choice is a better tradeoff if an equality check is cheaper than checking the property you are currently trying to find a minimal case for; that seems likely to be the case in most situations to me.

(One can almost certainly produce a more efficient shrink implementation than either of these.)