Haskell is fun to program in. It's like it lets me create my own little programming language that didn't have math until I added it! All this, and no debugging, really.
-- Jared Updike, Caltech senior
This is the home page for the Haskell track of CS 11. This information is for the Fall 2007 term.
All the administrative information for the Haskell track is on this page.
The Haskell language is named after Haskell Curry, one of the major figures in the development of the theoretical foundations of functional programming languages (notably the theory of combinatory logic). The Haskell language has many interesting features, including:
It is a functional programming language, which we discuss below. In short, functions are data and can be passed as arguments to other functions, created on the fly, and returned from functions. In contrast to other functional programming languages like Scheme and Ocaml, Haskell is purely functional, which means that you must program in a functional style. It also means that functions cannot have side-effects (i.e. they can't change the values of global variables) which makes it much easier to reason about what functions are doing and eliminates large classes of bugs.
It is a type-safe language, which means that all values have types and all types are checked at compile time. Type errors cannot occur at run time. If you've programmed in languages like C, C++, or Java, you're used to compile-time type checking, but Haskell is *much* stricter than those languages (and interestingly, the Haskell type system is also much more powerful and expressive than the type systems of those languages).
To minimize the need to declare types for all values, the language features type inference whereby the types of most values can be automatically derived by the compiler. This makes code much less cluttered.
It is very easy to define new data types which are checked for correctness just like built-in data types are.
One class of types is called algebraic data types which are like
the union types of C, except that they're type-safe. Once
you've used algebraic data types, you'll wonder how you ever lived without
them. In conjunction with this, Haskell has powerful pattern-matching
features which make it easy to use these types.
Haskell features polymorphic types which are types which are parameterized over other types (e.g. list of "a", where "a" is an arbitrary type). This allows you to define functions that work the same way over a large number of types.
Haskell is a lazily evaluated language, which means that nothing is computed unless it has to be. This has a very strong influence on the way programs are written.
Unused memory is reclaimed by garbage collection. You never have to free memory explicitly.
Haskell allows you to define type classes, which allow you to overload related operations over different types.
Haskell supports monads which have many interesting uses. One of the most prominent uses is as a way of incorporating input/output within a purely functional framework.
Plus many other features that there isn't enough space to cover here (as well as new ones that are continually being developed).
Haskell is a highly enjoyable language to program in for many tasks, but it isn't perfect. Here are a few of the problems that are commonly encountered:
Compared to (say) Ocaml, code written in Haskell is often somewhat slow. Much of this is because of lazy evaluation, and much of the slowdown can be removed if you're sufficiently expert at the language.
Ineffective or excessive use of lazy evaluation can result in space leaks, where much more space is being consumed than is needed for the computation being performed.
The learning curve for Haskell is quite steep; we'll try to make that learning curve shallower in this track.
Despite this, people have written and are writing real applications in Haskell. Some of the best-known applications include:
The darcs revision control system.
The xmonad window manager (which I use every day).
The pugs Perl 6 compiler/interpreter.
In addition, one of the nice things about Haskell is that it will definitely open your mind to a new way of writing programs. One thing to be aware of about Haskell is that, as one IRC poster said, "Haskell is bad, it makes you hate other languages." Once you start programming in Haskell, programming in most other languages will start to feel like wading waist-deep through a swamp. I love programming in Haskell, and I hope you will too.
Functional programming is a paradigm of programming (i.e. a particular way of writing programs) which contrasts greatly with the more common imperative and object-oriented paradigms. Haskell is a pure functional language, which means that it only supports functional programming. But what exactly is functional programming?
First off, functional programming means that functions are data. This means that functions can be passed as arguments to other functions, they can be created on the fly, they can be returned from a function, and they can be stored into data structures. Most computer languages (e.g. C) will allow you to pass a function as an argument to another function (although Java doesn't even allow that unless you wrap the function in an object) but they won't allow you to create a function on the fly. In addition to this, functions can hold references to data objects that existed when they were created and use them when they're invoked (such functions are called "closures" and are really like lightweight objects).
Another key aspect of functional programming is that data should be persistent. Put differently, it means that you cannot use mutable data in pure functional programming. So re-assigning the values of variables is impossible in Haskell! Most programmers probably think that it's impossible to program without using mutable variables all over the place, but it is indeed possible; it just requires that you think differently. Instead of using variables, you use constants: values that are bound to an identifier which don't change after being assigned. This is more like the way we think in mathematics: when we say that "a = 5" we mean that "a" represents the number "5" from that point on, not just until we change it to something else. In fact, one of the interesting aspects of functional programming is that it's much more amenable to mathematical verification of algorithm correctness than imperative programming is.
The fact that data is persistent in Haskell has a large number of effects on the way you write programs in the language, including:
Functions are referentially transparent. This means that functions act as "black boxes"; they always produce the same output given the same input.
Looping statements of the kind seen in C, C++ and Java
(for loops and while loops) are not used; instead,
we use recursion to do computations that involve loops.
We don't normally use updatable arrays for storing aggregate data; instead we use data structures like singly-linked lists or trees. That's because these data structures are persistent; for instance, you can add an element to the front of a list, and a variable which referred to the original list will still refer to the same data. Functional programming requires us to learn how to program using a completely different set of data structures than what imperative programmers are used to.
Lecture 1
Lecture 2
Lecture 3
Lecture 4
Lecture 5
Lecture 6
Current grades for all students are located on this page.
I have a separate page on Haskell books and papers that you should be aware of. It's mostly going to be useful after you finish this track, because it contains links to more advanced material.
The Haskell home page is at www.haskell.org. The definition of the language and its libraries is here. There is a lot of tutorial material linked from this page. Also check out the Short introduction to Haskell for an excellent overview of the language.
The primary reference for this track will be the Gentle Introduction to Haskell. Despite the name, it's not that gentle (except perhaps in the sense that Ex-Lax is gentle), but it will get you up to speed on the language quickly.
There are several excellent textbooks on Haskell aimed at beginners that I recommend. These include:
Programming in Haskell by Graham Hutton, which is a good introduction for absolute beginners.
The Haskell School of Expression by Paul Hudak, which uses multimedia programs as a way of motivating the study of Haskell.
Haskell: the Craft of Functional Programming by Simon Thompson, which is a more orthodox approach.
Introduction to Functional Programming using Haskell by Richard Bird. This book is more theoretically-oriented than the first two and less gentle (and more expensive!), but if you can handle it, it will get you up to speed on the language much faster.
A really useful book on functional data structures is Chris Okasaki's Purely Functional Data Structures, which you may be able to take out from the library (or buy, if you're really keen). Although the code examples are in Standard ML, Haskell translations of the code are included in the book.
A great book for learning about functional programming, geared towards novice programmers, is Abelson and Sussman's Structure and Interpretation of Computer Programs. It uses the Scheme programming language, which is much simpler than Haskell. The book (available online for free) is a great way to prepare yourself for learning Haskell. The first two chapters cover functional programming is considerable detail.
The Glasgow Haskell Compiler. This is the Haskell compiler we'll be using, and it also contains an interpreter.
A tour of the Haskell Prelude. This is useful for looking up prelude functions. You'll find out all about these as we go along, but basically they're library functions that are built-in.