haskell - これらの XOR のどれが Haskell で優れていると考えられていますか?

Question

Haskell で最も標準的な方法を教えてください。

最初のものは、(ほとんどの場合) 2 つの引数が必要であることを明確に示しています。

2 番目は 2 番目の句に関数呼び出し ( id) を含むため、最初の実装では単純に 2 番目の引数を返すことができるため、効率が低下するはずです。

したがって、私は最初の方が優れていると考える傾向があり、選択する必要があります。読みやすく、それが何をするかを理解しやすく[1]、関数呼び出しは保存されます。

しかし、私はHaskellの初心者です.おそらくコンパイラはこの余分な呼び出しを最適化します.

xor :: Bool -> Bool -> Bool

xor True x = not x
xor False x = x

xor True = not
xor False = id

Falseまた、両方をワイルドカードに置き換えることができるかどうかを知りたいです。

では、Haskell のグッドプラクティスは何ですか。多分別の実装？

[1] よく知られている機能であることは省略します。重要な機能であると想像してみましょう。

ありがとう

score 14 · Accepted Answer

読みやすくするために、パターンマッチングを避け、定義する関数について興味深いことを表現する 1 つの方程式で関数を定義するようにします。常に可能というわけではありませんが、この例では多くのオプションがあります。

xor = (/=)
xor a b = a /= b
xor a b = not (a == b)
xor a b = (a && not b) || (not a && b)
xor a b = (a || b) && not (a && b)
xor a b = odd (fromEnum a + fromEnum b)

score 12 · Accepted Answer

もちろん、コンパイラとコンパイラに渡されるオプションに依存します。

この特定の例では、最適化を行わずにコンパイルすると、GHC はユーザーが書いたとおりのコードを生成するため、2 番目のバージョンにはidresp への呼び出しが含まれます。にnot。これは、次の呼び出しのみを含む最初のバージョンよりもわずかに効率が低下しますnot。

Xors.xor1 :: GHC.Types.Bool -> GHC.Types.Bool -> GHC.Types.Bool
[GblId, Arity=2]
Xors.xor1 =
  \ (ds_dkm :: GHC.Types.Bool) (x_aeI :: GHC.Types.Bool) ->
    case ds_dkm of _ {
      GHC.Types.False -> x_aeI;
      GHC.Types.True -> GHC.Classes.not x_aeI
    }

Xors.xor2 :: GHC.Types.Bool -> GHC.Types.Bool -> GHC.Types.Bool
[GblId, Arity=1]
Xors.xor2 =
  \ (ds_dki :: GHC.Types.Bool) ->
    case ds_dki of _ {
      GHC.Types.False -> GHC.Base.id @ GHC.Types.Bool;
      GHC.Types.True -> GHC.Classes.not
    }

(呼び出しはまだ生成されたアセンブリにありますが、コアの方が読みやすいので、それだけを投稿します)。

しかし、最適化を行うと、両方の関数が同じコアにコンパイルされます (したがって、同じマシンコードになります)。

Xors.xor2 =
  \ (ds_dkf :: GHC.Types.Bool) (eta_B1 :: GHC.Types.Bool) ->
    case ds_dkf of _ {
      GHC.Types.False -> eta_B1;
      GHC.Types.True ->
        case eta_B1 of _ {
          GHC.Types.False -> GHC.Types.True;
          GHC.Types.True -> GHC.Types.False
        }
    }

idGHC は 2 番目のバージョンを eta 拡張し、 andの呼び出しをインライン化したnotので、純粋なパターンマッチングが得られます。

2 番目の式で使用するFalseかワイルドカードを使用するかは、最適化の有無にかかわらず、どちらのバージョンでも違いはありません。

おそらく、コンパイラはこの余分な呼び出しを最適化します。

最適化を要求すると、このような単純なケースでは、GHC は余分な呼び出しを排除します。

それが重要な関数であると想像してみましょう。

ここに考えられる問題があります。コードが十分に自明でない場合、コンパイラは、すべての引数が提供されていない関数を定義することによって導入されたすべての呼び出しを排除できない場合があります。ただし、GHCはそれを実行して呼び出しをインライン化するのがかなり得意なので、コードをコンパイルするときに知っている単純な関数の呼び出しを排除してGHCが失敗するようにするには、かなりの量の非自明性が必要です(もちろん、関数への呼び出しをインライン化することはできません)問題のモジュールをコンパイルするときの実装がわからない)。

重要なコードの場合は、コンパイラが生成するコードを常に確認してください。GHC の場合、関連するフラグは-ddump-simpl、最適化後にコアを生成し-ddump-asm、生成されたアセンブリを取得することです。

score 4 · Accepted Answer

だから私は最初の方が良いと思う傾向があり、選ぶべきです：読みやすく、それが何をするかを理解するのが簡単です

読みやすさについては同意します。しかし、2 番目のものは非常に慣用的な Haskell であり、経験豊富なプログラマーにとってはむしろ読みやすいものです。その些細な eta リダクションを実行しないことは非常に疑わしく、実際には意図から逸れる可能性があります。したがって、最適化されたバージョンについては、明示的な形式で完全に書き出すことをお勧めします。

True  `xor` False = True
False `xor` True  = True
_     `xor` _     = False

ただし、そのような代替案が最も慣用的なものよりもかなり読みにくい場合は、それを置き換えるのではなく、コンパイラが理想的なバージョンに最適化できるようにヒントを追加することを検討する必要があります。Daniel Fischer が示したように、GHC はそれ自体が非常に賢く、多くの場合、助けがなくても正しく処理されます。そうでない場合は、いくつかのINLINEおよび/またはRULESプラグマを追加すると役立つ場合があります。最適なパフォーマンスを得るためにこれを行う方法を理解するのは簡単ではありませんが、高速な Haskell98 コードを書く場合も同じことが言えます。

haskell - これらの XOR のどれが Haskell で優れていると考えられていますか?

3 に答える 3

Related

Reference