什么数据结构用于实现模式匹配？

Question

在“Programming Elixir”一书中，作者指出“即使您有数千个子句，以这种方式使用的模式匹配也很快。匹配映射或结构是 O(log n)。”。

我想知道在Elixir中使用什么数据结构来实现模式匹配使得时间复杂度为O(log n)。

是不是某种树结构？

Answer 1

模式匹配的实现因函数式语言而异，但在大多数情况下，它归结为决策树。

Luc Maranget paper“将模式匹配编译为良好的决策树”对如何将模式匹配实施到决策树中进行了非常深入的描述。

另一个非常好的资源是 Simon Peyton Jones 的 book“函数式编程语言的实现”。

Answer 2

Elixir 委托给 Erlang 的模式匹配。

查看 Elixir 的源代码，用 Erlang 编写，这里是似乎处理匹配的代码：

elixir_clauses.erl:

match(Fun, Expr, #{current_vars := Current, unused_vars := {_, Counter} = Unused} = AfterE, BeforeE) ->
  #{
    context := Context,
    prematch_vars := Prematch,
    current_vars := {Read, _}
  } = BeforeE,

  CallE = BeforeE#{
    context := match,
    prematch_vars := {Read, Counter},
    current_vars := Current,
    unused_vars := Unused
  },

  {EExpr, #{current_vars := NewCurrent, unused_vars := NewUnused}} = Fun(Expr, CallE),

  EndE = AfterE#{
    context := Context,
    prematch_vars := Prematch,
    current_vars := NewCurrent,
    unused_vars := NewUnused
  },

  {EExpr, EndE}.

这是 Erlang 代码，所以这里 Elixir 委托给 Erlang's = operator. As this is the case, Robert Virding (the author of Erlang's pattern matching code)'s answer to this related Erlang question 很有用：

A very good description of compiling pattern matching is given in "The implementation of functional programming languages" by Simon Peyton Jones. It is a bit old but a very good book. It also contains, amongst other things, a description of compiling list comprehensions.

The Erlang compiler uses both of these algorithms from the book.

什么数据结构用于实现模式匹配？

What data structure is used to implement pattern match?

elixir

pattern-matching