在f#中模式匹配是如何工作的?

I am completely new to F# (and functional programming in general) but I see pattern matching used everywhere in sample code. I am wondering for example how pattern matching actually works? For example, I imagine it working the same as a for loop in other languages and checking for matches on each item in a collection. This is probably far from correct, how does it actually work behind the scenes?

我对f#(以及一般的函数式编程)完全陌生，但是我看到在示例代码中到处都使用模式匹配。例如，我想知道模式匹配是如何工作的?例如，我假设它与其他语言中的For循环一样工作，并检查集合中的每个项目是否匹配。这可能远不正确，它是如何在幕后工作的?

4 个解决方案

#1

It depends on what kind of pattern matching do you mean - it is quite powerful construct and can be used in all sorts of ways. However, I'll try to explain how pattern matching works on lists. You can write for example these patterns:

这取决于你指的是哪种模式匹配——它是非常强大的结构，可以用在各种各样的地方。但是，我将尝试解释模式匹配如何在列表中工作。例如，你可以这样写:

match l with
| [1; 2; 3] ->  // specific list of 3 elements
| 1::rest ->    // list starting with 1 followed by more elements
| x::xs ->      // non-empty list with element 'x' followed by a list
| [] ->         // empty list (no elements)

The F# list is actually a discriminated union containing two cases - [] representing an empty list or x::xs representing a list with first element x followed by some other elements. In C#, this might be represented like this:

f#列表实际上是一个有区别的联合，包含两种情况——[]表示一个空列表，或x::xs表示一个列表，第一个元素x后面跟着一些其他元素。在c#中，可以这样表示:

// Represents any list
abstract class List<T> { }
// Case '[]' representing an empty list
class EmptyList<T> : List<T> { }
// Case 'x::xs' representing list with element followed by other list
class ConsList<T> : List<T> {
  public T Value { get; set; } 
  public List<T> Rest { get; set; }
}

The patterns above would be compiled to the following (I'm using pseudo-code to make this simpler):

上面的模式将被编译成如下(我使用伪代码使其更简单):

if (l is ConsList) && (l.Value == 1) &&
   (l.Rest is ConsList) && (l.Rest.Value == 2) &&
   (l.Rest.Rest is ConsList) && (l.Rest.Rest.Value == 3) &&
   (l.Rest.Rest.Rest is EmptyList) then
   // specific list of 3 elements
else if (l is ConsList) && (l.Value == 1) then
   var rest = l.Rest;
   // list starting with 1 followed by more elements
else if (l is ConsList) then
   var x = l.Value, xs = l.Rest;
   // non-empty list with element 'x' followed by a list
else if (l is EmptyList) then 
   // empty list (no elements)

As you can see, there is no looping involved. When processing lists in F#, you would use recursion to implement looping, but pattern matching is used on individual elements (ConsList) that together compose the entire list.

如您所见，不涉及循环。在f#中处理列表时，您将使用递归实现循环，但是模式匹配使用在单个元素(con)上，这些元素组合在一起构成整个列表。

Pattern matching on lists is a specific case of discriminated union which is discussed by sepp2k. There are other constructs that may appear in pattern matching, but essentially all of them are compiled using some (complicated) if statement.

列表上的模式匹配是sepp2k讨论的一种特殊的区分结合情况。在模式匹配中可能出现其他构造，但基本上所有的构造都是使用一些(复杂的)if语句编译的。

#2

How does pattern matching actually work? The same as a for loop?

模式匹配是如何工作的?和for循环一样吗?

It is about as far from a for loop as you could imagine: instead of looping, a pattern match is compiled to an efficient automaton. There are two styles of automaton, which I call the "decision tree" and the "French style." Each style offers different advantages: the decision tree inspects the minimum number of values needed to make a decision, but a naive implementation may require exponential code space in the worst case. The French style offers a different time-space tradeoff, with good but not optimal guarantees for both.

它离for循环的距离是可以想象的:模式匹配不是循环，而是编译为高效的自动机。有两种类型的自动机，我称之为“决策树”和“法式风格”。每种样式都有不同的优点:决策树检查决策所需的最小值数，但是在最坏的情况下，幼稚的实现可能需要指数级的代码空间。法国风格提供了一种不同的时间-空间权衡，对两者都有好的但不是最佳的保证。

But the absolutely definitive work on this problem is Luc Maranget's excellent paper "Compiling Pattern Matching to Good Decisions Trees from the 2008 ML Workshop. Luc's paper basically shows how to get the best of both worlds. If you want a treatment that may be slightly more accessible to the amateur, I humbly recommend my own offering When Do Match-Compilation Heuristics Matter?

但是，关于这个问题的绝对确定的工作是Luc Maranget的优秀论文“编译模式匹配到良好决策树，从2008 ML研讨会。吕克的论文基本上说明了如何在这两个世界中取得最好的结果。如果你想要一种对业余爱好者来说可能更容易理解的治疗方法，我谦卑地向你推荐我自己的治疗方法，什么时候配对编译启发式才重要呢?

Writing a pattern-match compiler is easy and fun!

编写模式匹配编译器既简单又有趣!

#3

No, it doesn't loop. If you have a pattern match like this

不,它不循环。如果你有这样的模式匹配

match x with
| Foo a b -> a + b
| Bar c -> c

this compiles down to something like this pseudo code:

这可以归结为这样的伪代码:

if (x is a Foo)
  let a = (first element of x) in
  let b = (second element of x) in
  a+b
else if (x is a Bar)
  let c = (first element of x) in
  c

If Foo and Bar are constructors from an algebraic data type (i.e. a type defined like type FooBar = Foo int int | Bar int) the operations x is a Foo and x is a Bar are simple comparisons. If they are defined by an active pattern, the operations are defined by that pattern.

如果Foo和Bar是代数数据类型的构造函数(即定义为FooBar = Foo int | Bar类型的类型)，那么操作x是Foo, x是Bar是简单的比较。如果它们是由活动模式定义的，那么操作就是由该模式定义的。

#4

If you compile your F# code to an .exe then take a look with Reflector you can see what the C# "equivalent" of the F# code.

如果您将f#代码编译为.exe，那么请查看Reflector，您可以看到f#代码的c#“等效”。

I've used this method to look at F# examples quite a bit.

我已经用这个方法查看了很多f#示例。

#1

match l with
| [1; 2; 3] ->  // specific list of 3 elements
| 1::rest ->    // list starting with 1 followed by more elements
| x::xs ->      // non-empty list with element 'x' followed by a list
| [] ->         // empty list (no elements)

// Represents any list
abstract class List<T> { }
// Case '[]' representing an empty list
class EmptyList<T> : List<T> { }
// Case 'x::xs' representing list with element followed by other list
class ConsList<T> : List<T> {
  public T Value { get; set; } 
  public List<T> Rest { get; set; }
}