So recently I started taking a course about Haskell. This whole functional programming thing has me really hooked lately and I really want to get good at this.

For me as a programmer Haskell is “not” that difficult.

What i mean with that is, Haskell in a sence isn’t hard to grasp. You have functions. Everything is a function. You have a switch statement on steroids (quite insane steroids tbh ^^) and you Algebraic Datatypes (which are also quite nice).

On the other hand there are these Monads and Functors and what not..

Most of the time, when reading something about Haskell, the book/ course either starts with functions or with lambda calculus (and yes this is a really interesting thing ^^ maybe I write a blog post about that too :D).

So you read about all this and you think yeah .. Monad is an abstraction, Functor is a abstraction. I “understand”, but why doesn’t it feel right?

Evaluating Statements

In a “normal” programming language, you write statements. These statements get executed one after another. Thats the way to go.. From top to bottom. Easy. And you know this. That’s the way the program flows.

But as on many occassions, Haskell is different.

Reductions and Reducable Expressions

As you might have guessed by know (at least after this headline), redex is an abbrevation for reducable expression.

To understand what a redex is we first have to define what a expression is.

In lamda calculus a expression is can either be a function, a variable or name or another expression. This holds also true for haskell. Haskell follows lamda calculus very closely.

An expression could be a arithmetic formula written in your code or a string concatenation.

Reduction - this is my simpler form

When writing a simple expression like the following, in order to get the result, you have to reduce it to the simplest from of itself (meaning the result).

    sayHello :: String -> String
    sayHello name = "Hello " ++ name

If we want to apply this function, we need to know a value for the expected parameter.

    -- Let's apply peter for the parameter
    sayHello "Peter"

    -- This could lead to the following reduction path
    sayHello "Peter" = "Hello " ++ "Peter"

    sayHello "Peter" = "Hello Peter"

    -- The result would be "Hello Peter"

We sneakingly introduced a new word in this block of code: Reduction Path

The meaning of the reduction path is that it is the way in which a expression can be reduced to its simplest form.

What we have in this example is a so-called unique reduction path . This means that there is only one reduction possible at a time.

Getting simple in multiple ways

There are also expressions which can be reduced in more than one way at once. This might also appear more often than not.

Look at this example

    (3+4)-(4*8)/2

In this expression we have two parts of the expression which we can reduce from the beginning and then another two or three which can be reduced after that.

This means that we have multiple reduction paths that can be done.

The result doesn’t depend on reduction path!

This is a fundamental theorem called the Church-Rosser theorem.

This means that every terminating reduction path gives the same result.

This means that

• Correctness doesn’t depend on order of evaluation.
• The compiler (or programmer) can change the order freely to improve performance, without affecting the result.
• Different expressions can be evaluated in parallel, without affecting the result. As a result, functional languages are leading contenders for programming future parallel systems

My conclusion

After getting to know all this, suddenly the concepts of Haskell make slightly more sense. I guess this is because this principle is so deeply integrated in the language design that it bleeds through everything that happens in Haskell.

If you don’t know about this, understanding why something happens makes sense and also not at the same moment.

For me this was quite a thing to get my hands on.

I hope this can help someone else, like it helped me ^^‚

Tags

• programming
• functional
• haskell