Haskell

kuniga.me > NP-Incompleteness > Haskell

Haskell

07 Aug 2011

Haskell Logo

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.

Real World Haskell Book Cover

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.

Setup

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.

Hello World!

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!”

-- Function that calculates the factorial
fact n = if n == 0
      then 1
      else n * fact (n-1)

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:

-- Using pattern matching
fact 0 = 1
fact n = n * fact (n-1)

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,

fact 5

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?

fact 5.1

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:

fact :: Int -> Int
fact 0 = 1
fact n = n * fact (n-1)

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

> fact 30
-8764578968847253504

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:

fact :: Integer -> Integer
fact 0 = 1
fact n = n * fact (n-1)

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

fact :: Integer -> Integer
fact n = product[1..n]

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..10]   -- [1,2,3,4,5,6,7,8,9,10]
[7..2]    -- [7,6,5,4,3,2]
[1,4..15] -- [1,4,7,10,13]

References