PROGRAMMING IN HASKELL

An Introduction

Based on lecture notes by Graham Hutton

1
What is a Functional Language?

Opinions differ, and it is difficult to give a

precise definition, but generally speaking:

• Functional programming is style of

programming in which the basic method of
computation is the application of functions
to arguments;

• A functional language is one that supports

and encourages the functional style.
2
 Example
Summing the integers 1 to 10 in an
imperative language:

total = 0;
for (i = 1; i  10; ++i)
total = total+i;

The computation method is variable assignment.

3
 Example
Summing the integers 1 to 10 in Haskell:

sum [1..10]

The computation method is function application.

4
 Historical Background
1930s:

Alonzo Church develops the lambda

calculus, a simple but powerful theory
of functions.
5
 Historical Background
1987:

An international committee of researchers initiates the

development of Haskell, a standard lazy functional
language.

Partially in response to “Can programming be

liberated from the Von Neuman style?”, by John
Backus.
6
(Named in honor of logician Haskell B. Curry.)
 Historical Background
2003:

The committee publishes the Haskell 98

report, defining a stable version of the
language. 7
A Taste of Haskell
f [] = []
f (x:xs) = f ys ++ [x] ++ f zs
where
ys = [a | a  xs, a  x]
zs = [b | b  xs, b > x]

? 8
 Basic Structure
• Purely function
• Lazy evaluation
• Statically typed with strong typing
• Uses type inference (like Python)
• VERY concise – small and elegant code
• Types are KEY (like Java or C – but more)

Features we care about:

• On turing
• Website with interface (somewhat limited
functionality)
• Free and easy to download locally 9
Glasgow Haskell Compiler
• GHC is the leading implementation of
Haskell, and comprises a compiler and
interpreter;

• The interactive nature of the interpreter

makes it well suited for teaching and
prototyping;
[Link]/platform

• GHC is freely available from:

10
 Starting GHC on Flip server
The GHC interpreter can be started from the
Unix command prompt by simply typing ghci:

11
The GHCi prompt > means that the
interpreter is ready to evaluate an
expression.

For example:

12
 The Standard Prelude: List
Madness!
Haskell comes with a large number of standard library
functions. In addition to the familiar numeric functions such
as + and *, the library also provides many useful functions
on lists.
Select the first element of a
list: > head [1,2,3,4,5]
1

Calculate the length of a list:

> length [1,2,3,4,5]

5

13
Remove the first element from a list:

> tail [1,2,3,4,5]

[2,3,4,5]

Select the nth element of a list:

> [1,2,3,4,5] !! 2
3

Select the first n elements of a list:

> take 3 [1,2,3,4,5]

[1,2,3]
14
Calculate the product of a list of numbers:

> product [1,2,3,4,5]

120

Append two lists:

> [1,2,3] ++ [4,5]

[1,2,3,4,5]

Reverse a list:

> reverse [1,2,3,4,5]

[5,4,3,2,1]
15
Function Application
In mathematics, function application is
denoted using parentheses, and
multiplication is often denoted using
juxtaposition or space.

f(a,b) + c d

Apply the function f to a and b, and

add the result to the product of c and
d.
16
In Haskell, function application is denoted
using space, and multiplication is denoted
using *.

f a b + c*d

As previously, but in Haskell

syntax.

17
Moreover, function application is assumed
to have higher priority than all other
operators.

fa+b

Means (f a) + b, rather than f (a +

b).

18
Examples
Mathematics Haskell

f(x) fx

f(x,y) fxy

f(g(x)) f (g x)

f(x,g(y)) f x (g y)

f(x)g(y) fx*gy
19
Types
All computation in Haskell is done via evaluation of
expressions to get values. Every value has an
associated type, and is a first class object.
Examples:
• Integer
• Int
• Float
• Char
• Integer->Integer
• [a] -> Integer

e :: t

If evaluating an expression e would produce a value of type t,

then e has type t, written
20
All type errors are found at compile time, which
makes programs safer and faster by removing the
need for type checks at run time.

In GHCi, the :type command calculates the type of

an expression, without evaluating it:

> not False

True

> :type not False

not False :: Bool

> :t head
head :: [a] -> a
21
 My First Script
When developing a Haskell script, it is useful to keep two
windows open, one running an editor for the script, and the
other running GHCi.

Start an editor, type in the following two function definitions,

and save the script as [Link]:

myDouble :: Num a => a -> a

myDouble x = x + x

intDouble :: Int -> Int

intDouble x = x + x

Leaving the editor open, in another window start up GHCi with

the new script:

% ghci [Link] 22
Useful GHCi Commands
Command Meaning

:load name load script

name
:reload reload current
script
:edit name edit script
name
:edit edit current script
:type expr show type of expr
:? show all
commands
23
Leaving GHCi open, return to the editor, add
the following two definitions, and resave:

myFactorial n = product [1..n]

myAverage ns = sum ns `div` length ns

Note:
• div is enclosed in back quotes, not forward;
• x `f` y is just syntactic for f x y.
• So this is just saying div (sum ns) (length ns)

24
GHCi does not automatically detect that the
script has been changed, so a reload
command must be executed before the new
definitions can be used:

> :reload
Reading file "[Link]"

> factorial 10
3628800

> average [1,2,3,4,5]

3

25
Functions are often done using pattern
matching, as well as a declaration of type
(more later):

head :: [a] -> a

head (x:xs) = x

Now you try one…

26
Exercise
Write a program to find the number of
elements in a list. Here’s how to start:

myLength :: [a] -> Int

myLength [] =
myLength (x:xs) =

How do you test this to be sure it

works?

27
 Naming Requirements
• Function and argument names must begin with a lower-
case letter. For example:

myFun fun1 arg_2 x’

• By convention, list arguments usually have an s suffix on

their name. For example:

xs ns nss
28
The Layout Rule
In a sequence of definitions, each definition
must begin in precisely the same column:

a = 10 a = 10 a = 10

b = 20 b = 20 b = 20

c = 30 c = 30 c = 30

29
The layout rule avoids the need for explicit
syntax to indicate the grouping of
definitions.

a = b + c a = b + c
where where
b = 1 means {b = 1;
c = 2 c = 2}
d = a * 2 d = a * 2

implicit explicit
grouping grouping
30
Exercise
Fix the syntax errors in the program
below, and test your solution using
GHCi.
N = a ’div’ length xs
where
a = 10
xs = [1,2,3,4,5]

31
What is a Type?
A type is a name for a collection of related
values. For example, in Haskell the basic
type

Bool

contains the two logical values:

False True

32
Type Errors
Applying a function to one or more
arguments of the wrong type is called a type
error.

> 1 + False
Error

1 is a number and False is a

logical value, but + requires two
numbers.
33
 Basic Types
Haskell has a number of basic types,
including:
Bool - logical values
Char - single characters
String - strings of characters
Int - fixed-precision integers
Integer - arbitrary-precision integers

Float - floating-point numbers

34
List Types
A list is sequence of values of the same
type:
[False,True,False] :: [Bool]

[‘a’,’b’,’c’] :: [Char]

[[‘a’],[‘b’, ‘c’ ]] :: [[Char]]

In general:
[t] is the type of lists with elements of
type t.
35
 Tuple Types
A tuple is a sequence of values of different
types:

(False,True) :: (Bool,Bool)

(False,’a’,True) :: (Bool,Char,Bool)

In general:

(t1,t2,…,tn) is the type of n-tuples

whose ith components have type ti for
any i in 1…n.
36
Function Types
A function is a mapping from values of one
type to values of another type:
not :: Bool -> Bool

isDigit :: Char -> Bool

In general:

t1  t2 is the type of functions that map

values of type t1 to values to type t2.

37
The arrow  is typed at the keyboard as ->.

The argument and result types are

unrestricted. For example, functions with
multiple arguments or results are possible
using lists or tuples:
addXY :: (Int,Int) -> Int
addXY (x,y) = x+y

zeroto :: Int -> [Int]

zeroto n = [0..n]

38
Curried Functions
Functions with multiple arguments are also
possible by returning functions as results:

myAdd :: Int -> Int -> Int

myAdd x y = x+y
map (myAdd 6) [1,2,3,4]
myAdd2 = myAdd 2

myAdd takes one argument at a time

39
As a consequence, it is then natural for
function application to associate to the left.

mult x y z

Means ((mult x) y) z.

Unless tupling is explicitly required, all

functions in Haskell are normally defined in
curried form.
40
 Polymorphic Functions
A function is called polymorphic (“of many forms”)
if its type contains one or more type variables.

length :: [a] 
Int

for any type a, length takes a list of values

of type a and returns an integer.

41
 Ranges in Haskell
As already discussed, Haskell has
extraordinary range capability on lists:
ghci> [1..15]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
ghci> ['a'..'z']
"abcdefghijklmnopqrstuvwxyz"
ghci> ['K'..'Z']
"KLMNOPQRSTUVWXYZ”
ghci> [2,4..20]
[2,4,6,8,10,12,14,16,18,20]
ghci> [3,6..20]
[3,6,9,12,15,18] 42
Infinite Lists
A few useful infinite list functions:
ghci> take 10 (cycle [1,2,3])
[1,2,3,1,2,3,1,2,3,1]
ghci> take 12 (cycle "LOL ")
"LOL LOL LOL "

ghci> take 10 (repeat 5)

[5,5,5,5,5,5,5,5,5,5]

43
 List Comprehensions
Very similar to standard set theory list notation:

ghci> [x*2 | x <- [1..10]]

[2,4,6,8,10,12,14,16,18,20]

Can even add predicates to the comprehension:

ghci> [x*2 | x <- [1..10], x*2 >= 12]

[12,14,16,18,20]

ghci> [ x | x <- [50..100], x `mod` 7 == 3]

[52,59,66,73,80,87,94]

44
Pattern Matching
Functions can often be defined in many different ways using
pattern matching. For example

(&&) :: Bool  Bool  Bool can be defined more

True && True = True compactly by
True && False = False
False && True = False True && True = True
False && False = False _ && _ = False

However, the following definition is more efficient, because it

avoids evaluating the second argument if the first argument is
False:
True && b = b
False && _ = False

Note: The underscore symbol _ is a wildcard pattern that

matches any argument value.
45
Patterns are matched in order. For example,
the following definition always returns False:

_ && _ = False
True && True = True

46
 List Patterns
Internally, every non-empty list is
constructed by repeated use of an operator
(:) called “cons” that adds an element to the
start of a list.

[1,2,3,4]

Means 1:(2:(3:(4:
[]))).

47
Functions on lists can be defined using x:xs
patterns.

head :: [a]  a
head (x:_) = x

tail :: [a]  [a]

tail (_:xs) = xs

head and tail map any non-empty

list to its first and remaining
elements.
48
 Type
It’s of functions
good practice (and REQUIRED in this
class) to also give functions types in your
definitions.
removeNonUppercase :: [Char] -> [Char]
removeNonUppercase st =
[ c | c <- st, c `elem` ['A'..'Z']]

addThree :: Int -> Int -> Int -> Int

addThree x y z = x + y + z

49
Type Classes
In a typeclass, we group types by what
behaviors are supported. (These are NOT
object oriented classes – closer to Java
interfaces.)

Example:
ghci> :t (==)
(==) :: (Eq a) => a -> a -> Bool

Everything before the => is called a type

constraint, so the two inputs must be of a
type that is a member of the Eq class.
50
Type Classes
Other useful typeclasses:

• Ord is anything that has an ordering.

• Show are things that can be presented as
strings.
• Enum is anything that can be sequentially
ordered.
• Bounded means has a lower and upper
bound.
• Num is a numeric typeclass – so things have
to “act” like numbers.
• Integral and Floating what they seem.
51
 Overloaded Functions
A polymorphic function is called overloaded
if its type contains one or more class
constraints.

sum :: Num a  [a] 

a

for any numeric type a,

sum takes a list of values
of type a and returns a
value of type a.
52
Overloaded functions

Constrained type variables can be

instantiated to any types that satisfy the
constraints:
> sum [1,2,3] a = Int
6
a=
> sum [1.1,2.2,3.3]
Float
6.6
Char is not
> sum [’a’,’b’,’c’] a numeric
ERROR type
53
Useful functions: map
The function map applies a function
across a list:
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs

ghci> map (+3) [1,5,3,1,6]

[4,8,6,4,9]

ghci> map (replicate 3) [3..6]

[[3,3,3],[4,4,4],[5,5,5],[6,6,6]]

ghci> map (map (^2)) [[1,2],[3,4,5,6],[7,8]]

[[1,4],[9,16,25,36],[49,64]]
54
Useful functions: filter
The function fliter:
filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter p (x:xs)
| p x = x : filter p xs
| otherwise = filter p xs

ghci> filter (>3) [1,5,3,2,1,6,4,3,2,1]

[5,6,4]
ghci> filter (==3) [1,2,3,4,5]
[3]
ghci> filter even [1..10]
[2,4,6,8,10]
55
 Conditional Expressions
As in most programming languages,
functions can be defined using conditional
expressions.

abs :: Int  Int

abs n = if n  0 then n else -n

Note: In Haskell, conditional expressions must always have an

else branch, which avoids any possible ambiguity issues.

56
 Guarded Equations
As an alternative to conditionals, functions
can also be defined using guarded
equations.

abs n
|n0 =n
| otherwise = -n

As previously, but using guarded

equations.
57
Exercise
Create a function allX that returns
a list of the x’s in a list of ordered
pairs (x,y)

allX :: [(Int, Int)] -> [Int]

58
Exercise
Create a function evens that
returns a list of even numbers from
a list.

evens :: [Int] -> [Int]

59
Exercise
Create a function myElem that
returns True if an element is in a
given list and returns False
otherwise
myElem :: (Eq a) -> a -> [a] -> Bool

60
Exercise
Create a function isAsc that returns
True if if the list given is in
ascending order

isAsc :: [Int] -> Bool

61
Exercise
Create a list of the factors of an
integer

factors :: Int -> [Int]

62
 Lambda Expressions
Functions can be constructed without
naming the functions by using lambda
expressions.

x 
x+x

the nameless function that takes a

number x and returns the result
x+x.
63
Note:

 The symbol  is the Greek letter lambda,

and is typed at the keyboard as a
backslash \.

 In mathematics, nameless functions are

usually denoted using the  symbol, as in
x  x+x.

 In Haskell, the use of the  symbol for

nameless functions comes from the
lambda calculus, the theory of functions 64
Lambda expressions are useful when
defining functions that return functions as
results.

For example:
const :: a  b 
a
const x _ = x

is more naturally defined

by
const :: a  (b 
a)
const x = \_  x
65
Lambda expressions can be used to avoid
naming functions that are only referenced
once.

For example:

odds n = map f [0..n-1]

where
f x = x*2 + 1

can be simplified
to
odds n = map (\x  x*2 + 1) [0..n-
1]
66
 Sections
An operator written between its two
arguments can be converted into a curried
function written before its two arguments by
using parentheses.

For example:

> 1+2
3

> (+) 1 2
3
67
This convention also allows one of the
arguments of the operator to be included in
the parentheses.

For example:

> (1+) 2
3

> (+2) 1
3

In general, if  is an operator then functions

of the form (), (x) and (y) are called
sections.
68
Why Are Sections Useful?
Useful functions can sometimes be
constructed in a simple way using sections.
For example:

(1+) - successor function

(1/) - reciprocation function

(*2) - doubling function

(/2) - halving function

69
 Higher-order Functions
A function is higher-order if it takes a function
as ab argument or returns a function as a
result.

twice :: (a -> a) -> a -> a

twice f x = f (f (x) )

Twice is higher-order because it takes

a function as its first argument.

70
 The Foldr Function
A number of functions on lists can be defined
using the following simple pattern of
recursion:

f [] = v
f (x:xs) = x  f xs

f maps the empty list to some value

v, and any non-empty list to some
function  applied to its head and f of
its tail. 71
For example:

sum [] =0
=0
v

sum (x:xs) = x + sum xs =

+

product [] =1
v =
product (x:xs) = x * product xs 1
=*

v =
and [] = True
and (x:xs) = x && and xs
True
 = &&
72
The higher-order library function foldr (fold
right) encapsulates this simple pattern of
recursion, with the function  and the value v
as arguments.

For example:

sum = foldr (+) 0

product = foldr (*) 1

or = foldr (||) False

and = foldr (&&) True

73
Foldr itself can be defined using recursion:

foldr :: (a  b  b)  b  [a]  b
foldr f v [] =v
foldr f v (x:xs) = f x (foldr f v xs)

However, it is best to think of foldr non-

recursively, as simultaneously replacing each
(:) in a list by a given function, and [] by a
given value.
74
For example:

sum [1,2,3]
=
foldr (+) 0 [1,2,3]
=
foldr (+) 0 (1:(2:(3:[])))
=
1+(2+(3+0))
=
6
Replace each (:)
by (+) and [] by
0.
75
For example:

product [1,2,3]
=
foldr (*) 1 [1,2,3]
=
foldr (*) 1 (1:(2:(3:[])))
=
1*(2*(3*1))
=
6
Replace each (:)
by (*) and [] by 1.
76
Now recall the reverse function:

reverse [] = []
reverse (x:xs) = reverse xs ++ [x]

For example:
Replace each (:)
by x xs  xs ++
reverse [1,2,3] [x] and [] by [].
=
reverse (1:(2:(3:[])))
=
(([] ++ [3]) ++ [2]) ++ [1]
=
[3,2,1]
77
The library function all decides if every
element of a list satisfies a given predicate.

all :: (a  Bool)  [a]  Bool

all p xs = and [p x | x  xs]

For example:

> all even [2,4,6,8,10]

True
78
 Type Declarations
In Haskell, a new name for an existing type
can be defined using a type declaration.

type String = [Char]

String is a synonym for the type

[Char].
79
Type declarations can be used to make other
types easier to read. For example, given

type Point = (Int,Int)

we can
define:

origin :: Point
origin = (0,0)

left :: Point  Point

left (x,y) = (x-1,y)
80
Like function definitions, type declarations can
also have parameters. For example, given

type Pair a = (a,a)

we can
define:

mult :: Pair Int  Int

mult (m,n) = m*n

copy :: a  Pair a
copy x = (x,x)
81
Data Declarations
A completely new type can be defined by specifying
its values using a data declaration.

data Pet = Cat | Dog

Pet is a new type, with two new

values Cat and Dog.

• The two values Cat and Dog are called the constructors
for the type Pet.
• Type and constructor names must begin with an upper-
case letter.
• Data declarations are similar to context free grammars.
The former specifies the values of a type, the latter the
sentences of a language.
82
Values of new types can be used in the same
ways as those of built in types. For example,
given
data Answer = Yes | No | Unknown

we can
define:
answers :: [Answer]
answers = [Yes,No,Unknown]

flip :: Answer  Answer

flip Yes = No
flip No = Yes
flip Unknown = Unknown
83
The constructors in a data declaration can
also have parameters. For example, given

data Shape = Circle Float | Rect Float Float

we can
define:
square :: Float  Shape
square n = Rect n n

area :: Shape  Float

area (Circle r) = pi * r^2
area (Rect x y) = x * y
84
Note:

• Shape has values of the form Circle r where r is

a float, and Rect x y where x and y are floats.

• Circle and Rect can be viewed as functions that

construct values of type Shape:

Circle :: Float  Shape

Rect :: Float  Float  Shape

85
Not surprisingly, data declarations
themselves can also have parameters. For
example, given
data Maybe a = Nothing | Just a

we can define:

safediv :: Int  Int  Maybe Int

safediv _ 0 = Nothing
safediv m n = Just (m `div` n)

86
Binary Trees
In computing, it is often useful to store data in a
two-way branching structure or binary tree.

data Tree = Node Int Tree Tree | Leaf

deriving Show
5

3 7

1 4 6 9

Node 5 (Node 3(Node 1 Leaf Leaf)(Node 4 Leaf Leaf))

(Node 7 (Node 6 Leaf Leaf) (Node 9 Leaf Leaf))

87
We can now define a function for a traversal of
a binary tree:

inorder :: Tree -> [Int]

inorder Leaf = []
inorder (Node x l r) = inorder l ++ [x] ++ inorder
r

88
Search trees have the important property that
when trying to find a value in a tree we can
always decide which of the two sub-trees it
may occur in:

occurs m (Leaf) = False

occurs m (Node n l r)
| m==n = True
| m<n = occurs m l
| m>n = occurs m r

This definition is efficient, because it only

traverses one path down the tree.
89
Modules
So far, we’ve been using built-in functions
provided in the Haskell prelude. This is a
subset of a larger library that is provided
with any installation of Haskell.
Examples of other modules:
- lists
- concurrent programming
- complex numbers
- char
- sets
-…
90
 Example: [Link]

To load a module, we need to import it:

import [Link]

All the functions in this module are

immediately available:

numUniques :: (Eq a) => [a] -> Int

numUniques = length . nub
function This is a function in
concatenatio [Link] that removes
n duplicates from a list. 91
File I/O
So far, we’ve worked mainly at the prompt,
and done very little true input or output. This
is logical in a functional language, since
nothing has side effects!

However, this is a problem with I/O, since the

whole point is to take input (and hence
change some value) and then output
something (which requires changing the state
of the screen or other I/O device.

Luckily, Haskell offers work-arounds that

separate the more imperative I/O. 92
A simple example: save the following file as
[Link]

main = putStrLn "hello, world"

Now we actually compile a program:

$ ghc --make helloworld

[1 of 1] Compiling Main
( [Link], helloworld.o )
Linking helloworld ...
$ ./helloworld
hello, world
93
What are these functions?

ghci> :t putStrLn
putStrLn :: String -> IO ()
ghci> :t putStrLn "hello, world"
putStrLn "hello, world" :: IO ()
So putStrLn takes a string and returns an I/O
action (which has a result type of (), the
empty tuple).

In Haskell, an I/O action is one with a side

effect - usually either reading or printing.
Usually some kind of a return value, where ()
is a dummy value for no return. 94
More on getLine:
ghci> :t getLine
getLine :: IO String
This is the first I/O we’ve seen that doesn’t
have an empty tuple type - it has a String.

Once the string is returned, we use the <- to

bind the result to the specified identifier.

Notice this is the first non-functional action

we’ve seen, since this function will NOT have
the same value every time it is run! This is
called “impure” code, and the value name is
“tainted”. 95