Pattern matching

Not to be confused with Regular Expressions

While programming, it is often useful to match expressions that have a particular form, like sequences or tree structures, rather than laboriously parse them out with conditionals. The purpose of pattern matching is to match expressions with patterns and bind variables to successful matches. For example, if we have a list processing function, rather than explicitly test for the existence of a head and tail, then explicitly access the head and tail, we can simply ask if the input list has the pattern of a list with a head and tail, and if so, immediately use the bound values for computation. Pattern matching has not yet been widely adopted, but is especially useful in modern functional languages like OCaml, Haskell, F#, and Mathematica, among others.

The simplest patterns could be just matching a particular constant or bind just any expression to the variable.

Here is a recursive haskell construction of the fibonacci function:

1 2 3

fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n- 2)

Please note that in haskell, = stands for definition, not assignment.

The wildcard matches just any expression. The good thing about it is that it does not bind to any expression.

In haskell, the wildcard is written as _

Here is a function that would evaluate to 1 at 2 and 0 everywhere else

1 2	fancyF 2 = 1 fancyF _ = 0

Another lesson to learn here is that haskell matches tries to match the pattern one by one from the top. So, when fancyF 2 is called it wont match the wildcard.

Constructors are functors that create data structures from simpler data structures. Examples of constructors include :.

Lists

Every list written in the form [a1, a2, a3... aN] is just syntactic sugar for a1:a2:a3:...:aN:[] where [] is the empty list.

Here is how I would pick up all but the last two elements of the lists that begin with 0.

1 2 3 4 5

lists = [[0,0,1],[1,2,3],[0,1,2,3],[1,2,3,4,5]] y = [xs | 0:xs <- lists] --y binds to [[0,1],[1,2,3]]

The really cool uses of pattern matching of this type is in creating recursive function definitions.

Check out how map is defined:

1 2	map _ [] = [] map f (x:xs) = f x : map f xs

The basic idea is to apply the function on the first element and attach it to the map of the rest of the list. Of course, you have to tell that the map of the empty list is just the empty list, whatever be the function.

Tuples

Pattern matching inside tuples sure would work.

The following function calculates the distance between two points on a plane.

1	distance (x1,y1) (x2,y2) = sqrt((x1-x2)^2 + (y1-y2)^2)

Other Data Types

Haskell supports algebraic data types. Since they are constructed through functors, pattern matching would work in a similar way.

Here is a simple date datatype.

1 2 3

data Date = Date Int Int Int -- Year, Month, Day showDate :: Date -> String showDate (Date y m d) = show y ++ "-" ++ show m ++ "-" ++ show d

Note that operators like ++ won't work. They are not functors. They join lists, not construct them.

Guards are boolean expressions that must evaluate to true for the branch to work.

They could be thought of as an alternative for switch/case constructs.

The idea of guards could also be thought as a piecewise function.

\[fib(n) = \left\{\begin{matrix} 0 & n=0 \\ 1 & n=1 \\ fib(n-1)+fib(n-2) & else \end{matrix}\right.\]

1 2 3 4

fib n |n==0 = 0 |n==1 = 1 |otherwise = fib(n-1) + fib(n-2)

otherwise is just defined to be true

As-patterns let you bind a name to the whole pattern even though you want to split it. The syntax is of the form var@pattern where var is the variable to which the entire pattern binds.

Here is a variant of map.

Consider the code:

1 2 3

contrivedMap :: ([a] -> a -> b) -> [a] -> [b] contrivedMap f [] = [] contrivedMap f (x:xs) = f (x:xs) x : contrivedMap f xs

This could better be written as

1 2 3

contrivedMap :: ([a] -> a -> b) -> [a] -> [b] contrivedMap f [] = [] contrivedMap f list@(x:xs) = f list x : contrivedMap f xs

using as-patterns.