20

HaskellsortBy関数は(a -> a -> Ordering)、最初の引数として取ります。そこにどんな理由があるのか​​、誰でも教えてもらえますか? 私のバックグラウンドは完全に、代わりに同様の関数 take を持つ言語にあるため、 /(a -> a -> Bool)を返す関数を作成する必要があるのは少し混乱しました。LTGT

これは、静的に型付けされた/純粋な関数型言語で行う標準的な方法ですか? これは ML 系言語特有のものですか? 私が見ていない基本的な利点、または代わりにブール値を使用することの隠れた欠点はありますか?

要約:

  • AnOrderingは ではなくGT | LT、実際にはGT | EQ | LT(GHCソートの目的でこれをボンネットの下で使用していないようですが、それでも)

  • 3 分値を返すと、2 つの要素を比較した結果をより厳密にモデル化できます。

  • 場合によってOrderingは、a ではなくを使用Boolすると比較が保存されます

  • を使用すると、Ordering安定ソートの実装が容易になります

  • を使用するOrderingと、2 つの要素間の比較が行われていることが読者に明確になります (ブール値は本質的にこの意味を持っていませんが、多くの読者がそれを想定しているように感じます)。

この編集の時点で単一の回答がすべてのポイントに達していないため、カールの回答を暫定的に受け入れ、上記の要約を投稿しています。

4

5 に答える 5

23

Boolean Blindnessが主な理由だと思います。Boolドメイン セマンティクスを持たない型です。のような関数の場合のセマンティクスはsortBy、関数が動作しているドメインからではなく、完全に慣習から来ています。

これにより、比較関数の作成に関連する精神的プロセスに 1 レベルの間接化が追加されます。「返すことができる 3 つの値は、より小さい、等しい、または大きい」という順序付けのセマンティック ビルディング ブロックを単に言う代わりに、「より小さい値を返したいので、ブール値に変換する必要があります」と言います。常に存在する追加の精神的な変換ステップがあります。慣習に精通していても、少し遅くなります。また、規則に精通していない場合は、それが何であるかを確認する必要があるため、かなり遅くなります。

2 値ではなく 3 値であるという事実は、安定性を得るためにソートの実装にそれほど注意を払う必要がないことを意味しますが、それは実装の詳細です。実際に価値観に意味を持たせることほど重要ではありません。(また、Boolよりも効率的ではありませOrderingん。Haskell のプリミティブではありません。どちらもライブラリで定義された代数データ型です。)

于 2012-08-28T04:54:40.260 に答える
20

物事を分類するときは、それらを順番に並べます。決定する「真実」の値はありません。

さらに言えば、「真実」とは何を意味するのでしょうか。最初の引数が 2 番目の引数より小さいことは? より大きい？ここで、「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

2 つの別々の設計上の決定があったと思います:
1)Ordering型を作成する 2)値を返すために
for を選択するsortByOrdering

Ordering型は単なるものではありません。sortByたとえば、型クラスcompareの「目玉」ですOrd。そのタイプは:: Ord a => a -> a -> Orderingです。2 つの値が与えられた場合、それらがより小さいか、より大きいか、または等しいかを調べることができます。他の比較関数 ( (<)、(<=)、(>)、(>=)) を使用すると、これら 3 つの可能性のうちの 1 つしか除外できません。

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

3 つの値Orderingは、大文字と小文字を区別する必要がある場合に比較を保存するためEQに必要です。重複保存sortorでは、大文字と小文字の区別mergeを無視するため、以下のセマンティクスを持つ述語は完全に受け入れられます。ただし、比較の3 つの結果を区別したい場合、または区別したい場合はそうではありません。EQunionnubSort

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 に答える