Haskell Pattern Matching

One of the most interesting aspects of computer science are programming languages, they are the means by which the user and the computer interact and in their choices support certain modes of thought. Some modes of thought are promoted more than others, the dominant style being imperative programming in which you tell the computer explicitly what to do and how to do it. Intuitively this makes a lot of sense, and for that reason it is by far the most dominate paradigm for programming. Besides being intuitive, it is also promoted much more that other options, beginners start with Python, Ruby or JavaScript and for that reason they perpetuate the same ideas, and the same notions of how you program.

This has the fortunate side effect of making programming more generally accessible, but at the cost of new schools of thought and the possibility of better ways of doing things. For the past few weeks I've been starting to learn more about Functional Programming in Haskell and it is difficult to understand, but there are loads of interesting a great ideas that other languages miss completely.

Take for example this implementation of the Ackermann program. It illustrates a few of the features that we're interested in and is also rather interesting due to how quickly the program builds in complexity.

ackermann :: Int -> Int -> Int
ackermann m n
    | m == 0 = n + 1
    | m > 0 && n == 0 = ackermann (m-1) 1
    | otherwise = ackermann (m-1) $ ackermann m (n-1)

This Ackermann function is a great introduction to the notion of pattern matching. Before we look at pattern matching or guards (the pipes after ackermann m n), we should first take a look at the type signature. ackermann is a function that takes two Ints and returns another Int. When looking at this many people who are more used to Python, JS or other high level languages would wonder why bother with these type signatures? What do they get us that high level dynamically typed languages don't have?

Well the first key benefit is a key component of what makes Haskell interesting, Haskell features a static type system, which in short means that your errors are caught at compile time as opposed to run time. If we ever had an instance in which ackermann would take some other datatype we would know before running the program and wondering where we went wrong. This is important for catching errors, but more importantly it changes how you think about your functions. Instead of diving into coding something you sit down and divide the functions into responsibilities and types. This makes programming a much more careful and thought out process.

The second interesting aspect of ackermann is pattern matching. If you look at line two in ackermann you see m and n. ackermann is called in the form: ackermann 2 3, which matches m to 2 and n to 3. You may say this is no different from other languages, but not so! We'll have to look at another example in order to get a better understanding of why pattern matching is useful.

intersperse :: t -> [[t]] -> [t]
intersperse _ []     = []
intersperse _ (x:[]) = x
intersperse sep (x:xs) = x ++ [sep] ++ intersperse sep xs

In a sense, the patterns here are doing what if statements would do in other languages. You can read the first pattern as follows: ignore the first variable, if the second is an empty list return an empty list. Simple right! The biggest reason for the patterns is ease of use when it comes to recursive function calls. If you look at the intersperse function defined above you can start to get a sense of the benefits. Guards which were shown in the ackermann function are closer to the if statements that you've probably seen before or case statements. You can read m == 0 = n + 1 as if m is equal to 0 then return n + 1, in the ackermann function this case is the base case, meaning the case that terminates the recursive calls. With the ackermann function this can take quite a while but you can see the same thing in a simple implementation of the map function.

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

The (x:xs) syntax just splits the list into its head and tail the head is the first element in the list and the tail is everything else. You can see that the function f applies itself to the head of the list, then a new list is made when the map function call is made again.

This was a basic introduction to Haskell Pattern Matching, I hope you found it somewhat useful. To learn more take a look at Real World Haskell or Learn You a Haskell For Great Good.