CODEWITHSUNDEEP
pattern-matchingelixir
satoru
satoru

Reputation: 33225

What data structure is used to implement pattern match?

In the book "Programming Elixir", the author states that "Even if you have thousands of clauses, pattern matching used in this way is fast. Matching a map or struct is O(log n).".

I wonder what data structure is used to implement pattern match in Elixir such that the time complexity if O(log n).

Is it some kind of tree structure?

Upvotes: 2

Views: 245

Answers (2)

Adam Millerchip
Adam Millerchip

Reputation: 23091

Elixir delegates to Erlang's pattern matching.

Looking through Elixir's source code, written in Erlang, here is the code that seems to be handling matching:

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

This is Erlang code, so here Elixir is delegating to 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 is useful:

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.

Upvotes: 1

noxdafox
noxdafox

Reputation: 15040

The implementation of pattern matching differs across functional languages but in most of the cases it boils down to decision trees.

Luc Maranget paper "Compiling Pattern Matching to Good Decision Trees" gives a pretty good in depth description of how pattern matching can be implemented into decision trees.

Another very good resource in merit is the book "The Implementation of Functional Programming Languages" by Simon Peyton Jones.

Upvotes: 2

Related Questions