Haskell/Pattern matching

From Wikibooks, the open-content textbooks collection

Pattern matching is a convenient way to bind variables to different parts of a given value.

Note Pattern matching on what? Some languages like Perl and Python use the term pattern matching for matching regular expressions against strings. The pattern matching we are referring to in this chapter is quite different. In fact, you're probably best off forgetting what you know about pattern matching for now. Here, pattern matching is used in the same way as in others ML-like languages : to deconstruct values according to their type specification.

[edit] What is pattern matching?

You've actually met pattern matching before, in the chapter about lists. Recall functions like map:

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

Here there are four different patterns going on: two per equation. Let's explore each one in turn (although not in the order they appeared in that example):

• [] is a pattern that matches the empty list. It doesn't bind any variables.
• (x:xs) is a pattern that matches something (which gets bound to x), which is cons'd, using the function (:), onto something else (which gets bound to the variable xs).
• f is a pattern which matches anything at all, and binds f to that something.
• _ is the pattern which matches anything at all, but doesn't do any binding.

So pattern matching is a way of assigning names to things (or binding those names to those things), and possibly breaking down expressions into subexpressions at the same time (as we did with the list in the definition of map).

However, you can't pattern match with everything. For example, you might want to define a function like the following to chop off the first three elements of a list:

dropThree ([x,y,z] ++ xs) = xs

However, that won't work, and will give you an error. The problem is that the function (++) isn't allowed in patterns. So what is allowed?

The one-word answer is constructors. Recall algebraic datatypes, which look something like:

data Foo = Bar | Baz Int

Here Bar and Baz are constructors for the type Foo. And so you can pattern match with them:

f :: Foo -> Int
f Bar     = 1
f (Baz x) = x - 1

Remember that lists are defined thusly (note that the following isn't actually valid syntax: lists are in reality deeply grained into Haskell):

data [a] = [] | a : [a]

So the empty list, [], and the (:) function, are in reality constructors of the list datatype, so you can pattern match with them.

Note, however, that as [x, y, z] is just syntactic sugar for x:y:z:[], you can still pattern match using the latter form:

dropThree (_:_:_:xs) = xs

If the only relevant information is the type of the constructor (regardless of the number of its elements) the {} pattern can be used:

g :: Foo -> Bool
g Bar {} = True
g Baz {} = False

The function g does not have to be changed when the number of elements of the constructors Bar or Baz changes. Note: Foo does not have to be a record for this to work.

For constructors with many elements, it can help to use records:

data Foo2 = Bar2 | Baz2 {barNumber::Int, barName::String}

which then allows:

h :: Foo2 -> Int
h Baz2 {barName=name} = length name
h Bar2 {} = 0

[edit] The one exception

There is one exception to the rule that you can only pattern match with constructors. It's known as n+k patterns. It is indeed valid Haskell 98 to write something like:

pred :: Int -> Int
pred (n+1) = n

However, this is generally accepted as bad form and not many Haskell programmers like this exception, and so try to avoid it.

[edit] As-patterns

Sometimes, when matching a pattern with a value, it may be useful to bind a name also to the whole value being matched. As-patterns allow exactly this: they are of the form var@pattern and have the additional effect to bind the name var to the whole value being matched by pattern.

For instance, the following code snippet:

other_map f [] = []
other_map f list@(x:xs) = f x list : other_map f xs

creates a variant of map, called other_map, which passes to the parameter function f also the original list. Writing it without as-patterns would have been more cumbersome, because you must recreate the original value, i.e. x:xs:

other_map f [] = []
other_map f (x:xs) = f x (x:xs) : other_map f xs

The difference would be more notable with a more complex pattern.

[edit] Where you can use it

The short answer is that wherever you can bind variables, you can pattern match. Let's have a look at that more precisely.

[edit] Equations

The first place is in the left-hand side of function equations. For example, our above code for map:

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

Here we're binding, and doing pattern-matching, on the left hand side of both of these equations.

[edit] Let expressions / Where clauses

You can obviously bind variables with a let expression or where clause. As such, you can also do pattern matching here. A trivial example:

let Just x = lookup "bar" [("foo", 1), ("bar", 2), ("baz", 3)] 

[edit] Case expressions

One of the most obvious places you can use pattern binding is on the left hand side of case branches:

case someRandomList of
  []     -> "The list was empty"
  (x:xs) -> "The list wasn't empty: the first element was " ++ show x ++ ", and " ++
            "there were " ++ show (length xs) ++ " more elements in the list."

[edit] Lambdas

As lambdas can be easily converted into functions, you can pattern match on the left-hand side of lambda expressions too:

head = (\(x:xs) -> x)

Note that here, along with on the left-hand side of equations as described above, you have to use parentheses around your patterns (unless they're just _ or are just a binding, not a pattern, like x).

[edit] List comprehensions

After the | in list comprehensions, you can pattern match. This is actually extremely useful. For example, the function catMaybes from Data.Maybe takes a list of Maybes, filters all the Just xs, and gets rid of all the Just wrappers. It's easy to write it using list comprehensions:

catMaybes :: [Maybe a] -> [a]
catMaybes ms = [ x | Just x <- ms ]

If the pattern match fails, it just moves on to the next element in ms. (More formally, as list comprehensions are just the list monad, a failed pattern match invokes fail, which is the empty list in this case, and so gets ignored.)

[edit] A few other places

That's mostly it, but there are one or two other places you'll find as you progress through the book. Here's a list in case you're very eager already:

• In p <- x in do-blocks, p can be a pattern.
• Similarly, with let bindings in do-blocks, you can pattern match analogously to 'real' let bindings.

---

Exercises

If you have programmed in a language like Perl and Python before, how does pattern matching in Haskell compare to the pattern matching you know? What can you use it on, where? In what sense can we think of Perl/Python pattern matching as being "more powerful" than the Haskell one, and vice versa? Are they even comparable? You may also be interested in looking at the Haskell Text.Regex library wrapper.