[contificate]

It is worth noting that lots of applications of unification do not reify explicit substitutions in their implementations. You often see introductory type inference articles (usually focused on Hindley-Milner) use algorithm W, which uses a unification procedure that returns substitutions (which must then be composed with other substitutions). All of this is less efficient and arguably more error-prone and more complicated than the destructive unification implied by algorithm J (using the union-find data structure, often implemented invasively into the type representation to imply a union-find forest).

To this end, good coverage of decent (destructive) unification algorithms can be found in any simple resource on type inference (https://okmij.org/ftp/ML/generalization/sound_eager.ml) or the Warren Abstract Machine (https://github.com/a-yiorgos/wambook/blob/master/wambook.pdf).

Of course, there are times where you would want to reify substitutions as a data structure to compose and apply, but most of the time you just want to immediately apply them in a pervasive way.

Despite what another comment says, unification is a valid - and rather convenient - way to implement pattern matching (as in the style of ML) in an interpreter: much like how you rewrite type variables with types you are unifying them with, you can rewrite the pattern variables to refer to the parts of the (evaluated) value you are matching against (which you then use to extend the environment with when evaluating the right hand side).

[ReleaseCandidat]

> Despite what another comment says, unification is a valid - and rather convenient - way to implement pattern matching

The article shows that it is a valid and rather convenient way. That's why it is important to tell people that it is not necessary to use it for the "usual" pattern matching. You do (again: for the "usual" pattern matching without "variables", as in free variables, on the right side) _not_ want to use unification but "compile" the pattern matching.

[contificate]

If we are talking about the context of a compiler, I agree: you should compile pattern matching to decision trees (DAGs), by way of something like Pettersson's algorithm. In my comment, I specified "in an interpreter", as I think it's the natural way to implement an SML-like match construct in that context.

EDIT: Perhaps I am missing Elixir-specific context and I apologise if this is the case. It was the unification that made me click this post.