Introduction programming with Haskell

What I want to do in this post is not to give a detailed introduction of Haskell language or functional programming, but to give basic idea of what functional programming is and to constrast it with object oriented programming and other languages such Java or C#, and especially what makes functional programming with Haskell so special.

History of two main camps of programming

From the beginning of computing there are two main approaches to programmings which are quite apposite in directions, yet trying to come close to each other.

One is top-down approach which stresses the abstraction of functional programming trickling down from a higher abstraction based on lambda calculus to the hardware specifications. This includes languages such as Haskell, OCaml...

Another one is bottom-up approach which focuses on trying to get close to the hardware as much as possible by building up from hardware abtraction. This include languages such as C, C++, Java...

Definition of functional programming

functional programming can be viewed as a style of programming in which the basic method of computation is the application of functions to arguments. In turn, a functional program- ming language is one that supports and encourages the functional style.

Characteristic of functional programming

Programs in traditional languages, such as C, C++, and Java depends a great deal on modifying the values of a collection of variables, called the state. These are imperative or procedural languages in which function change state of variable. function has somewhat more important status that data or variable.

In functional programming function is an expression that corresponds to mathematical function f. There is no state so we can not use assignments since there is nothing to assign to. Function can be passed around and treated like data. Instead of sequencing and looping, functional languages use recursive functions. C, for example does not allow one to create new functions dynamically.

Let's see an example for a factorial function we imperative language we can use loop like this:

int factorial(int n) {
  int result = 1;
  while (n > 0) {
    result = result * (n--)
  }
  return result;
}

In functional programming we can only use recursive like this:

  let result factorial n =
    if n = 0 then 1
    else n * factorial(n - 1);

Here is another example of programming with sum up of integer: in C for example one would write something as:

int sum(n) {
  int sum = 0;
  for(int i =1; i <= n; i++) {
    sum += i
  }
  return sum;
}

in this implementation we see the state change of sum gradually;

in functional programming such as Haskell

sum [1..n]

will do the job. There is no assignment, so no change of state.

Installation

Let make it run and try to test it. We can go to this website https://www.haskell.org/platform/ and choose the correct platform to use: I'll use ubuntu for this post.

  $ sudo apt-get install haskell-platform
  $ ghci # run in console

Why should we prefer functional programming to imperative one?

Perhap the main reason is that functional programs correspond more directly to mathematical objects, and it is therefore easier to reason about them. In imperative languages it is hard to make definite meaning of a function called denotational semantics in a mathematical sense since state of the object changes.

for example:

int --> Z (set of integer)

so the factorial function above can be written as:

f: int --> int

This opens up more possibilities for correctness proofs.

One more advantage is that since each sub-expression in a function is stateless; the execution of one expression does not effect the other, this makes it easier and possible to feed each sub expression to different processors hence improving performance.

But functional programming has disadvantages. Since it correspond less directly the the eventual execution in hardware, it can be dificult to reason about their exact usage of resources such as time and space.

Things we can remember

  • In functional programming function and data have almost the same role. One is not more important than the other. If we can make an anology in a mathematical sense of a function between set then we can easily get into the essence of functional programming. The main idea is to controlling types, so that nothing leak outside of the domain.
  • This lead to the idea of monads and monoids, which I think I will explore in the next post.