Difference between revisions of "Introduction"

From HaskellWiki
Jump to: navigation, search
(making qsort more attractive)
m (first stab at cleanup. spellchecked it as well, primarily search and replaces.)
Line 1: Line 1:
 
Haskell is a computer programming language. In particular, it is a
 
Haskell is a computer programming language. In particular, it is a
<i> polymorphicly typed, lazy, purely functional </i> language, quite
+
'' polymorphicly typed, lazy, purely functional '' language, quite
 
different from most other programming languages.
 
different from most other programming languages.
 
The language is named for [[Haskell Brooks Curry]], whose work in mathematical logic serves as a foundation for
 
The language is named for [[Haskell Brooks Curry]], whose work in mathematical logic serves as a foundation for
 
functional languages.
 
functional languages.
Haskell is based on <i>lambda calculus</i>, hence the lambda we use as
+
Haskell is based on ''lambda calculus'', hence the lambda we use as
 
a logo.
 
a logo.
   
   
== Why Use Haskell? ==
+
==Why Use Haskell?==
 
 
Writing large software systems that
 
Writing large software systems that
 
work is difficult and expensive. Maintaining those systems is even
 
work is difficult and expensive. Maintaining those systems is even
Line 34: Line 34:
 
Haskell offers you:
 
Haskell offers you:
 
<ul>
 
<ul>
<li>Substantially increased programmer productivity (Ericsson measured
+
*Substantially increased programmer productivity (Ericsson measured
 
an improvement factor of between 9 and 25 using Erlang, a functional programming language similar to Haskell, in one set of experiments on telephony software).
 
an improvement factor of between 9 and 25 using Erlang, a functional programming language similar to Haskell, in one set of experiments on telephony software).
<li>Shorter, clearer, and more maintainable code.
+
*Shorter, clearer, and more maintainable code.
<li>Fewer errors, higher reliability.
+
*Fewer errors, higher reliability.
<li>A smaller &quot;semantic gap&quot; between the programmer and the
+
*A smaller &quot;semantic gap&quot; between the programmer and the
 
language.
 
language.
   
<li>Shorter lead times.
+
*Shorter lead times.
 
</ul>
 
</ul>
 
Haskell is a wide-spectrum language, suitable for a variety of
 
Haskell is a wide-spectrum language, suitable for a variety of
Line 47: Line 47:
 
be highly modifiable and maintainable.
 
be highly modifiable and maintainable.
   
Much of a software product's life is spent in <I>specification</I>,
+
Much of a software product's life is spent in ''specification'',
<I>design</I> and <I>maintenance</I>, and not in <I>programming</I>.
+
''design'' and ''maintenance'', and not in ''programming''.
 
Functional languages are superb for writing specifications which can
 
Functional languages are superb for writing specifications which can
 
actually be executed (and hence tested and debugged). Such a
 
actually be executed (and hence tested and debugged). Such a
specification then <I>is</I> the first prototype of the final
+
specification then ''is'' the first prototype of the final
 
program.
 
program.
   
 
Functional programs are also relatively easy to maintain, because the
 
Functional programs are also relatively easy to maintain, because the
 
code is shorter, clearer, and the rigorous control of side effects
 
code is shorter, clearer, and the rigorous control of side effects
eliminates a huge class of unforseen interactions.
+
eliminates a huge class of unforeseen interactions.
 
=== What is functional programming? ===
 
   
C, Java, Pascal, Ada, and so on, are all <I>imperative</I>
 
  +
===What is functional programming?===
 
C, Java, Pascal, Ada, and so on, are all ''imperative''
 
languages. They are &quot;imperative&quot; in the sense that they
 
languages. They are &quot;imperative&quot; in the sense that they
 
consist of a sequence of commands, which are executed strictly one
 
consist of a sequence of commands, which are executed strictly one
after the other. Haskell is a <i>functional</i> language. A
+
after the other. Haskell is a ''functional'' language. A
 
functional program is a single expression, which is executed by
 
functional program is a single expression, which is executed by
 
evaluating the expression.
 
evaluating the expression.
Line 67: Line 68:
 
Anyone who has used a spreadsheet has experience of functional
 
Anyone who has used a spreadsheet has experience of functional
 
programming. In a spreadsheet, one specifies the value of each cell
 
programming. In a spreadsheet, one specifies the value of each cell
in terms of the values of other cells. The focus is on <I>what</I> is
+
in terms of the values of other cells. The focus is on ''what'' is
to be computed, not <I>how</I> it should be computed. For
+
to be computed, not ''how'' it should be computed. For
 
example:
 
example:
   
 
<ul>
 
<ul>
<li>we do not specify the order in which the cells should be
+
*we do not specify the order in which the cells should be
 
calculated -&nbsp;instead we take it for granted that the
 
calculated -&nbsp;instead we take it for granted that the
 
spreadsheet will compute cells in an order which respects their
 
spreadsheet will compute cells in an order which respects their
 
dependencies.
 
dependencies.
<li>we do not tell the spreadsheet how to allocate its memory
+
*we do not tell the spreadsheet how to allocate its memory
 
-&nbsp;rather, we expect it to present us with an apparently
 
-&nbsp;rather, we expect it to present us with an apparently
 
infinite plane of cells, and to allocate memory only to those cells
 
infinite plane of cells, and to allocate memory only to those cells
 
which are actually in use.
 
which are actually in use.
<li>for the most part, we specify the value of a cell by an
+
*for the most part, we specify the value of a cell by an
<I>expression</I> (whose parts can be evaluated in any order), rather
+
''expression'' (whose parts can be evaluated in any order), rather
by a <I>sequence of commands </I> which computes its
+
by a ''sequence of commands '' which computes its
 
value.
 
value.
 
</ul>
 
</ul>
Line 104: Line 105:
 
relation should be computed, without saying how it should be computed.
 
relation should be computed, without saying how it should be computed.
 
Indeed, the query can be evaluated in any convenient order. SQL
 
Indeed, the query can be evaluated in any convenient order. SQL
implementations often perform extensive query optimisation which
+
implementations often perform extensive query optimization which
 
(among other things) figures out the best order in which to evaluate
 
(among other things) figures out the best order in which to evaluate
 
the expression.
 
the expression.
   
=== What's good about functional programming? ===
+
===What's good about functional programming?===
+
Spreadsheets and SQL are both fairly specialized languages.
Spreadsheets and SQL are both fairly specialised languages.
 
 
Functional programming languages take the same ideas, and move them
 
Functional programming languages take the same ideas, and move them
 
into the realm of general-purpose programming. To get an idea of what
 
into the realm of general-purpose programming. To get an idea of what
Line 117: Line 118:
 
and the second in C.
 
and the second in C.
   
==== Quicksort in Haskell ====
+
====Quicksort in Haskell====
 
 
<haskell>
 
<haskell>
 
qsort [] = []
 
qsort [] = []
 
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)</haskell>
 
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)</haskell>
   
==== Quicksort in C ====
+
====Quicksort in C====
 
<pre>
 
<pre>
 
qsort( a, lo, hi ) int a[], hi, lo;
 
qsort( a, lo, hi ) int a[], hi, lo;
Line 168: Line 169:
 
</BLOCKQUOTE>
 
</BLOCKQUOTE>
   
==== 1. Brevity ====
+
====1. Brevity====
 
Functional programs tend to be much more <B>concise</B> than their
 
Functional programs tend to be much more <B>concise</B> than their
 
imperative counterparts. Quicksort is a rather extreme case, but in
 
imperative counterparts. Quicksort is a rather extreme case, but in
 
general functional programs are much shorter (two to ten times).
 
general functional programs are much shorter (two to ten times).
==== 2. Ease of understanding ====
 
  +
 
====2. Ease of understanding====
 
Functional programs are often easier to <B>understand</B>.
 
Functional programs are often easier to <B>understand</B>.
 
You should be able to understand the program without any previous
 
You should be able to understand the program without any previous
Line 190: Line 192:
 
the rest of which is called <tt>xs</tt>, sort the elements of <tt>xs</tt> that are less than <tt>x</tt>, sort the elements of <tt>xs</tt> that are greater than or equal to <tt>x</tt>, and concatenate (<tt>++</tt>) the results with <tt>x</tt> sandwiched in the middle."
 
the rest of which is called <tt>xs</tt>, sort the elements of <tt>xs</tt> that are less than <tt>x</tt>, sort the elements of <tt>xs</tt> that are greater than or equal to <tt>x</tt>, and concatenate (<tt>++</tt>) the results with <tt>x</tt> sandwiched in the middle."
   
==== 3. No core dumps ====
+
====3. No core dumps====
 
Most functional languages, and Haskell in particular, are <B>strongly
 
Most functional languages, and Haskell in particular, are <B>strongly
 
typed</B>, eliminating a huge class of easy-to-make errors at compile
 
typed</B>, eliminating a huge class of easy-to-make errors at compile
Line 197: Line 199:
 
following a null pointer.
 
following a null pointer.
   
==== 4. Code re-use ====
+
====4. Code re-use====
 
Of course, strong typing is available in many imperative languages,
 
Of course, strong typing is available in many imperative languages,
 
such as Ada or Pascal. However, Haskell's type system is much less
 
such as Ada or Pascal. However, Haskell's type system is much less
Line 210: Line 212:
 
Polymorphism enhances re-usability.
 
Polymorphism enhances re-usability.
   
==== 5. Strong glue ====
+
====5. Strong glue====
 
Non-strict functional languages have another powerful feature: they
 
Non-strict functional languages have another powerful feature: they
 
only evaluate as much of the program as is required to get the answer
 
only evaluate as much of the program as is required to get the answer
Line 251: Line 253:
 
allows us to write more <B>modular programs</b>.
 
allows us to write more <B>modular programs</b>.
   
==== 6. Powerful abstractions ====
+
====6. Powerful abstractions====
 
In general, functional languages offer powerful new ways to
 
In general, functional languages offer powerful new ways to
 
encapsulate <B>abstractions</B>. An abstraction allows you to define
 
encapsulate <B>abstractions</B>. An abstraction allows you to define
 
an object whose internal workings are hidden; a C procedure, for
 
an object whose internal workings are hidden; a C procedure, for
example, is an abstraction. Abstractions are <I>the</I> key to
+
example, is an abstraction. Abstractions are ''the'' key to
 
building modular, maintainable programs, so much so that a good
 
building modular, maintainable programs, so much so that a good
 
question to ask of any new language is "what mechanisms for
 
question to ask of any new language is "what mechanisms for
Line 271: Line 273:
 
Very many sophisticated programs need to allocate dynamic memory from
 
Very many sophisticated programs need to allocate dynamic memory from
 
a heap. In C this is done with a call to <tt> malloc</tt>, followed by code to
 
a heap. In C this is done with a call to <tt> malloc</tt>, followed by code to
initialise the store just allocated. The programmer is responsible
+
initialize the store just allocated. The programmer is responsible
 
for returning the store to the free pool when it isn't needed any
 
for returning the store to the free pool when it isn't needed any
 
more, a notorious source of &quot;dangling-pointer&quot; errors.
 
more, a notorious source of &quot;dangling-pointer&quot; errors.
Line 280: Line 282:
   
 
Every functional language relieves the programmer of this storage
 
Every functional language relieves the programmer of this storage
management burden. Store is allocated and initialised implicitly, and
+
management burden. Store is allocated and initialized implicitly, and
 
recovered automatically by the garbage collector. The technology of
 
recovered automatically by the garbage collector. The technology of
 
storage allocation and garbage collection is now well developed, and
 
storage allocation and garbage collection is now well developed, and
Line 288: Line 290:
 
It isn't all roses, of course. The C quicksort uses an extremely
 
It isn't all roses, of course. The C quicksort uses an extremely
 
ingenious technique, invented by Hoare, whereby it sorts the array
 
ingenious technique, invented by Hoare, whereby it sorts the array
<I>in place</I>; that is, without using any extra storage. As a
+
''in place''; that is, without using any extra storage. As a
 
result, it runs quickly, and in a small amount of memory. In
 
result, it runs quickly, and in a small amount of memory. In
 
contrast, the Haskell program allocates quite a lot of extra memory
 
contrast, the Haskell program allocates quite a lot of extra memory
Line 303: Line 305:
 
in which the computation is carried out.
 
in which the computation is carried out.
   
==== Functional vs imperative ====
+
====Functional vs imperative====
 
 
But few programs require performance at any cost! After all, we all
 
But few programs require performance at any cost! After all, we all
 
stopped writing assembly-language programs, except perhaps for key
 
stopped writing assembly-language programs, except perhaps for key
Line 337: Line 339:
 
free. First-time users may want to start with [http://haskell.org/hugs/ Hugs], a small, portable Haskell interpreter.
 
free. First-time users may want to start with [http://haskell.org/hugs/ Hugs], a small, portable Haskell interpreter.
   
=== Does Anyone Use Functional Programming? ===
+
===Does Anyone Use Functional Programming?===
 
 
Functional programming languages are used in substantial applications.
 
Functional programming languages are used in substantial applications.
 
For example:
 
For example:
 
<ul>
 
<ul>
<li>
 
  +
*
 
Software AG, a major German software company, market an expert system
 
Software AG, a major German software company, market an expert system
 
(Natural Expert) which is programmed in a functional language. Their
 
(Natural Expert) which is programmed in a functional language. Their
Line 347: Line 349:
 
through which they gain access to an underlying database system. It
 
through which they gain access to an underlying database system. It
 
all runs on an IBM mainframe.
 
all runs on an IBM mainframe.
<li>Ericsson have developed a new functional language, Erlang, to use
+
*Ericsson have developed a new functional language, Erlang, to use
 
in their future telephony applications. They have already written
 
in their future telephony applications. They have already written
 
130k-line Erlang applications, and find them very much shorter and
 
130k-line Erlang applications, and find them very much shorter and
 
faster to develop.
 
faster to develop.
<li>Amoco ran an experiment in which they re-coded in a functional
+
*Amoco ran an experiment in which they re-coded in a functional
 
language a substantial fraction of their main oil-reservoir simulation
 
language a substantial fraction of their main oil-reservoir simulation
code, a critical applictaion. The resulting program was vastly
+
code, a critical application. The resulting program was vastly
 
shorter, and its production revealed a number of errors in the
 
shorter, and its production revealed a number of errors in the
 
existing software. Amoco subsequently transcribed the functional
 
existing software. Amoco subsequently transcribed the functional
 
program into ... with encouraging results.
 
program into ... with encouraging results.
<li>A researcher at the MITRE corporation is using Haskell to
+
*A researcher at the MITRE corporation is using Haskell to
 
prototype his digital signal-processing applications.
 
prototype his digital signal-processing applications.
<li>Researchers at Durham University used a functional language in a
+
*Researchers at Durham University used a functional language in a
 
seven-year project to build LOLITA, a 30,000-line program for
 
seven-year project to build LOLITA, a 30,000-line program for
 
natural-language understanding.
 
natural-language understanding.
<li>Query is the query language of the O2 object-oriented database
+
*Query is the query language of the O2 object-oriented database
 
system. O2Query is probably the most sophisticated
 
system. O2Query is probably the most sophisticated
 
commercially-available object-oriented database query language
 
commercially-available object-oriented database query language
 
and it is a functional language.
 
and it is a functional language.
<li>ICAD Inc market a CAD system for mechanical and aeronautical
+
*ICAD Inc market a CAD system for mechanical and aeronautical
 
engineers. The language in which the engineers describe their design
 
engineers. The language in which the engineers describe their design
 
is functional, and it uses lazy evaluation extensively to avoid
 
is functional, and it uses lazy evaluation extensively to avoid
 
recomputing parts of the design which are not currently visible on the
 
recomputing parts of the design which are not currently visible on the
 
screen. This results in substantial performance improvements.
 
screen. This results in substantial performance improvements.
<li>An incestuous example: the Glasgow Haskell compiler is written in
+
*An incestuous example: the Glasgow Haskell compiler is written in
 
Haskell: a 30,000-line application.
 
Haskell: a 30,000-line application.
 
</ul>
 
</ul>
 
Some other examples of [[Haskell in practice]] are found at this web site.
 
Some other examples of [[Haskell in practice]] are found at this web site.
   
=== Other frequently-asked questions ===
+
===Other frequently-asked questions===
+
''Is functional programming hard to learn?''
<i>Is functional programming hard to learn?</i>
 
 
<blockquote>
 
<blockquote>
 
Functional programming does require a change in perspective, which
 
Functional programming does require a change in perspective, which
Line 385: Line 387:
 
that they can "pick it up on the day".
 
that they can "pick it up on the day".
 
</blockquote>
 
</blockquote>
<I>Aren't functional programs very slow?</i>
+
''Aren't functional programs very slow?''
 
<blockquote>They used to be, perhaps 20 years ago. But the compilers
 
<blockquote>They used to be, perhaps 20 years ago. But the compilers
 
have long since caught up. Haskell programs run fast for all but the
 
have long since caught up. Haskell programs run fast for all but the
Line 394: Line 396:
 
</blockquote>
 
</blockquote>
   
<i>I already have a large application in C or C++; can I benefit from
+
''I already have a large application in C or C++; can I benefit from
functional programming without rewriting my whole system?</i>
+
functional programming without rewriting my whole system?''
 
<blockquote>
 
<blockquote>
   
Line 410: Line 412:
 
</blockquote>
 
</blockquote>
   
<i> What libraries does Haskell support?</i>
+
'' What libraries does Haskell support?''
 
<blockquote>
 
<blockquote>
 
Many software libraries have been developed for Haskell. See the
 
Many software libraries have been developed for Haskell. See the
Line 418: Line 420:
 
</blockquote>
 
</blockquote>
   
<i> What other software tools for Haskell are there? </i>
+
'' What other software tools for Haskell are there? ''
 
<blockquote>
 
<blockquote>
 
Glasgow Haskell comes with a profiler which allows you to find which
 
Glasgow Haskell comes with a profiler which allows you to find which
Line 428: Line 430:
 
</blockquote>
 
</blockquote>
   
<I>Can I get a support contract or a help-line?</i>
+
''Can I get a support contract or a help-line?''
 
<blockquote>
 
<blockquote>
 
It used to be the case that if you wanted help, you had to persuade a
 
It used to be the case that if you wanted help, you had to persuade a
Line 438: Line 440:
   
 
<ul>
 
<ul>
<LI>Support for compilers, tools and libraries.</LI>
+
*Support for compilers, tools and libraries.</LI>
<LI>Help with improving code quality (time, space, robustness,
+
*Help with improving code quality (time, space, robustness,
 
maintainability, etc.) using code reviews and tools.</LI>
 
maintainability, etc.) using code reviews and tools.</LI>
<LI>
 
 
*Help with using libraries, tools and advanced Haskell features such
Help with using libraries, tools and advanced Haskell features such as
 
 
as type system extensions, exception handling, the foreign function interface, test harnesses, and concurrency.
type system extensions, exception handling, the foreign
 
function interface, test harnesses, and concurrency.
 
 
</LI>
 
</LI>
   
<LI>Library and application development.</LI>
+
*Library and application development.</LI>
   
<LI>Staff training.</li>
+
*Staff training.</li>
 
</ul>
 
</ul>
 
These companies and individuals tend to work closely with those
 
These companies and individuals tend to work closely with those
Line 456: Line 456:
   
 
</blockquote>
 
</blockquote>
<i>How can I learn Haskell?</i>
+
''How can I learn Haskell?''
 
<blockquote>
 
<blockquote>
 
For more example and explanations, look at the [http://www.haskell.org/tutorial/ Gentle Introduction to Haskell]. There are a
 
For more example and explanations, look at the [http://www.haskell.org/tutorial/ Gentle Introduction to Haskell]. There are a
Line 462: Line 462:
 
</blockquote>
 
</blockquote>
   
<i>Based on a paper by Simon Peyton Jones.</i>
+
''Based on a paper by [[Simon Peyton Jones]].''

Revision as of 03:51, 27 March 2006

Haskell is a computer programming language. In particular, it is a polymorphicly typed, lazy, purely functional language, quite different from most other programming languages. The language is named for Haskell Brooks Curry, whose work in mathematical logic serves as a foundation for functional languages. Haskell is based on lambda calculus, hence the lambda we use as a logo.


Why Use Haskell?

Writing large software systems that work is difficult and expensive. Maintaining those systems is even more difficult and expensive. Functional programming languages, such as Haskell, can make it easier and cheaper. For example, a new user who wrote a small relational DBMS in Haskell had this to say:

WOW! I basically wrote this without testing just thinking about my program in terms of transformations between types. I wrote the test/example code and had almost no implementation errors in the code! The compiler/type-system is really really good at preventing you from making coding mistakes! I've never in my life had a block of code this big work on the first try. I am WAY impressed.

Even if you are not in a position to use Haskell in your programming projects, learning Haskell can make you a better programmer in any language.

I learned Haskell a couple of years ago, having previously programmed in Python and (many) other languages. Recently, I've been using Python for a project (the choice being determined by both technical and non-technical issues), and find my Python programming style is now heavily influenced (for the better, I hope ;-) by my Haskell programming experience.

Graham Klyne


Haskell offers you:

    • Substantially increased programmer productivity (Ericsson measured
    an improvement factor of between 9 and 25 using Erlang, a functional programming language similar to Haskell, in one set of experiments on telephony software).
    • Shorter, clearer, and more maintainable code.
    • Fewer errors, higher reliability.
    • A smaller "semantic gap" between the programmer and the
    language.
    • Shorter lead times.

Haskell is a wide-spectrum language, suitable for a variety of applications. It is particularly suitable for programs which need to be highly modifiable and maintainable.

Much of a software product's life is spent in specification, design and maintenance, and not in programming. Functional languages are superb for writing specifications which can actually be executed (and hence tested and debugged). Such a specification then is the first prototype of the final program.

Functional programs are also relatively easy to maintain, because the code is shorter, clearer, and the rigorous control of side effects eliminates a huge class of unforeseen interactions.

What is functional programming?

C, Java, Pascal, Ada, and so on, are all imperative languages. They are "imperative" in the sense that they consist of a sequence of commands, which are executed strictly one after the other. Haskell is a functional language. A functional program is a single expression, which is executed by evaluating the expression.

Anyone who has used a spreadsheet has experience of functional programming. In a spreadsheet, one specifies the value of each cell in terms of the values of other cells. The focus is on what is to be computed, not how it should be computed. For example:

    • we do not specify the order in which the cells should be
    calculated - instead we take it for granted that the spreadsheet will compute cells in an order which respects their dependencies.
    • we do not tell the spreadsheet how to allocate its memory
    - rather, we expect it to present us with an apparently infinite plane of cells, and to allocate memory only to those cells which are actually in use.
    • for the most part, we specify the value of a cell by an
    expression (whose parts can be evaluated in any order), rather by a sequence of commands which computes its value.

An interesting consequence of the spreadsheet's unspecified order of re-calculation is that the notion of assignment is not very useful. After all, if you don't know exactly when an assignment will happen, you can't make much use of it! This contrasts strongly with programs in conventional languages like C, which consist essentially of a carefully-specified sequence of assignments, or Java, in which the ordering of method calls is crucial to the meaning of a program.

This focus on the high-level "what" rather than the low-level "how" is a distinguishing characteristic of functional programming languages.

Another well-known nearly-functional language is the standard database query language SQL. An SQL query is an expression involving projections, selections, joins and so forth. The query says what relation should be computed, without saying how it should be computed. Indeed, the query can be evaluated in any convenient order. SQL implementations often perform extensive query optimization which (among other things) figures out the best order in which to evaluate the expression.

What's good about functional programming?

Spreadsheets and SQL are both fairly specialized languages. Functional programming languages take the same ideas, and move them into the realm of general-purpose programming. To get an idea of what a functional program is like, look at the following quicksort programs. They both sort a sequence of numbers into ascending order using a standard method called "quicksort". The first program is written in Haskell and the second in C.

Quicksort in Haskell

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

Quicksort in C

qsort( a, lo, hi ) int a[], hi, lo;
{
  int h, l, p, t;

  if (lo < hi) {
    l = lo;
    h = hi;
    p = a[hi];

    do {
      while ((l < h) && (a[l] <= p)) 
          l = l+1;
      while ((h > l) && (a[h] >= p))
          h = h-1;
      if (l < h) {
          t = a[l];
          a[l] = a[h];
          a[h] = t;
      }
    } while (l < h);

    t = a[l];
    a[l] = a[hi];
    a[hi] = t;

    qsort( a, lo, l-1 );
    qsort( a, l+1, hi );
  }
}

Let's examine some of benefits of Haskell and functional programming. A more detailed case for functional programming can be found in

Why Functional Programming Matters by John Hughes, The Computer Journal, Vol. 32, No. 2, 1989, pp. 98 - 107. Also in: David A. Turner (ed.): Research Topics in Functional Programming, Addison-Wesley, 1990, pp. 17 - 42.

A slightly less formal essay inspired by the paper above can be found in

Why Haskell Matters originally by Sebastian Sylvan

1. Brevity

Functional programs tend to be much more concise than their imperative counterparts. Quicksort is a rather extreme case, but in general functional programs are much shorter (two to ten times).

2. Ease of understanding

Functional programs are often easier to understand. You should be able to understand the program without any previous knowledge of either Haskell or quicksort. The same certainly cannot be said of the C program. It takes quite a while to understand, and even when you do understand it, it is extremely easy to make a small slip and end up with an incorrect program. Here is a detailed explanation of the Haskell quicksort:

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

The first line reads: "The result of sorting an empty list ([]) is an empty list". The second line reads: "To sort a list whose first element is x and the rest of which is called xs, sort the elements of xs that are less than x, sort the elements of xs that are greater than or equal to x, and concatenate (++) the results with x sandwiched in the middle."

3. No core dumps

Most functional languages, and Haskell in particular, are strongly typed, eliminating a huge class of easy-to-make errors at compile time. In particular, strong typing means no core dumps! There is simply no possibility of treating an integer as a pointer, or following a null pointer.

4. Code re-use

Of course, strong typing is available in many imperative languages, such as Ada or Pascal. However, Haskell's type system is much less restrictive than, say, Pascal's, because it uses polymorphism. For example, the qsort program given in Figure 1 will not only sort lists of integers, but also lists of floating point numbers, lists of characters, lists of lists; indeed, it will sort lists of anything which can be compared by the less-than and greater-than operations. In contrast, the C version is restricted to sorting an array of integers.

Polymorphism enhances re-usability.

5. Strong glue

Non-strict functional languages have another powerful feature: they only evaluate as much of the program as is required to get the answer - this is called lazy evaluation. This feature is rather like Unix pipes. For example, the Unix command

grep printf Foo.c | wc

counts the number of lines in the file Foo.c which include the string printf The command "grep printf Foo.c"

produces all lines which contain the string "printf", while the "wc" command counts them. The pipe, written "|", takes the output from the first command and delivers it to the second. The two commands execute together, so that the output of the first is consumed more-or-less immediately by the second. In this way, no large intermediate files need be produced. You can think of wc "demanding" lines from the grep

If the second command only needs some of the output of the first, then execution of the first command might never need to be completed. For example

grep printf Foo.c | head 5

just prints the first 5 lines which contain "printf". There is no need to modify the grep command to take account of the fact that its execution might be abandoned.

Non-strict languages provide exactly this kind of demand-driven evaluation. Data structures are evaluated just enough to deliver the answer, and parts of them may not be evaluated at all. As in the case of Unix commands, this provides powerful "glue" with which to compose existing programs together. What this means is that it is possible to re-use programs, or pieces of programs, much more often than can be done in an imperative setting. Lazy evaluation allows us to write more modular programs.

6. Powerful abstractions

In general, functional languages offer powerful new ways to encapsulate abstractions. An abstraction allows you to define an object whose internal workings are hidden; a C procedure, for example, is an abstraction. Abstractions are the key to building modular, maintainable programs, so much so that a good question to ask of any new language is "what mechanisms for abstraction does it provide?".

One powerful abstraction mechanism available in functional languages is the higher-order function. In Haskell a function is a first-class citizen: it can freely be passed to other functions, returned as the result of a function, stored in a data structure, and so on. It turns out that the judicious use of higher-order functions can substantially improve the structure and modularity of many programs.

7. Built-in memory management

Very many sophisticated programs need to allocate dynamic memory from a heap. In C this is done with a call to malloc, followed by code to initialize the store just allocated. The programmer is responsible for returning the store to the free pool when it isn't needed any more, a notorious source of "dangling-pointer" errors. Furthermore, malloc is fairly expensive, so programmers often

malloc a single large chunk of store, and then allocate "by hand" out of this.

Every functional language relieves the programmer of this storage management burden. Store is allocated and initialized implicitly, and recovered automatically by the garbage collector. The technology of storage allocation and garbage collection is now well developed, and the costs are rather slight.

When C is better

It isn't all roses, of course. The C quicksort uses an extremely ingenious technique, invented by Hoare, whereby it sorts the array in place; that is, without using any extra storage. As a result, it runs quickly, and in a small amount of memory. In contrast, the Haskell program allocates quite a lot of extra memory behind the scenes, and runs rather slower than the C program.

In effect, the C quicksort does some very ingenious storage management, trading this algorithmic complexity for a reduction in run-time storage management costs.

In applications where performance is required at any cost, or when the goal is detailed tuning of a low-level algorithm, an imperative language like C would probably be a better choice than Haskell, exactly because it provides more intimate control over the exact way in which the computation is carried out.

Functional vs imperative

But few programs require performance at any cost! After all, we all stopped writing assembly-language programs, except perhaps for key inner loops, long ago. The benefits of having a more supportive programming model (an arbitrary number of named, local variables instead of a fixed number of registers, for example) far outweigh the modest run-time costs.

Similarly, we willingly accept the costs of a virtual memory paging system, in exchange for the more supportive programming model of an infinite virtual address space. The days of explicit memory overlays are over.

Functional languages take another large step towards a higher-level programing model. Programs are easier to design, write and maintain, but the language offers the programmer less control over the machine. For most programs the result is perfectly acceptable.

What is Haskell?

Haskell is a modern, standard, non-strict, purely-functional programming language. It provides all the features sketched above, including polymorphic typing, lazy evaluation and higher-order functions. It also has an innovative type system which supports a systematic form of overloading and a module system.

It is specifically designed to handle a wide range of applications, from numerical through to symbolic. To this end, Haskell has an expressive syntax, and a rich variety of built-in data types, including arbitrary-precision integers and rationals, as well as the more conventional integer, floating-point and boolean types.

There are a number of compilers and interpreters available. All are free. First-time users may want to start with Hugs, a small, portable Haskell interpreter.

Does Anyone Use Functional Programming?

Functional programming languages are used in substantial applications. For example:

    Software AG, a major German software company, market an expert system (Natural Expert) which is programmed in a functional language. Their users find it easy to develop their applications in this language, through which they gain access to an underlying database system. It all runs on an IBM mainframe.
    • Ericsson have developed a new functional language, Erlang, to use
    in their future telephony applications. They have already written 130k-line Erlang applications, and find them very much shorter and faster to develop.
    • Amoco ran an experiment in which they re-coded in a functional
    language a substantial fraction of their main oil-reservoir simulation code, a critical application. The resulting program was vastly shorter, and its production revealed a number of errors in the existing software. Amoco subsequently transcribed the functional program into ... with encouraging results.
    • A researcher at the MITRE corporation is using Haskell to
    prototype his digital signal-processing applications.
    • Researchers at Durham University used a functional language in a
    seven-year project to build LOLITA, a 30,000-line program for natural-language understanding.
    • Query is the query language of the O2 object-oriented database
    system. O2Query is probably the most sophisticated commercially-available object-oriented database query language and it is a functional language.
    • ICAD Inc market a CAD system for mechanical and aeronautical
    engineers. The language in which the engineers describe their design is functional, and it uses lazy evaluation extensively to avoid recomputing parts of the design which are not currently visible on the screen. This results in substantial performance improvements.
    • An incestuous example: the Glasgow Haskell compiler is written in
    Haskell: a 30,000-line application.

Some other examples of Haskell in practice are found at this web site.

Other frequently-asked questions

Is functional programming hard to learn?

Functional programming does require a change in perspective, which some programmers find hard. But Ericsson's experience in training programmers in Erlang is that most find the transition easy - provided they take the training need seriously rather than assuming that they can "pick it up on the day".

Aren't functional programs very slow?

They used to be, perhaps 20 years ago. But the compilers

have long since caught up. Haskell programs run fast for all but the most performance-demanding applications. At the time of writing, Haskell compiled via GHC is in 2nd place (behind C) in the Great Language Shootout, with other functional languages also ranked highly.

I already have a large application in C or C++; can I benefit from functional programming without rewriting my whole system?

Haskell has been successfully integrated into existing applications in a number of ways. HaskellDirect is an IDL (Interface Description Language) based tool that allows Haskell programs to work with software components. Low level C/C++ interfaces can be generated with Green Card or C->Haskell, allowing tight integration between Haskell and C. These tools have been used to build a large number of successful, mixed language systems.

What libraries does Haskell support?

Many software libraries have been developed for Haskell. See the list of Haskell libraries for a list of much of what is available.

What other software tools for Haskell are there?

Glasgow Haskell comes with a profiler which allows you to find which parts of your program are consuming most time and space. Chalmers Haskell has a space-profiling tool, and a quasi-parallel simulator which allows you to experiment with running your program in parallel. Hugs also has some similar tools. For a complete list, check the tools page.

Can I get a support contract or a help-line?

It used to be the case that if you wanted help, you had to persuade a Haskell research group that your problem was interesting enough or important enough that they should spend time helping you for free.
Whilst that is still an option, there is now a directory of Haskell Consultants who provide:

    • Support for compilers, tools and libraries.
    • Help with improving code quality (time, space, robustness,
    maintainability, etc.) using code reviews and tools.
    • Help with using libraries, tools and advanced Haskell features such

    as type system extensions, exception handling, the foreign function interface, test harnesses, and concurrency.

    • Library and application development.
    • Staff training.

These companies and individuals tend to work closely with those developing Haskell (indeed, they have usually made major contributions to Haskell themselves).

How can I learn Haskell?

For more example and explanations, look at the Gentle Introduction to Haskell. There are a number of textbooks that use Haskell; see Books.

Based on a paper by Simon Peyton Jones.