algorithm f# pattern-matching functional-programming

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

发布于 2024-09-03 03:08:24 字数 136 浏览 7 评论 0原文

我对 F#（以及一般的函数式编程）完全陌生，但我看到示例代码中到处都使用了模式匹配。我想知道例如模式匹配实际上是如何工作的？例如，我想象它的工作方式与其他语言中的 for 循环相同，并检查集合中每个项目的匹配情况。这可能远不正确，它在幕后实际上是如何工作的？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

冷血 2024-09-10 03:08:24

模式匹配实际上是如何工作的？与 for 循环相同吗？

它与您想象的 for 循环相差甚远：模式匹配不是循环，而是编译为高效的自动机。自动机有两种风格，我称之为“决策树”和“法国风格”。每种风格都具有不同的优点：决策树检查做出决策所需的最小值数量，但在最坏的情况下，简单的实现可能需要指数代码空间。法式风格提供了不同的时空权衡，对两者都有良好但不是最优的保证。

但关于这个问题绝对权威的工作是 Luc Maranget 的优秀论文“编译2008 年 ML 研讨会上的模式匹配到良好决策树基本上展示了如何获得两全其美的效果，如果您想要一种对业余爱好者来说更容易理解的处理方法，我谦虚地说。推荐我自己的产品匹配编译启发式何时重要？< /em>

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

回复收藏 0 原文

没有伤那来痛 2024-09-10 03:08:24

这取决于您指的是哪种模式匹配 - 它是非常强大的构造，可以以各种方式使用。不过，我将尝试解释模式匹配如何在列表上工作。例如，您可以编写以下模式：

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 语句进行编译的。

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:

// 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.

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.

回复收藏 0 原文

南七夏 2024-09-10 03:08:24

不，它不循环。如果您有这样的模式匹配，

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

则会编译为类似以下伪代码的内容：

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

如果 Foo 和 Bar 是代数数据类型的构造函数（即定义为 type FooBar = Foo int int | Bar int 的类型） >) 操作x is a Foo和x is a Bar是简单的比较。如果它们是由活动模式定义的，则操作由那个图案。

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.

回复收藏 0 原文