pattern-matching - 使用什么数据结构来实现模式匹配？

Question

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

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

它是某种树结构吗？

标签： pattern-matchingelixir

Answer 1

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

Luc Maranget论文“Compiling Pattern Matching to Good Decision Trees”对如何将模式匹配实现到决策树中进行了很好的深入描述。

另一个非常好的资源是Simon Peyton Jones 的《函数式编程语言的实现》一书。