模式匹配如何在F#幕后工作？

Question

我对F#(以及一般的函数式编程)是全新的,但我看到样本代码中到处都使用了模式匹配.我想知道模式匹配实际上是如何工作的？例如,我想它在其他语言中与for循环一样工作,并检查集合中每个项目的匹配.这可能远非正确,它在幕后实际上是如何工作的？

Answer 1

模式匹配实际上如何工作？同为一个for循环？

它for与您想象的循环差不多:不是循环,而是将模式匹配编译为高效的自动机.自动机有两种风格,我称之为"决策树"和"法式风格".每种样式都有不同的优点:决策树检查做出决策所需的最小值,但在最坏的情况下,天真的实现可能需要指数代码空间.法国风格提供了不同的时空权衡,两者都有良好但不是最佳的保证.

但关于这个问题的绝对明确的工作是Luc Maranget的优秀论文"从2008 ML研讨会编制模式匹配良好决策树 .Luc的论文基本上展示了如何充分利用两个世界.如果你想要一个可能稍微多一点的治疗业余人士可以访问,我谦卑地推荐我自己的产品什么时候匹配编译启发式问题？

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

Answer 2

这取决于你的意思是什么样的模式匹配 - 它是非常强大的构造,可以以各种方式使用.但是,我将尝试解释模式匹配如何在列表上工作.您可以编写例如以下模式:

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)

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; }
}

上面的模式将被编译为以下(我使用伪代码使这更简单):

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)

如您所见,没有涉及循环.在F#中处理列表时,您将使用递归来实现循环,但是模式匹配用于ConsList组合整个列表的各个元素().

列表上的模式匹配是sepp2k讨论的区分联合的特定情况.在模式匹配中可能会出现其他构造,但基本上所有构造都是使用某些(复杂)语句编译的.if