OrderedList 和 SortedList 有什么区别

Question

Test.QuickCheck.Modifiers 同时提供 OrderedList 和 SortedList。

SortedList 的文档说：

Sorted xs: guarantees that xs is sorted.

OrderedList 的文档说：

Ordered xs: guarantees that xs is ordered.

（我猜这些应该分别是 SortedList xs 和 OrderedList xs）。

有序列表和有序列表有什么区别？

Answer 1

tl;dr：我认为 OrderedList 应该被弃用，它的 shrink 实现移植到 SortedList.

它们都被定义为

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

但 Foo 的选择不同。（顺便说一句：这解释了为什么文档说 Sorted xs 和 Ordered xs 而不是 SortedList xs 和 OrderedList xs —— 这些是 computation-level 术语，而不是 type-level 个，所以文档是正确的！）

除了实例之外，没有可用的特殊帮助函数，因此如果有差异，那一定是在实例中。两者都导出 (Eq, Ord, Read, Show, Typeable)，所以没有区别。

OrderedList 有一个 Functor 实例而 SortedList 没有，但我认为 OrderedList 也不应该有一个：它的 fmap 有不保留被订购文档所承诺的不变性。这个事实是我对是否弃用 SortedList 或 OrderedList 的迫切需要：弃用具有错误 Functor 实例的那个，这样您只有一个 backwards-incompatible 更改删除类型，而不是弃用一个并从另一个中删除一个坏的 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 实现。）

OrderedList 和 SortedList 有什么区别

What's the difference between OrderedList and SortedList

haskell

quickcheck