Thursday, November 11, 2010

Haskell for Math People

I'd like to keep a little quick reference here of tips for reading Haskell code if you are coming from a math background:

  • Function application is left associative and doesn't use parenthesis so f a b c is the same as (((f a) b) c) which is the same as the normal math notation f(a,b,c).
  • Writing function application this way makes it easy to do partial application. For instance if we have a math function f : A\times{}A\rightarrow{}A we can think of it as function f : A\rightarrow(A\rightarrow{}A). That is a function from a space to a space of functions. This function would naturally take one parameter and the "value" that it represents would also take one parameter. To partially apply in Haskell we just provide the number of parameters we want to apply.
  • We often talk about "types" in Haskell and this is somewhat analogous to making statements about the domain and range of a function. For example when we write f :: Int -> Int -> Int in Haskell we are saying that we have a function named f where f : N\times{}N\rightarrow{}N. More precicely types are isomorphic to proofs in constructive mathmatics (see Curry–Howard correspondence).
  • The following program often uses a data structure called a list. We write the type of a list as [a] where a is some type. We construct lists in a few ways
    1. As a list of values: [1,2,3].
    2. Using the : (called "Cons") operator: 1:2:3:[]. The Cons operator is a function that takes a value and a list and produces a new list with that value at the head of the list. The empty list is written as [].
    3. As a list comprehension which we will talk about later.
  • Function definitions in haskell are written with the function name followed by pattern matched arguments, an equals sign, then an expression in terms of the arguments given. We call everything to the left of the equals sign the "left-hand side" or lhs and everything to the right of the equals the "right-hand side" or rhs. Pattern matching is where instead of listing a name for an argument we specify some structure or pattern that the value must fit for the function to be applicable. Haskell will look for the first applicable function and use that expression. For example the function f (x:xs) = (1 + x) : f xs is applicable when given a list. The first element of the list will be bound to x on the rhs while the rest of the list (the tail) will be bound to xs on the rhs. Attempting to apply f to [] would result in a "Non-exhaustive patterns" exception because [] is the empty list and does not have a head and a tail. To fix this we would have to define that base case with f [] = []. We now have a function where given a list of numbers it would result in a new list of numbers where each number is incremented by one.
  • Function composition is written with a period f . g which is meant to mimic the math notation f\circ{}g.


Martijn said...

Nice introduction, thank you. :-)

Small correction: applying f to [] won't result in a compile error but a runtime error. Defining f like that however will result in a compile warning: "Pattern match(es) are non-exhaustive"

Ryan Yates said...

Nice catch, thanks! Building with the "-Wall" option will give a compile time warning in this case.