Personal tools

A brief introduction to Haskell

From HaskellWiki

Revision as of 02:43, 27 October 2006 by DonStewart (Talk | contribs)

Jump to: navigation, search

Haskell is:

  • A language developed by the programming languages research community.
  • Is a lazy, purely functional language (that also has imperative features such as side effects and mutable state, along with strict evaluation)
  • Born as an open source vehicle for programming language research
  • One of the youngest children of ML and Lisp
  • Particularly useful for programs that manipulate data structures (such as compilers and interpreters), and for concurrent/parallel programming

Inspired by the Introduction to OCaml.


1 Background


  • 1990. Haskell 1.0
  • 1991. Haskell 1.1
  • 1993. Haskell 1.2
  • 1996. Haskell 1.3
  • 1997. Haskell 1.4
  • 1998. Haskell 98
  • 2000-2006. Period of rapid language and community growth
  • ~2007. Haskell Prime


2 Haskell features

Has some novel features relative to Java (and C++).

  • Immutable variables by default (mutable state programmed via monads)
  • Pure by default (side effects are programmed via monads)
  • Lazy evaluation: results are only computed if they're required (strictness optional)
  • Everything is an expression
  • First-class functions: functions can be defined anywhere, passed as arguments, and returned as values.
  • Both compiled and interpreted implementations available
  • Full type inference -- type declarations optional
  • Pattern matching on data structures -- data structures are first class!
  • Parametric polymorphism
  • Bounded parametric polymorphism

These are all conceptually more advanced ideas.

Compared to similar functional languages, Haskell differs in that it has support for:

  • Lazy evaluation
  • Pure functions by default
  • Monadic side effects
  • Type classes
  • Syntax based on layout

The GHC Haskell compiler, in particular, provides some interesting extensions:

  • Generalised algebraic data types
  • Impredicative types system
  • Software transactional memory
  • Parallel, SMP runtime system

3 The Basics

Read the language definition to supplement these notes. For more depth and examples see the Haskell wiki.

3.1 Interacting with the language

Haskell is both compiled and interpreted. For exploration purposes, we'll consider interacting with Haskell via the GHCi interpreter:

  • expressions are entered at the prompt
  • newline signals end of input

Here is a GHCi sessoin, starting from a UNIX prompt.

   $ ghci
      ___         ___ _
     / _ \ /\  /\/ __(_)
    / /_\// /_/ / /  | |      GHC Interactive, version 6.4.2, for Haskell 98.
   / /_\\/ __  / /___| |
   \____/\/ /_/\____/|_|      Type :? for help.
   Loading package base-1.0 ... linking ... done.
Here the incredibly simple Haskell program
let x = 3+4
is compiled and loaded, and available via the variable
Prelude> let x = 3 + 4

We can ask the system what type it automaticaly inferred for our

x :: Integer
means that the variable
"has type"
, the type of unbounded

integer values.

Prelude> :t x
x :: Integer

A variable evaluates to its value.

Prelude> x
The variable
is in scope, so we can reuse it in later


Prelude> x + 4
Local variables may be bound using
, which declares a

new binding for a variable with local scope.

Prelude> let x = 4 in x + 3

Alternatively, declarations typed in at the top level are like an open-ended let:

Prelude> let x = 4
Prelude> let y = x + 3
Prelude> x * x
Prelude> :t x
x :: Integer
Prelude> :t y
y :: Integer
Prelude> :t x * x
x * x :: Integer

Notice that type inference infers the correct type for all the expressions, without us having to ever specify the type explicitly.

4 Basic types

There is a range of basic types, defined in the language Prelude.

Int         -- bounded, word-sized integers
Integer     -- unbounded integers
Double      -- floating point values
Char        -- characters
String      -- strings
()          -- the unit type
Bool        -- booleans
[a]         -- lists
(a,b)       -- tuples / product types
Either a b  -- sum types
Maybe a     -- optional values

For example:

True, False
('x', 42)
Left True, Right "string"
Nothing, Just True

These types have all the usual operations on them, in the standard libraries.

4.1 Libraries

  • The Prelude contains the core operations on basic types. It is imported by default into every Haskell module. For example;
+ - div mod && || not < > == /=

Learn the Prelude well. Less basic functions are found in the standard libraries. For data structures such as List, Array and finite maps.

To use functions from these modules you have to import them, or in GHCi, refer to the qualified name, for example to use the toUpper function on Chars:

Prelude> Char.toUpper 'x'
Prelude> :m + Char
Prelude Char> toUpper 'y'

In a source file, you have to import the module explicitly:

import Char

4.2 Overloading

Haskell uses typeclasses to methodically allow overloading. A typeclass describes a set of functions, and any type which provides those functions can be made an instance of that type. This avoids the syntactic redundancy of languages like OCaml.

For example, the function
is a method of the typeclass
, as we can see from its type:
Prelude> :t (*)
(*) :: (Num a) => a -> a -> a

Which can be read as "* is a polymorphic function, taking two types 'a', and returning a result of the same type, where those types are members of the class Num".

This means that it will operate on any type in the
class, of which the following types are members:
Double, Float,
Int, Integer
. Thus:
Prelude> 2.3 * 5.7

or on integers:

Prelude> 2 * 5
The type of the arguments determines which instance of

used. Haskell also never performs implicit coercions, all coercions must be explicit. For example, if we try to multiply two different types,

then the type check against
* :: Num a => a -> a -> a


Prelude> (2.3 :: Double) * (5 :: Int)
    Couldn't match `Double' against `Int'
      Expected type: Double
      Inferred type: Int
    In the expression: 5 :: Int
    In the second argument of `(*)', namely `(5 :: Int)'
To convert 5 to a
we'd write:
Prelude> (2.3 :: Double) * fromIntegral (5 :: Int)

Why bother -- why not allow the system to implicitly coerce types? Implicit type conversions by the system are the source of innumerable hard to find bugs in languages that support them, and makes reasoning about a program harder, since you must apply not just the language's semantics, but an extra set of coercion rules.

Note that If we leave off the type signatures however, Haskell will helpfully infer the most general type:

Prelude> 2.3 * 5

4.3 Expressions

In Haskell expressions are everything. There are no pure "statements" like in Java/C++. instead, statements are also expressions, they return values.

Prelude> (if 2 == 3 then 5 else 6) + 1
Prelude> (if 2 == 3 then 5 else 6.5) + 1

4.4 Local bindings

In Haskell
allows local declarations to be defined.
let x = 1 + 2 in x + 3

is analogous to:

   int x = 1 + 2;
   ... x + 3 ... ;

in C, but the Haskell variable x is given a value that is immutable (can never change).

4.5 Allocation

When you declare a new variable, Haskell automatically allocates that value for you -- no need to explicitly manage memory. The garbage collector will then collect any ureachable values once they go out of scope.

Advanced users can also manage memory by hand using the foreign function interface.

4.6 Lists

Lists are ... lists of Haskell values. Defining a new list is trivial, easier than in Java.

Prelude> [2, 1+2, 4]
Prelude> :t [2, 1+2, 4]
[2, 1+2, 4] :: (Num a) => [a]

This automatically allocates space for the list and puts in the elements. Haskell is garbage-collected like Java so no explicit de-allocation is needed. The type of the list is inferred automatically. All elements of a list must be of the same type.

Prelude> ["e", concat ["f", "g"], "h"]
Notice how the function call
concat ["f","g"]
does not require

parenthesis to delimit the function's arguments. Haskell uses whitespace, and not commas, and:

  • You don't need parentheses for function application in Haskell:
    sin 0.3
  • Multiple arguments can be passed in one at a time (curried) which means they can be separated by spaces:
    max 3 4

Lists must be uniform in their type ("homogenous").

Prelude> ['x', True]
Couldn't match `Char' against `Bool'

Here we tried to build a list containing a Char and a Boolean, but the

list constructor,
, has type:
Prelude> :t []
[] :: [a]
meaning that all elements must be of the same type,

(For those wondering how to build a list of heterogenous values, you would use a sum type):

Prelude> [Left 'x', Right True]
[Left 'x',Right True]
Prelude> :t [Left 'x', Right True]
[Left 'x', Right True] :: [Either Char Bool]

List operations are numerous, as can be seen in the Data.List library.

Prelude> let x = [2,3]
Prelude> let y = 1 : x  -- 'cons' the value 1 onto the list
Prelude> x              -- the list is immutable
Prelude> y
Prelude> x ++ y         -- joining lists
Prelude> head y         -- first element of the list is the 'head'
Prelude> tail y         -- the rest of the list is the 'tail'

4.7 Pattern matching

Haskell supports pattern matching on data structures. This is a powerful language feature, making code that manipulates data structures incredibly simple. The core language feature for pattern matching is the

Prelude> case x of h:t -> h
(the scrutinee) to match pattern
, a list with head and tail, and then we extract the head,
. Tail is similar, and we can use a wildcard

pattern to ignore the part of the pattern we don't care about:

Prelude> case x of _:t -> t

4.8 Tuples

Tupes are fixed length structures, whose fields may be of differing types ("heterogenous"). They are known as product types in programming language theory.

Prelude> let x = (2, "hi")
Prelude> case x of (y,_) -> y

Unlike the ML family of languages, Haskell uses the same syntax for the value level as on the type level. So the type of the above tuple is:

Prelude> :t x
x :: (Integer, [Char])

All the data mentioned so far is immutable - it is impossible to change an entry in an existing list, tuple, or record without implicitly copying the data! Also, all variables are immutable. By default Haskell is a pure language. Side effects, such as mutation, are discussed later.

5 Functions

Here is a simple recursive factorial function definition.

Prelude> let fac n = if n == 0 then 1 else n * fac (n-1)
Prelude> :t fac
fac :: (Num a) => a -> a
Prelude> fac 42
The function name is
, and the argument is
. This function is recursive (and there is no need to

specially tag it as such, as you would in the ML family of languages).

When you apply (or invoke) the fac function, you don't need any special parenthesis around the code. Note that there is no return statement; instead, the value of the whole body-expression is implicitly what gets returned.

Functions of more than one argument may be defined:

Prelude> let max a b = if a > b then a else b
Prelude> max 3 7

Other important aspects of Haskell functions:

  • Functions can be defined anywhere in the code via lambda abstractions:
Prelude> ((\x -> x + 1) 4) + 7
Or, identical to
let f x = x + 1
Prelude> let f = \x -> x + 1
Prelude> :t f
f :: Integer -> Integer

Anonymous functions like this can be very useful. Also, functions can be passed to and returned from functions. For example, the higher order

, applies its function argument to each

element of a list (like a for-loop):

Prelude> map (\x -> x ^ 2) [1..10]

In Haskell, we can use section syntax for more concise anonymous functions:

Prelude> map (^ 2) [1..10]
takes two arguments, the function </hask>(^

2) :: Integer -> Integer</hask>, and a list of numbers.

5.1 Currying

Currying is a method by which function arguments may be passed one at a time to a function, rather than passing all arguments in one go in a structure:

Prelude> let comb n m = if m == 0 || m == n then 1 else comb (n-1) m + comb (n-1) (m-1)
Prelude> comb 10 4
The type of comb,
Num a => a -> a -> a
, can be rewritten as
Num a => a -> (a -> a)
. That is, it takes a single argument of some numeric type
, and returns a function that takes

another argument of that type!

Indeed, we can give comb only one argument, in which case it returns a function that we can later use:

Prelude> let comb10 = comb 10
Prelude> comb10 4
Prelude> comb10 3

Mutually recursive functions may defined in the same way as normal functions:

let take []      = []
         (x:xs)  = x : skip xs
    skip []      = []
         (_:ys)  = take ys
Prelude> :t take
take :: [a] -> [a]
Prelude> :t skip
skip :: [a] -> [a]
Prelude> take [1..10]
Prelude> skip [1..10]

This example also shows a pattern match with multiple cases, either empty list or nonempty list. More on patterns now.

5.2 Patterns

Patterns make function definitions much more succinct, as we just saw.

let rev []     = []
    rev (x:xs) = rev xs ++ [x]
In this function definition,

are patterns against which the value passed to the function is matched. The match occurs on the structure of the data -- that is, on its constructors.

Lists are defined as:

data [] a = [] | a : [a]
That is, a list of some type a has type
, and it can be

built two ways:

  • either the empty list,
  • or an element consed onto a list, such as
    1 : []
1 : 2 : 3 : []
  • For the special case of lists, Haskell provides the syntax sugar:
to build the same data. Thus,
matches against the empty list constructor, and
, match against the cons constructor, binding

variables x and xs to the head and tail components of the list.

Remember that
is the syntactic primitive for

performing pattern matching (pattern matching in let bindings is sugar

). Also, the first successful match is taken if

more than one pattern matches:

case [1,2,3] of
    (x:y)   -> True
    (x:y:z) -> False
    []      -> True
Warning: Pattern match(es) are overlapped
         In a case alternative: (x : y : z) -> ...

Warnings will be generated at compile time if patterns don't cover all possibilities, or contain redundant branches.

Prelude> :set -Wall
Prelude> case [1,2,3] of (x:_) -> x
Warning: Pattern match(es) are non-exhaustive
         In a case alternative: Patterns not matched: []

An exception will be thrown at runtime if a pattern match fails:

Prelude> let myhead (x:_) = x
Warning: Pattern match(es) are non-exhaustive
         In a case alternative: Patterns not matched: []
Prelude> myhead []
*** Exception: <interactive>:1:16-36: Non-exhaustive patterns in case

As we have seen, patterns may be used in function definitions. For example, this looks like a function of two arguments, but its a function of one argument which matches a pair pattern.

Prelude> let add (x,y) = x + y
Prelude> add (2,3)

6 Declaring our own types

7 Imperative features: monadic IO, references, mutable arrays, exceptions

8 Type classes