Why Haskell Is Important for Research, Part 1 of N

| Comments

I would like to write a bit about my experience using Haskell for academic research. I have been working on a project with several UW faculty addressing information asymmetry in inventory models. Part of this research involved solving a finite horizon dynamic program. The reference implementation was written in Matlab, and was extremely slow. So slow, in fact, that it ran for a month and produced no output.

During the tail end of 2013, I had been casually studying Haskell, mostly reading about it on the bus and programming in my mind. I took the opportunity to use Haskell to solve this problem. The results were amazing. What would have taken months to solve in Matlab solved in less than 4 minutes in a program written by an intermediate-level Haskell programmer (and, judging myself as intermediate may be generous).

The implementation and results will be saved for another blog post. What follows is are the beginnings of my thoughts on why Haskell is the perfect language for academic research.

Functional Programming

What is a function?

Functional programming (FP) is a programming paradigm in which the function itself is a first-class object. The term functional in FP comes from the idea that within FP, there is a much closer mapping between the mathematical definition of a function and its equivalent in code. In mathematics, we define a function to have input , and produce output , where the capitalized notation is used to remind ourselves that and can be numbers, vectors, or arbitrary sets of mathematical objects. In mathematics, we define a function as in Eq. 1, denoting that output depends solely on input , and the characteristics of the function itself.

Equation 1: Alternatively, we can write , where we read this as “ is a mapping from an input in the space of to an output in the space of .” As a simple example, for the Euclidean norm, , where is the space of inputs and is the space of outputs.

Two very simple properties emerge from this mapping.

Property 1. For , . Property 2. is invariant to changes in objects outside the set .

These properties may seem like an an obvious exposition, but consider the dissonance between the definition of a function in the context of mathematics, and our use of the word “function” when writing computer code.

Property 1 Violated
1
2
3
4
5
6
7
8
9
10
11
12
13
double global_variable = 1.0;

double code_f(double x) {
  double y;
  y = 2.0 * x + global_variable;
  global_variable = global_variable + 1.0; // increment the global variable
  return(y);
}

void main() {
  double y1 = code_f(1.0);             // = 3.0
  double y2 = code_f(1.0);             // = 4.0
}

In discussion this code, we would casually refer to code_f as a “function”, because it takes input and produces output. However, in light of Property 1 we see that, due to the global variable, code_f is not a function as we have defined it according to Eq. 1. Specifically, global_variable is a global variable with mutable state. The argument set for code_f is x. We see that the first property is violated. Namely, for (X = X’, f(X) \neq f(X’)).

We can also easily construct, using a global variable, a violation of the second property.

Property 2 Violated
1
2
3
4
5
6
7
8
9
10
11
12
13
double global_variable = 1.0;

double code_g(double x) {
  double y;
  y = 2.0 * x + global_variable;
  return(y);
}

void main() {
  double y3 = code_g(1.0);             // = 3.0
  global_variable = 10.0;              // change something outside of X
  double y4 = code_g(1.0);             // = 13.0
}

In the previous listing, property two is violated because a change outside of the argument set of code_g can change the value of code_g(1.0). This, strictly speaking, code_g is not a function in the strict mathematical sense. By contrast, consider the following function for squaring numbers.

Square
1
2
3
double square(double x) {
  return (x*x);
}

As square does not depend on the global state of any variable, a call to square for a given input x will always return the same output. There is a clear mapping between square and the mathematical function . To distinguish this from functions which do depend on global state, we can call this a pure function. Functions whose values can change depending on global state are denoted impure.

Functional Programming Concepts

To be continued…

Comments