Adventures in Haskell – Pattern Matching

Simple

Another nice feature of Haskell is pattern matching. I glossed over it in the Fibonacci function, so let’s review.

fib :: (Integral t) => t -> t
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

Analogous code in Java would be:

public int fib(int n) {
    if(n == 0) {
        return 1;
    } else if(n == 1) {
        return 1;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
}

In Java, you declare the variables, then test them to decide what to do. In Haskell, the test is built into the function definition. You could provide one function definition and test within the body, but you actually still use pattern matching even if you don’t realize it. Let’s say you change your code to:

fib :: (Integral t) => t -> t
fib n = if n == 0
        then 1
        else if n == 1
             then 1
             else fib (n - 1) + fib (n - 2)

This is actually just syntactic sugar for:

fib :: (Integral t) => t -> t
fib n = case n == 0 of
          True -> 1
          False -> case n == 1 of
                     True -> 1
                     False -> fib (n - 1) + fib (n - 2)

Guess what? case statements use pattern matching, just like function definitions.

Advanced

Now let’s say you want to write a sum function. Here’s a simple definition:

sum :: (Num t) => [t] -> t
sum [] = 0
sum (x:xs) = x + sum xs

What’s going on here? We have pattern matching again, but not 1-to-1 between arguments and variables. In the first definition, the first argument doesn’t bind to a variable, which is the same as with fib 0. It simple matches an empty list. The second definition is more subtle. It binds x to the first element of the list, and it binds xs to the remainder of the list. This is known as deconstruction, and obviously it has to do with taking things apart. There’s also another tie-in for that term. The colon is actually a constructor for lists. (The parentheses are not special syntax, they just compensate for the colon’s precedence.) If I have a list foo and say 0:foo, I just created a new list with 0 prepended to foo. Deconstruction (in this sense) actually uses constructors in reverse.

Let’s quickly skim over a few more pattern topics. First, some code:

bar w@(x:xs) y | x == y    = w
               | otherwise = bar xs y
bar _ _ = []

There are three things going on here:

  • The at-pattern w matches the whole first argument, while x matches the head and xs matches the tail
  • The pipes are used to create pattern guards. Variables are bound to parts of the pattern, then the guard is executed to see if the pattern should match. As the example shows, patterns can have multiple guards. They are tested sequentially, and the first one to return true is used. If none return true, the whole pattern fails. otherwise is just a commonly-used variable that is set to True to make these more readable.
  • Underscores are wildcards which will match anything. In this case, the second pattern will match anything, but only if the first pattern fails. The only way the first pattern could fail is for the first argument to be an empty list.

Post a Comment

Your email is never shared. Required fields are marked *

*
*