kuniga.me > NP-Incompleteness > Haskell

07 Aug 2011

I’ve been wanting to learn Haskell, which is a functional language, for some time. The motivation started with a series of posts I’ve been reading about C++ that made references to Haskell concepts most of which I didn’t understand.

I also wanted to remember some concepts from functional languages, which I learned when I studied Lisp in college, but which I ended up forgetting.

I am studying the book Real World Haskell [1], available for online for free. I liked their idea of providing space for comments in each paragraph of the book. Thus, readers act as proofreaders suggesting better examples or correcting typos.

Being the first in a series of notes from my studies of this language, this post will be like an introduction. In the following posts I intend to discuss the most important aspects of language.

To start, you need to install the Haskell interpreter. I’m using `ghci`

to run the programs below. To do so, run `ghci`

in the terminal and load the sources with `:load <filename>`

. Sample codes can be saved with theextension `.hs`

.

Factorial is one of the first problems we see when learning recursion. As functional languages make a lot of use of recursion, let’s start with this example instead of the famous “Hello World!”

Here we have already learned a bit about the syntax of a function:

The name of the function, `fact`

(variable and function names must start with a lowercase letter). The parameter `n`

right after it (it is not necessary to put parentheses encompassing parameters and parameters are separated by spaces, not commas).

After the equal sign, the body of the function is defined, which in this case is an `if`

. Furthermore, functions in Haskell must only be a single expression. The presence of the `if`

gives the impression that there are two, but in practice only one of them will be executed.

The return value is the result of the executed expression. In addition, the type returned by the expressions must be the same and so all `if`

must be accompanied `else`

.

Another way to write the factorial function is through the following code:

Here we see the concept of pattern matching. It resembles a little polymorphism in C++, but here it is a little different because you can define a constant as a parameter. When calling the function fact with the code below,

It search for the function in order until one matches all parameters. So `fact 5`

only matches `fact n`

. This function recurses with values of `n`

until fact `0`

is called. The order in which the functions are defined is important, because the matching is top-down. Note that `fact 0`

matches both `fact 0`

and `fact n`

and if we matched the latter, we would have an infinite loop.

What if we call the function with a real value?

It works, but obviously subtracting 1 will never get the exact 0 value, resulting in an infinite loop. Note that in the function definition we do not define type. However, variables in Haskell do have types. The difference is that Haskell infers the types when possible.

We can restrict the types accepted by a function so that no one calls it improperly. For this, we can use type signature, as per the code below:

The first line defines that the input as well as the output are of type Int. Now let’s calculate factorial of 30:

Which overflows. Fortunately, Haskell has a native implementation of arbitrary-precision integers (big integer), which is the type `Integer`

. We can force our factorial function to use this type if we are going to calculate very large factorials:

There’s an even simpler way to compute the factorial:

This example uses the concept of lists, which are encapsulated by square brackets, have variable length and all their elements must be of the same type.

The syntax `[x..y]`

generates a list with numbers between `x`

and `y`

(inclusive!) with step 1 (`y`

can be less than `x`

, in which case it counts backwards). It is possible to define a custom step by providing the second element of the sequence (not the step length itself). Thus, `[x,y..z]`

will generate from `x`

to `z`

, with step (`y-x`

). Examples:

- [1] Real World Haskell, by Bryan O’Sullivan, Don Stewart, and John Goerzen.