Haskell pattern matching - what is it?

Question

What is pattern matching in Haskell and how is it related to guarded equations?

I've tried looking for a simple explanation, but I haven't found one.

EDIT: Someone tagged as homework. I don't go to school anymore, I'm just learning Haskell and I'm trying to understand this concept. Pure out of interest.

Answer 1

In a nutshell, patterns are like defining piecewise functions in math. You can specify different function bodies for different arguments using patterns. When you call a function, the appropriate body is chosen by comparing the actual arguments with the various argument patterns. Read A Gentle Introduction to Haskell for more information.

Compare:

with the equivalent Haskell:

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

Note the "n ≥ 2" in the piecewise function becomes a guard in the Haskell version, but the other two conditions are simply patterns. Patterns are conditions that test values and structure, such as x:xs, (x, y, z), or Just x. In a piecewise definition, conditions based on = or ∈ relations (basically, the conditions that say something "is" something else) become patterns. Guards allow for more general conditions. We could rewrite fib to use guards:

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

Answer 2

In a functional language, pattern matching involves checking an argument against different forms. A simple example involves recursively defined operations on lists. I will use OCaml to explain pattern matching since it's my functional language of choice, but the concepts are the same in F# and Haskell, AFAIK.

Here is the definition of a function to compute the length of a list lst. In OCaml, an `a list is defined recursively as the empty list [], or the structure h::t, where h is an element of type a (a being any type we want, such as an integer or even another list), t is a list (hence the recursive definition), and :: is the cons operator, which creates a new list out of an element and a list.

So the function would look like this:

let rec len lst =
  match lst with
    [] -> 0
  | h :: t -> 1 + len t

rec is a modifier that tells OCaml that a function will call itself recursively. Don't worry about that part. The match statement is what we're focusing on. OCaml will check lst against the two patterns - empty list, or h :: t - and return a different value based on that. Since we know every list will match one of these patterns, we can rest assured that our function will return safely.

Note that even though these two patterns will take care of all lists, you aren't limited to them. A pattern like h1 :: h2 :: t (matching all lists of length 2 or more) is also valid.

Of course, the use of patterns isn't restricted to recursively defined data structures, or recursive functions. Here is a (contrived) function to tell you whether a number is 1 or 2:

let is_one_or_two num =
  match num with
    1 -> true
  | 2 -> true
  | _ -> false

In this case, the forms of our pattern are the numbers themselves. _ is a special catch-all used as a default case, in case none of the above patterns match.

Answer 3

Pattern matching is, at least in Haskell, deeply tied to the concept of algebraic data types. When you declare a data type like this:

data SomeData = Foo Int Int
              | Bar String
              | Baz

...it defines Foo, Bar, and Baz as constructors--not to be confused with "constructors" in OOP--that construct a SomeData value out of other values.

Pattern matching is nothing more than doing this in reverse--a pattern would "deconstruct" a SomeData value into its constituent pieces (in fact, I believe that pattern matching is the only way to extract values in Haskell).

When there are multiple constructors for a type, you write multiple versions of a function for each pattern, with the correct one being selected depending on which constructor was used (assuming you've written patterns to match all possible constructions--which it's generally good practice to do).

Answer 4

Pattern matching is one of those painful operations that is hard to get one's head around if you come from procedural programming background. I find it hard to get into because the same syntax used to create a data structure can be used for matching.

In F# you can use the cons operator :: to add an element to the beginning of a list like so:

let a = 1 :: [2;3]
//val a : int list = [1; 2; 3]

Similarly you can use the same operator to split the list up like so:

let a = [1;2;3];;
match a with
    | [a;b] -> printfn "List contains 2 elements" //will match a list with 2 elements
    | a::tail -> printfn "Head is %d" a //will match a list with 2 or more elements
    | [] -> printfn "List is empty" //will match an empty list