7

Haskellのパターンマッチングがどのように機能するのか疑問に思いました。私はこのスレッドを知っていますが、その中の答えを完全に理解することはできませんでした。

  • 答えは、型がブール式と一致すると述べていますが、これはどのように可能ですか？
  • 私が得たもう1つのことは、パターンマッチングは、パターンマッチングよりも一般的で(==)ありEq、パターンマッチングを使用して実装されていることです。

次のコードスニペットで省略しても、その理由matchと動作を教えていただけますか（なぜ失敗するのかは明らかです）。match3deriving (Eq)match2

data MyType = TypeA | TypeB
            deriving (Eq)

match :: MyType -> String
match TypeA = "this is type A"
match TypeB = "this is type B"

match2 :: MyType -> String
match2 a | a == TypeA = "this is type A matched by equality"
         | a == TypeB = "this is type B matched by equality"
         | otherwise = "this is neither type A nor type B"

match3 :: MyType -> String
match3 a = case a of TypeA -> "this is type A matched by case expression"
                     TypeB -> "this is type B matched by case expression"

main :: IO ()
main = do
    (print . match) TypeA
    (print . match) TypeB
    (print . match2) TypeA
    (print . match2) TypeB
    (print . match3) TypeA
    (print . match3) TypeB
4

4 に答える 4

13

データ型とパターンマッチング（最初の概算）は単に有用ですが、ラムダ計算を使用して純粋に実装できる冗長な言語機能であることを指摘したいと思います。Eqラムダ計算でそれらを実装する方法を理解していれば、パターンマッチングを実装する必要がない理由を理解できます。

ラムダ計算でデータ型を実装することは、それらを「チャーチエンコード」することとして知られています（これを行う方法を示したAlonzo Churchにちなんで）。チャーチエンコードされた関数は、「継続渡しスタイル」とも呼ばれます。

値を提供する代わりに、値を処理する関数を提供するため、これは「継続渡しスタイル」と呼ばれます。したがって、たとえば、ユーザーにを与えるInt代わりに、次のタイプの値をユーザーに与えることができます。

type IndirectInt = forall x . (Int -> x) -> x

上記のタイプは、と「同型」Intです。IndirectInt「同型」は、任意のものをInt：に変換できることを示すための空想的な言い方です。

fw :: IndirectInt -> Int
fw indirect = indirect id

Int...そして私たちは任意のものをIndirectInt：に変換することができます

bw :: Int -> IndirectInt
bw int = \f -> f int

... そのような：

fw . bw = id -- Exercise: Prove this
bw . fw = id -- Exercise: Prove this

継続渡しスタイルを使用すると、任意のデータ型をラムダ計算項に変換できます。次のような単純なタイプから始めましょう。

data Either a b = Left a | Right b

継続渡しスタイルでは、これは次のようになります。

type IndirectEither a b = forall x . (Either a b -> x) -> x

しかし、Alonzo Churchは賢く、複数のコンストラクターを持つタイプの場合、コンストラクターごとに個別の関数を提供できることに気づきました。したがって、上記のタイプの場合、タイプの関数を提供する代わりに、代わりに(Either a b -> x)2つの別々の関数を提供できます。1つは、、もう1aつは、bです。

type IndirectEither a b = forall x . (a -> x) -> (b -> x) -> x
-- Exercise: Prove that this definition is isomorphic to the previous one

Boolコンストラクターに引数がないようなタイプはどうですか？ええと、 （演習：これを証明する）Boolと同型Either () ()なので、次のようにエンコードできます。

type IndirectBool = forall x . (() -> x) -> (() -> x) -> x

そして、（演習：これを証明する）() -> xと同型であるxため、さらに次のように書き直すことができます。

type IndirectBool = forall x . x -> x -> x

上記のタイプを持つことができる関数は2つだけです。

true :: a -> a -> a
true a _ = a

false :: a -> a -> a
false _ a = a

同型であるため、すべてのチャーチエンコーディングに、元のデータ型の可能な値と同じ数の実装が含まれることを保証できます。IndirectBoolしたがって、のコンストラクタが2つあるのと同じように、に生息する関数が2つあるのは偶然ではありませんBool。

しかし、どのようにパターンマッチングを行うのIndirectBoolでしょうか。たとえば、通常の場合、次のBoolように書くことができます。

expression1 :: a
expression2 :: a

case someBool of
    True  -> expression1
    False -> expression2

まあ、私たちIndirectBoolにはすでにそれ自体を分解するためのツールが付属しています。私たちはただ書くでしょう：

myIndirectBool expression1 expression2

の場合は最初の式を選択し、そうである場合myIndirectBoolは2番目の式を選択することに注意してください。これは、その値が何らかの形でパターン一致している場合と同じです。truefalse

で同じことをしてみましょうIndirectEither。通常Eitherのを使用して、次のように記述します。

f :: a -> c
g :: b -> c

case someEither of
    Left  a -> f a
    Right b -> g b

を使用して、次のIndirectEitherように記述します。

someIndirectEither f g

要するに、継続渡しスタイルで型を書く場合、継続はcase構造のcaseステートメントのようなものなので、私たちがしているのは、それぞれの異なるcaseステートメントを引数として関数に渡すことだけです。

Eqこれが、型のパターンマッチングの感覚を必要としない理由です。ラムダ計算では、型は、提供された引数から選択する引数を定義するだけで、「等しい」ものを決定します。

したがって、私がである場合は、常に最初の引数を選択することで、true私が「等しい」ことを証明します。true私がである場合、常に2番目の引数を選択することにより、false私が「等しい」ことを証明します。false要するに、コンストラクターの「等式」は、ラムダ計算で常に定義される「位置の等式」に要約されます。あるパラメーターを「最初の」として、別のパラメーターを「2番目の」として区別できる場合、必要なのはそれだけです。コンストラクターを「比較」する機能。

于 2012-06-19T01:10:39.500 に答える
12

まず第一に、matchそしてmatch3実際にはまったく同じです（異なる文字列を無視します）：関数のパターンマッチングはcaseステートメントに脱糖されます。

次に、パターンマッチングは、任意の値ではなくコンストラクターで機能します。パターンマッチングは言語に組み込まれており、ブール式に依存しません。コンストラクターに直接作用するだけです。これは、いくつかの一致する用語を含むより複雑な一致で最も明白です。

f :: MyType -> Int
f (A a) = a + 1
f (B a b) = a + b

これらのパターンをブール式にどのように書き直しますか？あなたはできません（他に何も知らずにMyType）。

代わりに、パターンマッチングはコンストラクターによって行われます。各パターンはコンストラクターが先頭に立つ必要があります。Haskellのようにパターンを書くことはできませんf (a b c)。次に、関数が値を取得すると、値のコンストラクターを調べて、適切なケースにすぐにジャンプできます。これは、（のようなA a）より複雑なパターンに対して機能する方法であり、使用した単純なパターンに対しても機能する方法です。

Eq パターンマッチングは適切なコンストラクターに移動するだけで機能するため、にまったく依存しません。パターンマッチングのインスタンスが必要ないだけでなく、Eqインスタンスがあれば、パターンマッチングの動作も変わりません。たとえば、次のことを試してください。

data MyType = TypeA | TypeB | TypeC

instance Eq MyType where 
  TypeA == TypeA = True
  TypeB == TypeC = True
  TypeC == TypeB = True
  _ == _         = False

match :: MyType → String
match TypeA = "this is type A"
match TypeB = "this is type B"
match TypeC = "this is type C"

match2 :: MyType → String
match2 a | a == TypeA = "this is type A matched by equality"
         | a == TypeC = "this is type B matched by equality"
         | a == TypeB = "this is type C matched by equality"
         | otherwise = "this is neither type A nor type B"

これで、それ自体TypeBと等しいが等しくないような平等を定義しました。TypeC（実際には、平等が合理的に動作し、反射特性に従うことを確認する必要がありますが、これはおもちゃの例です。）ここで、パターンマッチングを使用する場合TypeBでも、一致TypeBし、TypeC一致しTypeCます。ただし、ガード式を使用する場合は、TypeB実際には一致TypeCし、TypeC一致しTypeBます。TypeA2つの間で変更されていません。

さらに、パターンマッチングを使用しEqてインスタンスがどのように定義されたかに注意してください。句を使用すると、コンパイル時に生成されたコードと同様の方法で定義されます。したがって、パターンマッチングは、標準ライブラリの一部である言語の一部であるよりも基本的です。derivingEqEq

要約すると、パターンマッチングは言語に組み込まれており、コンストラクターを比較してから、残りの値を再帰的にマッチングすることで機能します。等式は通常、パターンマッチングの観点から実装され、コンストラクターだけでなく値全体を比較します。

于 2012-06-18T19:59:32.800 に答える
4

あなたが見逃しているのは、Haskellのコンストラクターが引数を持つことができるということです。タイプタグ「それ自体」は、同等性によって比較可能です（少なくとも内部的には、舞台裏で）が、完全な値は、構成引数も比較可能である場合にのみ比較可能です。

だからあなたがのようなタイプを持っているなら

data Maybe a = Nothing | Just a

次に、タイプタグが「Nothing」または「Just」であるかどうかをテストできますが（つまり、多分値のパターンマッチ）、タイプ「a」の値がそうでない限り、多分完全に比較することはできません。ジャストによって開催されたものもたまたま比較可能です。

--note that your first and third examples are
--just syntactic sugar for each other...
matchMaybe mb = case mb of
    Nothing -> "Got a Nothing"
    Just _  -> "Got a Just but ignored its value"

Maybesのmatch2のバリエーションを作成できない理由も明らかになりました。ジャストケースで平等をテストするために何を使用しますか？

matchMaybe_2 mb | mb == Nothing = "Got a Nothing"
                | mb == Just {- ??? -} = "This case is impossible to write like this"
于 2012-06-18T19:57:29.533 に答える
1

私の考えでは、パターンマッチングは基本的にビット単位の等式です。これは型に基づいており、抽象的な値の概念ではありません。

ただし、次のように考える必要がありますInt。

data Int = ... | -2 :: Int | -1 :: Int | 0 :: Int | 1 :: Int | 2 :: Int | ...

したがって、ある意味で、各整数は異なるタイプを持っています。

そういうわけであなたはInt言うと一致することができます2。

Eqさらに進んで、ビット単位で同じものではない可能性があるものを等しく設定することができます。

たとえば、ソートされた要素を格納するバイナリツリーがあるとします。次のように言います。

  A       A
 / \     / \
B   C   B   D
     \   \
      D   C

同じ要素が含まれているため、によって等しいと見なされる場合Eqがありますが、パターンマッチングを使用してここで等しいかどうかを確認することはできません。

ただし、数値の場合、ビット単位の等式は基本的に論理等式と同じであるため（正と負の浮動小数点を除く0.0）、ここEqとパターンマッチングはほぼ同等です。

C ++に例えるとEq、operator==パターンマッチングはとして考えてmemcmpください。を使用するだけで、多くのタイプの同等性を比較できmemcmpますが、「等しい」値の表現が異なる場合は、比較できないものもあります。

于 2012-06-19T02:05:27.177 に答える