O'Reilly logo

The Functional Approach to Programming by K. Callaway, Michel Mauny, Guy Cousineau

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 5

Formal Terms, Pattern Matching, Unification

 

 

 

In this chapter, we cover a general structure for terms with variables. We will present algorithms for pattern matching and unification—useful in many contexts where we handle expressions formally—such as type synthesis, evaluation, editing, formal computation, or even automatic proof. The chapter closes with an application of the unification algorithm to type synthesis.

5.1   Trees

The basic ideas we present in this section introduce the way we handle terms with variables in the next section.

We are interested in trees where the nodes have variable arity; that is, a node can have zero, one, or more children. The set of children of a node will be represented by a list. A leaf will simply ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required