Tuesday, February 25, 2014

Mathematical Pattern Matching

When first starting function programming from a procedural/object oriented background, people sometimes have trouble with a certain feature that has no representation in those language backgrounds. The concept of types in Haskell, though similar to other functional languages, is remarkably different from most procedural/OO languages.

Haskell is inherently based upon manipulation and usage of types. Really, a type is just a name that represents some abstract concept. Although used by the compiler to ensure a program runs correctly, a type is really an identifier for you. Let's begin with the Maybe type.

data Maybe a = Just a
               Nothing
 

If we break this down, Maybe is a name (a type) that is associated with a value (a). However, this value has the possibility of failure. Think of it like setting an errno if it fails. In Haskell, the lowest level construct is a function, and arguments are passed similarly to Lisp: to call a function you put the function name and arguments are then listed afterword separated by spaces. For instance, for a function called add that takes two arguments,

 let x = add 2 3

where the
let means declaring x with a value of whatever add returns.

Let's go back to our
Maybe type. Like I said before, Maybe is really just a label to represent some abstract concept; in this case, the abstract concept is the possibility of a value. When I said before that the lowest level Haskell construct is a function, I meant it. In the case of Maybe, the two things after the equals sign are called constructors. Each one is a function that will return a value that is wrapped in the Maybe type. The Just function takes one parameter and returns a value of the type Maybe. Let's see this in action:

 > let x = Just 4
> x
Just 4
> :t x
Maybe Int


As we can see here, the Just function takes one parameter and returns a value that is wrapped in the Maybe type. If this doesn't make any sense to you, that's OK. We'll iterate on this soon.

Haskell has another construct to facilitate retrieving a value from a type. This is called pattern matching, and it looks like this:
 

> let x = Just 4
> (Just 4) == x
True
> (Just 4) == (Just 4)
True

> let (Just y) = Just 4
> y
4
> let (Just z) = x
> z
4
> x
Just 4
 

This is a very important feature of Haskell, and it is also slightly hard to get your head around for the first time. Let's ditch Haskell for now and stay in the world of mathematics (where Haskell is (almost) completely derived from). Since we know that Just is a function, we can rewrite this as a mathematical equation.

 Given x = j(4)

j(4) = x
j(4) = j(4)
j(y) = j(4)
y = 4
j(z) = x
z = 4
 

As you can see, one can simplify and determine that y and z are both equal to 4, the originally wrapped value. This can also be referred to as type deconstruction. Just is really just a function that represents a wrapper around some value and the conglomerate of Just and its value is part of the Maybe type. If we look at pattern matching in Haskell from this mathematical perspective, then pattern matching (type deconstruction) is really just solving for the value of an unknown variable.