16

私はHaskellが初めてです。関数がカリー化されて、1 つのパラメーターを取る関数になることを理解しています。私が理解していないのは、この場合に複数の値に対するパターン マッチングをどのように達成できるかということです。例えば：

次の完全に任意の関数定義があるとします。

myFunc :: Int -> Int -> Int
myFunc 0 0 = 0
myFunc 1 1 = 1
myFunc x y = x `someoperation` y

myFunc 0基本的に返される部分的に適用された関数は次のとおりです。

partiallyAppliedMyFunc :: Int -> Int
partiallyAppliedMyFunc 0 = 0
partiallyAppliedMyFunc y = 0 `someoperation` y

したがって、おそらく一致しない無関係なパターンを削除しますか? または....ここで何が起こっているのですか？

4

1 に答える 1

27

実際、この質問は表面的に見えるよりも微妙であり、実際に適切に答えるには、コンパイラの内部について少し学ぶ必要があります。その理由は、入れ子になったパターンや複数の用語にまたがるパターンを持つことができることを当然のことと考えているからです。実際には、コンパイラの目的で唯一できることは、単一の最上位コンストラクターで分岐することだけです。価値。したがって、コンパイラの最初の段階では、ネストされたパターン (および複数の値にまたがるパターン) をより単純なパターンに変換します。たとえば、単純なアルゴリズムは、関数を次のように変換する可能性があります。

myFunc = \x y -> case x of
    0 -> case y of
        0 -> 0
        _ -> x `someoperation` y
    1 -> case y of
        1 -> 1
        _ -> x `someoperation` y
    _ -> x `someoperation` y

ここには最適ではないものがたくさんあることがすでにわかります。someoperation項は何度も繰り返されており、関数は a を実行し始める前に両方の引数を想定していcaseます。これを改善する方法については、有限オートマトン理論に触発された用語パターン マッチ コンパイラを参照してください。

とにかく、この形式では、実際にはカリー化ステップがどのように行われるかがもう少し明確になるはずです。xこの式でfor を直接代入して、何をmyFunc 0行うかを確認できます。

myFunc 0 = \y -> case 0 of
    0 -> case y of
        0 -> 0
        _ -> 0 `someoperation` y
    1 -> case y of
        1 -> 1
        _ -> 0 `someoperation` y
    _ -> 0 `someoperation` y

これはまだラムダであるため、それ以上の削減は行われません。十分にスマートなコンパイラがもう少し多くのことを行うことを望むかもしれませんが、GHC は明示的にそれ以上のことを行いません。引数を 1 つだけ指定した後でさらに計算を実行したい場合は、定義を変更する必要があります。(ここには時間/空間のトレードオフがあり、正しく選択することは確実に行うには難しすぎます。したがって、GHC はプログラマーの手にこの選択を任せます。) たとえば、明示的に次のように書くことができます。

myFunc 0 = \y -> case y of
    0 -> 0
    _ -> 0 `someoperation` y
myFunc 1 = \y -> case y of
    1 -> 1
    _ -> 1 `someoperation` y
myFunc x = \y -> x `someoperation` y

そしてmyFunc 0、はるかに小さな式に縮小されます。

于 2012-09-30T06:06:30.463 に答える