20

HaskellsortBy函数将(a -> a -> Ordering)其作为第一个参数。谁能教育我那里的推理是什么？我的背景完全是具有类似功能的语言(a -> a -> Bool)，所以不得不编写一个返回LT/的语言GT有点令人困惑。

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

总结：

  • 不是，它实际上是Ordering（显然没有在引擎盖下使用它来进行排序，但仍然）GT | LTGT | EQ | LTGHC

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

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

  • 使用 anOrdering可以更轻松地实现稳定的排序

  • 使用 anOrdering可以让读者清楚地知道两个元素之间的比较正在进行（布尔值本身并不具有这种含义，尽管我觉得许多读者会假设它）

我暂时接受 Carl 的回答，并发布上述摘要，因为在本次编辑中没有一个单一的答案能达到所有要点。

4

5 回答 5

23

我认为布尔盲是主要原因。Bool是没有域语义的类型。在类似函数的情况下，它的语义sortBy完全来自约定，而不是来自函数正在运行的域。

这为编写比较函数所涉及的心理过程增加了一层间接性。而不是仅仅说“我可以返回的三个值小于、等于或大于”，排序的语义构建块，你说“我想返回小于，所以我必须将它转换为布尔值”。总是存在一个额外的心理转换步骤。即使您精通约定，它仍然会减慢您的速度。如果你不熟悉约定，你会因为不得不检查它是什么而减慢了很多速度。

它是 3 值而不是 2 值的事实意味着您在排序实现中也不需要非常小心以获得稳定性 - 但这是一个次要的实现细节。它并不像让你的价值观真正有意义那么重要。（此外，它并不Bool比 . 它更有效Ordering。它不是 Haskell 中的原语。它们都是在库中定义的代数数据类型。）

于 2012-08-28T04:54:40.260 回答
20

当你整理东西时，你把它们整理好；没有要确定的“真相”值。

更重要的是，“真实”是什么意思？第一个论点小于第二个？比...更棒？现在您将“true”覆盖为真正的“小于”（或“大于”，具体取决于您选择实现该功能的方式）。如果他们是平等的呢？

那么为什么不删掉中间人，可以这么说，并返回你的真正意思呢？

于 2012-08-28T04:21:56.653 回答
11

没有理由不能。如果您查看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，但当前使用的实现不需要此信息。

于 2012-08-28T04:49:44.777 回答
6

我认为有两个独立的设计决策：
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作为一种解决方法。

于 2012-08-28T05:01:44.200 回答
6

在我们确实需要区分大小写的情况下，需要三个值Ordering来保存比较EQ。在重复保留sortormerge中，我们忽略了这种EQ情况，因此具有小于等于或等于语义的谓词是完全可以接受的。但不是在我们确实想要区分比较的三种结果的情况下或在哪里。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谓词编写后一个是不自然的。

于 2012-08-28T06:15:09.233 回答