为什么不排序(a - > a - > Bool)？

Question

Haskell sortBy函数(a -> a -> Ordering)作为其第一个参数.任何人都可以教育我有什么推理吗？我的背景完全是在具有类似功能的语言中(a -> a -> Bool)取而代之,因此必须编写一个返回LT/ GT有点令人困惑的语言.

这是在静态类型/纯函数语言中执行此操作的标准方法吗？这是ML下降语言特有的吗？是否有它的一些基本的优点是,我没有看到,或者一些隐藏的DIS优势,使用布尔值呢？

---

总结:

• 一个Ordering不是GT | LT,它实际上GT | EQ | LT(显然GHC没有在引擎盖下使用它来进行分类,但仍然)

• 返回三分法值更接近地模拟两个元素的比较的可能结果

• 在某些情况下,使用Ordering而不是Bool将保存比较

• 使用an Ordering可以更容易地实现稳定的排序

• 使用a Ordering使读者清楚地知道两个元素之间正在进行比较(布尔值本身并不具备这个含义,尽管我感觉很多读者都会认为它)

我暂时接受了卡尔的回答,并发布了上述摘要,因为在此编辑中没有一个答案达到了所有要点.

Answer 1

我认为布尔盲症是主要原因.Bool是一种没有域语义的类型.它的语义在函数的情况下sortBy完全来自约定,而不是来自函数所在的域.

这为编写比较函数所涉及的心理过程增加了一个间接层次.而不只是说"我可以返回的三个值小于,等于或大于",排序的语义构建块,你说"我想要返回少于,所以我必须将它转换为布尔值".还有一个永远存在的额外心理转换步骤.即使你精通大会,它仍会让你慢下来.如果你不熟悉这个惯例,那么你必须检查一下它是什么,你会慢下来.

事实上,它是3值而不是2值意味着您不需要在排序实现中非常小心地获得稳定性 - 但这是一个次要的实现细节.这并不像实际让你的价值观具有意义那么重要.(而且,Bool效率不高Ordering.它不是Haskell中的原语.它们都是库中定义的代数数据类型.)

Answer 2

当你对东西进行分类时,你要把它们整理好; 没有确定的"真相"价值.

更重要的是,"真实"意味着什么？第一个参数小于第二个？比...更棒？现在你要覆盖"真实",真正意味着"小于"(或"大于",取决于你选择如何实现这个功能).如果他们是平等的呢？

那么,为什么不切出的中间人,可以这么说,并返回你真正的意思吗？

Answer 3

没有理由不能.如果你看一下ghc实现,它只检查结果是否GT存在.代码的Haskell Report版本使用insertBy,它同样只检查GT或不检查.您可以编写以下内容并使用它而不会出现任何问题:

sortByBool :: (a -> a -> Bool) -> [a] -> [a]
sortByBool lte = sortBy (\x y -> if lte x y then LT else GT)

sort' :: Ord a => [a] -> [a]
sort' = sortByBool (<=)

有些种类可以通过了解元素何时进行优化EQ,但当前使用的实现不需要此信息.

Answer 4

我认为有两个独立的设计决策:
1)创建Ordering类型
2)选择sortBy返回Ordering值

该Ordering类型不仅仅是有用的sortBy- 例如,compare是Ord类型类的"核心" .它的类型是:: Ord a => a -> a -> Ordering.给定两个值,那么,你可以找出他们是否是小于,大于或等于-与任何其他比较函数((<),(<=),(>),(>=))你只能排除那些三种可能性之一.

这是一个简单的例子,其中Ordering(至少在我看来)使函数的意图更清晰一些:

f a b = 
  case compare a b of
    GT -> {- something -}
    LT -> {- something -}
    EQ -> {- something -}

一旦你决定创建这个Ordering类型,那么我认为在那些你正在寻找的信息(如sortBy)中使用它是很自然的,而不是Bool用作一种变通方法.

Answer 5

在我们需要区分案例的情况下,Ordering需要三个值来保存比较EQ.在重复保留中,sort或者merge我们忽略了这种EQ情况,因此具有较少或等于语义的谓词是完全可以接受的.但不是在的情况下,或者是我们期望区分3个比较的结果.unionnubSort

mergeBy lte (x:xs) (y:ys)
    | lte y x   = y : mergeBy lte (x:xs) ys
    | otherwise = x : mergeBy lte xs (y:ys)

union (x:xs) (y:ys) = case compare x y of 
    LT -> x : union  xs (y:ys) 
    EQ -> x : union  xs    ys 
    GT -> y : union (x:xs) ys

用lte谓词编写后者是不自然的.