How does the Erlang compiler implement pattern matching?

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.

Scala – case match partial string

Use regexes 😉 val Pattern = “(chat.*)”.r serv match { case Pattern(chat) => “It’s a chat” case _ => “Something else” } And with regexes you can even easily split parameter and base string: val Pattern = “(chat)(.*)”.r serv match { case Pattern(chat,param) => “It’s a %s with a %s”.format(chat,param) case _ => “Something else” … Read more

Haskell GHC: what is the time complexity of a pattern match with N constructors?

A jump table is used, making the pattern-match a constant time operation. Unfortunately I’m unable to find an up-to-date citation for this, although this page mentions the implementation of Cmm-level switch statements as jump tables, and this old tagging design document uses a case on a Bool as an example, producing a jump table.

Pattern Matching – Prolog vs. Haskell

Prolog pattern matching is based on unification, specifically the Martelli-Montanari Algorithm (minus the occurs check, by default). This algorithm matches values of the same position, binding variables on one side to a value at corresponding position on the other side. This kind of pattern matching could work both ways, therefore in Prolog you could use … Read more