Warning! This blog's new home now is here.

Introduction to Haskell, week 1

10 Aug 2014

A while ago I've finally started to study Haskell, in particular following the CIS 194: Introduction to Haskell course by Brent Yorgey from the Penn University of Pennsilvania. This is the first resource of the curriculum I plan to follow to learn Haskell (thanks a lot to Chris Allen for laying out a path to FP enlightenment :)

I've worked through the first 4 weeks now, but I decided at this point to switch gears and go back to recap what I've learned so far.

Without further ado, let's recap CIS 192: week 1.

What is Haskell?

Haskell (named after Haskell Curry, for his work on combinatory logic and for the Curry-Howard Correspondence), is a lazy, statically typed, pure functional programming language created in the 1980's by a committee of academics. It's very well alive today, as it's one of the most advanced (statically typed) languages out there.

Haskell is:

Functional

Functions are first-class values. That is, they can be passed to other functions or returned by them like any other values.
The computation model is based around evaluating expressions, not executing instructions. In other words, it's not based on the Von Neumann architecture (instructions that operate on a shared memory), but on the lambda calculus (you can think about it in terms of composing functions to transform streams of immutable data).

Pure

Every expression is referentially transparent. This means that:

Everything is immutable. Every "mutation" is modeled as a transformation, a function that doesn't change the original value but creates a new one.
There are no side effects (well, there are: modeled with monads to retain purity, but you don't need to know what a monad is to use them!).

As a consequence of the previous points, calling the same function with the same arguments results in the same output, always.

This approach has a number of very nice benefits, that once you wrap your head around this paradigm you won't give away too easily:

Equational reasoning: thinking about the code becomes much more easier. Refactoring becomes a breeze.
Parallelism: using multiple cores is much easier when you know that functions are guaranteed not to interfere with each another. There is no shared state!

In general, with static types and pure functions programs become much more easy to maintain, refactor, debug and reasoning about.

Lazy

In Haskell values are computed only when needed (call-by-need evaluation strategy).

Advantages:

It's easy to define new control structures just by defining a new function. Contrast this with languages like Clojure where you need macros to achieve that, or languages like Java where it's basically impossible.
It's easy to work with infinite data structures, since values are only computed when needed. You can achieve the same in idiomatic Clojure by using the seq abstraction and lazy-seq, in Java 8 using Streams, etc.
It enables a compositional style (we will see it down the road with wholemeal programming, currying and point-free style).

Downside: it becomes harder to reason about the time and space characteristics of programs.

Themes

The course revolves around thee key areas:

Types
Abstractions
Wholemeal programing

Types

Static type systems can be annoying, and some of them really are. But this isn't because type systems are inherently annoying, that's because some of them are insufficiently expressive (for example, Java and C++ ones).

A type system (especially the Haskell one):

Gives you clarity of thinking and helps you to design and reason about programs. Types become an organizing principle, a precise and powerful tool to think about and express abstractions. Using them, you are able to reason at a higher level, in a systematic way.
Is a form of documentation, always in sync with the actual code.
Turns a lot of runtime errors to compile time ones. Computers can do complex, repetitive and clearly specified things efficiently: why not delegate to them some of the burden that a human has to carry on while writing software?

Once you start to get the hang of it, a (good) type system becomes an invaluable ally. It feels liberating, since it can help you long before you write the first line of code: it helps you in the design of the system.

Abstraction

In some way, designing and maintaining software is a battle against repetition: you frequently need to take similar things and factor out their commonality (a process known as abstraction).

Haskell gives you a lot of abstraction power: parametric polymorphism, higher-order functions, type classes, etc. Its type systems is also a powerful, methodic and sound tool to think mathematically about them.

Wholemeal programming

Quoting Ralf Hinze:

“Functional languages excel at wholemeal programming, a term coined by Geraint Jones. Wholemeal programming means to think big: work with an entire list, rather than a sequence of elements; develop a solution space, rather than an individual solution; imagine a graph, rather than a single path. The wholemeal approach often offers new insights or provides new perspectives on a given problem. It is nicely complemented by the idea of projective programming: first solve a more general problem, then extract the interesting bits and pieces by transforming the general program into more specialised ones.”

In short, it's about working with abstractions rather than concrete instances of the problem/solution space, with group/types of things instead of with single instances.

Next, Brent Yorgey goes on showing the basic types (scalars and lists), how to define and combine functions, etc. Lots of good stuff.