Haskell:为什么模式匹配不适用于类型而不是相等的实例？

Question

我想知道Haskell中的模式匹配是如何工作的,我知道这个帖子,但是不太明白其中的答案.

如果没有我们在数据类型上定义Eq,Haskell如何进行模式匹配？

• 答案说明类型与布尔表达式匹配,但这是如何实现的.
• 我得到的另一件事是模式匹配是不是更宽泛(==),并Eq通过使用模式匹配的实现.

所以即使我在下面的代码片段中省略,你能告诉我为什么match并且match3正在工作deriving (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

Answer 1

我只是想指出数据类型和模式匹配(对于第一个近似)仅仅是有用的但是冗余语言特征,可以纯粹使用lambda演算来实现.如果您了解如何在lambda演算中实现它们,您就可以理解为什么它们不需要Eq实现模式匹配.

在lambda演算中实现数据类型被称为"教会编码"它们(在Alonzo Church之后,他演示了如何做到这一点).教会编码的功能也被称为"延续传递风格".

它被称为"延续传递样式",因为您不是提供值,而是提供将处理该值的函数.因此,例如,Int我可以改为给他们一个以下类型的值,而不是给用户一个:

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

以上类型是"同构"的Int."Isomorphic"只是一种说法,我们可以将任何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

使用延续传递样式,我们可以将任何数据类型转换为lambda-calculus术语.让我们从一个简单的类型开始:

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),我们可以改为提供两个单独的函数,一个用于,一个用于a,而且提供类型的函数,而不是提供类型的函数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

只有两个函数可以具有上述类型:

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

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

由于同构,我们可以保证所有的教会编码将具有与原始数据类型的可能值一样多的实现,因此,恰好有两个函数可以IndirectBool存在,就像正好有两个构造函数一样,这并非巧合Bool.

但是我们如何在我们的模式匹配IndirectBool？例如,对于普通人Bool,我们可以写:

expression1 :: a
expression2 :: a

case someBool of
    True  -> expression1
    False -> expression2

好吧,我们IndirectBool已经提供了解构自己的工具.我们只想写:

myIndirectBool expression1 expression2

请注意,如果myIndirectBool是true,它将选择第一个表达式,如果是false,它将选择第二个表达式,就好像我们在其值上以某种方式模式匹配一​​样.

让我们尝试用一个相同的东西IndirectEither.使用普通的Either,我们写道:

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

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

有了IndirectEither,我们只写:

someIndirectEither f g

简而言之,当我们以连续传递样式编写类型时,continuation就像case构造的case语句一样,所以我们所做的就是将每个不同的case语句作为参数传递给函数.

这就是你不需要Eq对类型进行模式匹配的任何意义的原因.在lambda演算中,类型通过定义从提供给它的那个参数中选择哪个参数来决定它是什么"相等".所以,如果我是一个true,我true总是选择我的第一个论点来证明我"平等" .如果我是一个false,我false总是选择我的第二个论点来证明我"平等" .简而言之,构造函数"相等"归结为"位置相等",它总是在lambda演算中定义,如果我们可以将一个参数区分为"第一个"而另一个参数区分为"第二个",那就是我们需要的全部内容"比较"构造函数的能力.

Answer 2

首先,match并且match3实际上完全相同(忽略不同的字符串):函数中的模式匹配被置于case语句中.

接下来,模式匹配适用于构造函数而不是任意值.模式匹配内置于语言中,不依赖于布尔表达式 - 它只是直接作用于构造函数.对于包含一些匹配术语的更复杂的匹配,这一点最为明显:

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

你会如何将这些模式重写为布尔表达式？你不能(不知道其他任何事情MyType).

相反,模式匹配只是由构造函数进行.每个模式必须由构造函数引导 - 你不能像f (a b c)Haskell 那样编写模式.然后,当函数获取值时,它可以查看值的构造函数并立即跳转到相应的情况.这是它必须为更复杂的模式(如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.TypeA两者之间没有变化.

此外,请注意如何使用模式匹配Eq定义实例.当您使用子句时,它将以与编译时生成的代码类似的方式定义.所以模式匹配比基础更为基础- 它是语言的一部分,它只是标准库的一部分.derivingEqEq

总结:模式匹配内置于语言中,通过比较构造函数然后递归匹配其余值来工作.平等通常在模式匹配方面实现,并比较整个值而不仅仅是构造函数.