7

我想知道 Haskell 中的模式匹配是如何工作的。我知道这个线程，但不太明白其中的答案。

  • 答案表明类型由布尔表达式匹配，但这怎么可能呢？
  • 我得到的另一件事是模式匹配比模式匹配更通用，(==)并且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

我只想指出，数据类型和模式匹配（初步近似）只是有用但冗余的语言特性，可以纯粹使用 lambda 演算来实现。如果您了解如何在 lambda 演算中实现它们，您就可以理解为什么它们不需要Eq实现模式匹配。

在 lambda 演算中实现数据类型被称为“教堂编码”（在Alonzo Church之后，他演示了如何做到这一点）。Church-encoded 函数也被称为“Continuation-passing style”。

它被称为“连续传递样式”，因为您提供了一个处理该值的函数，而不是提供值。因此，例如，Int我可以不给用户一个 ，而是给他们一个以下类型的值：

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

上述类型与Int. “同构”只是一种奇特的说法，我们可以将 anyIndirectInt转换为Int：

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

...我们可以将 anyInt转换为IndirectInt：

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

...这样：

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

使用延续传递风格，我们可以将任何数据类型转换为 lambda 演算项。让我们从一个简单的类型开始，例如：

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)，我们可以提供两个单独的函数，一个用于 ，一个用于 ，而不是提供atype的函数，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与 (Exercise: Prove this) 同构Either () ()，所以我们可以将其编码为：

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

并且() -> x与 (Exercise: Prove this) 同构x，因此我们可以进一步将其重写为：

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

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

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

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

由于同构，我们可以保证所有 Church 编码将具有与原始数据类型的可能值一样多的实现。因此，恰好有两个函数存在于其中并非巧合，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

简而言之，当我们以延续传递风格编写类型时，延续就像 case 构造的 case 语句，所以我们所做的就是将每个不同的 case 语句作为参数传递给函数。

这就是您不需要Eq对类型进行模式匹配的原因。在 lambda 演算中，类型决定它“等于”什么，只需定义它从提供给它的参数中选择哪个参数。

因此，如果我是，我通过始终选择我的第一个参数true来证明我是“平等的” 。true如果我是 a ，我通过总是选择我的第二个参数false来证明我是“平等的” 。false简而言之，构造函数“相等”归结为“位置相等”，它总是在 lambda 演算中定义，如果我们可以将一个参数区分为“第一个”，另一个作为“第二个”，这就是我们所需要的“比较”构造函数的能力。

于 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）。

相反，模式匹配只是通过构造函数进行。每个模式都必须以构造函数为首——你不能像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仍然 matchTypeB和TypeCmatches TypeC。但是如果你使用你的保护表达式，TypeB实际上 matchTypeC和TypeCmatches TypeB。TypeA两者之间没有变化。

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

总而言之：模式匹配内置在语言中，通过比较构造函数然后递归匹配其余值来工作。平等通常是根据模式匹配来实现的，它比较整个值而不仅仅是构造函数。

于 2012-06-18T19:59:32.800 回答
4

您缺少的是 Haskell 中的构造函数可以有参数。类型标签“它们自己”可通过相等性进行比较（至少在内部，在幕后），但只有当组成参数也可比较时，完整值才可比较。

所以如果你有这样的类型

data Maybe a = Nothing | Just a

那么即使您可以测试类型标记是“Nothing”还是“Just”（即；模式匹配可能的值），通常您也无法比较完整的可能，除非“a”类型的值是持有的Just也恰好是可比的。

--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 的变体。在 Just 案例中，您将使用什么来测试相等性？

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

在我看来，模式匹配基本上是按位相等。它基于类型，而不是一些抽象的价值概念。

但是请记住，您应该将 sayInt视为

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

所以在某种程度上，每个整数都有不同的类型。

这就是为什么你可以匹配Intsay 2。

Eq更进一步，它允许您将可能不是按位相同的事物设置为相等。

例如，您可能有一个存储已排序元素的二叉树。说以下内容：

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

可能被 视为相等Eq，因为它们包含相同的元素，但您无法在此处使用模式匹配检查相等性。

但是在数字的情况下，按位相等基本上与逻辑相等相同（可能除了正浮点和负浮点0.0），所以这里Eq和模式匹配几乎是等价的。

与 C++ 类比，将Eqasoperator==和模式匹配视为memcmp. 您可以简单地使用 比较许多类型的相等性memcmp，但如果它们可以对“相等”值有不同的表示，则不能比较一些类型。

于 2012-06-19T02:05:27.177 回答