An Introduction to

Programming in Haskell

Mark P Jones
Portland State University
1

Haskell Resources:

Haskell Resources:
The focal point for information about

Haskell programming, implementations,

libraries, etc is [Link]

Ill be using:

the Hugs interpreter ([Link]/hugs)

the Glasgow Haskell compiler, GHC, and
interpreter, GHCi ([Link]/ghc)

Online tutorials/references:

[Link]
[Link]
3

The Language Report:

The definition of the Haskell 98
standard
Lots of technical details not a
great read!
Available in hard copy from
Cambridge University Press
Or in pdf/html/etc from
[Link]/definition
4

Textbooks:

Introduction to Functional Programming using

Haskell (2nd edition), Richard Bird
The Haskell School of Expression, Paul Hudak
Haskell: The Craft of Functional Programming
(2nd edition), Simon Thompson
Programming in Haskell, Graham Hutton

What is Functional
Programming?

What is Functional Programming?

Functional programming is a style of

programming that emphasizes the

evaluation of expressions, rather than
execution of commands

Expressions are formed by using functions

to combine basic values

A functional language is a language that

supports and encourages programming in a

functional style
7

Functions:
In a pure functional language:

The result of a function depends only on

the values of its inputs:

Like functions in mathematics

No global variables / side-effects

Functions are first-class values:

They can be stored in data structures

They can be passed as arguments or returned
as results of other functions
8

Example:
Write a program to add up the
numbers from 1 to 10

In C, C++, Java, C#, :

initialization
initialization

int tot = 0;
for (int i=1; i<10; i++)
tot = tot + i;

iteration

update
update
implicit result returned in the variable tot

10

In ML:

accumulating parameter

let fun sum i tot

= if i>10
then tot
else sum (i+1) (tot+i)
in sum 1 0
end
initialization

(tail) recursion

result is the value of this expression

11

In Haskell:
sum [1..10]
combining
function

the list of numbers to add

result is the value of this expression

12

Raising the Level of Abstraction:

"If you want to reduce [design time], you
have to stop thinking about something you
used to have to think about. (Joe Stoy,
recently quoted on the Haskell mailing list)

Example: memory allocation

Example: data representation
Example: order of evaluation
Example: (restrictive) type annotations
13

Computing by Calculating:
Calculators are a great tool
for manipulating numbers

Buttons for:

entering digits
combining values
using stored values

42.0!

Not so good for manipulating

large quantities of data

Not good for manipulating

other types of data

14

Computing by Calculating:
What if we could calculate
with other types of value?

Buttons for:

entering pixels
combining pictures
using stored pictures

I wouldnt want to calculate a

whole picture this way!

I probably want to deal with

several different types of data at

the same time

15

Computing by Calculating:
Spreadsheets are

better suited for

dealing with larger
quantities of data

Values can be

named (but not operations)

Calculations (i.e., programs) are recorded so that

they can be repeated, inspected, modified

Good if data fits an array

Not so good for multiple types of data

16

Functional Languages:
Multiple types of data

Primitive types, lists, functions,

Flexible user defined types

Operations for combining values to build new

values (combinators)

Ability to name values and operations

(abstraction)

Scale to arbitrary size and shape data

Algebra of programming supports reasoning
17

Getting Started with

Haskell

18

Starting Hugs:
user$ hugs
__
__ __ __ ____
___
||
|| || || || || ||__
||___|| ||__|| ||__|| __||
||---||
___||
||
||
||
|| Version: September 2006

_________________________________________
Hugs 98: Based on the Haskell 98 standard
Copyright (c) 1994-2005
World Wide Web: [Link]
Bugs: [Link]
_________________________________________

Haskell 98 mode: Restart with command line option -98 to enable extensions
Type :? for help
Hugs>

The most important commands:

:q

quit

:l file

load file

:e file

edit file

Expr

evaluate expression

19

The read-eval-print loop:

1. Enter expression at the prompt
2. Hit return
3. The expression is read, checked, and
evaluated
4. Result is displayed
5. Repeat at Step 1

20

Simple Expressions:
Expressions can be constructed using:
The usual arithmetic operations:
1+2*3
Comparisons:
1 == 2
'a' < 'z'
Boolean operators:
True && False
not False
Built-in primitives:
odd 2
sin 0.5
Parentheses:
odd (2 + 1)
(1 + 2) * 3
Etc

21

Expressions Have Types:

The type of an expression tells you what
kind of value you will get when you
evaluate that expression:

In Haskell, read :: as has type

Examples:

1 :: Int, 'a' :: Char, True :: Bool, 1.2 :: Float,

You can even ask Hugs for the type of an

expression: :t expr

22

Type Errors:
Hugs> 'a' && True
ERROR - Type error
*** Expression
*** Term
*** Type
*** Does not match

in application
: 'a' && True
: 'a'
: Char
: Bool

Hugs> odd 1 + 2
ERROR - Cannot infer instance
*** Instance
: Num Bool
*** Expression : odd 1 + 2
Hugs>
23

Pairs:
A pair packages two values into one
(1, 2)

('a', 'z')

(True, False)

Components can have different types

(1, 'z')

('a', False)

(True, 2)

The type of a pair whose first component is

of type A and second component is of type
B is written (A,B)
What are the types of the pairs above?

24

Operating on Pairs:
There are built-in functions for
extracting the first and second
component of a pair:
fst (True, 2) = True
snd (0, 7) = 7

25

Lists:
Lists can be used to store zero or more

elements, in sequence, in a single value:

[]

[1, 2, 3]

['a', 'z']

[True, True, False]

All of the elements in a list must have the

same type
The type of a list whose elements are of
type A is written as [A]
What are the types of the lists above?

26

Operating on Lists:
There are built-in functions for extracting

the head and the tail components of a list:

head [1,2,3,4] = 1
tail [1,2,3,4] = [2,3,4]

Conversely, we can build a list from a given

head and tail using the cons operator:
1 : [2, 3, 4] = [1, 2, 3, 4]

27

More Operations on Lists:

Finding the length of a list:
length [1,2,3,4,5] = 5

Finding the sum of a list:

sum [1,2,3,4,5] = 15

Finding the product of a list:

product [1,2,3,4,5] = 120

Applying a function to the elements of a

list:

map odd [1,2,3,4] = [True, False, True, False]

28

Continued
Selecting an element (by position):
[1,2,3,4,5] !! 3 = 4

Taking an initial prefix (by number):

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

Taking an initial prefix (by property):

takeWhile odd [1,2,3,4,5] = [1]

Checking for an empty list:

null [1,2,3,4,5] = False

29

More ways to Construct Lists:

Concatenation:
[1,2,3] ++ [4,5] = [1,2,3,4,5]

Arithmetic sequences:
[1..10] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1,3..10] = [1, 3, 5, 7, 9]

Comprehensions:
[ 2 * x | x <- [1,2,3,4,5] ] = [2, 4, 6, 8, 10]
[ y | y <- [1,2,3,4], odd y ] = [ 1, 3 ]
30

Strings are Lists:

A String is just a list of Characters
['w', 'o', 'w', '!'] = "wow!"
['a'..'j'] = "abcdefghij"
"hello, world" !! 7 = 'w'
length "abcdef" = 6
"hello, " ++ "world" = "hello, world"
take 3 "functional" = "fun"
31

Functions:
The type of a function that maps

values of type A to values of type B is

written A -> B

Examples:
odd :: Int -> Bool
fst :: (a, b) -> a
(a,b are type variables)
length :: [a] -> Int

32

Operations on Functions:
Function Application. If f :: A -> B and x ::
A, then f x :: B

Notice that function application associates

more tightly than any infix operator:
f x + y = (f x) + y

In types, arrows associate to the right:

A -> B -> C = A -> (B -> C)
Example: take :: Int -> [a] -> [a]
take 2 [1,2,3,4] = (take 2) [1,2,3,4]

33

Sections:
If is a binary op of type A -> B -> C,
then we can use sections:

()
:: A -> B -> C
(expr ) :: B -> C
(assuming expr::A)
( expr) :: A -> C
(assuming expr::B)

Examples:

(1+), (2*), (1/), (<10),

34

Higher-order Functions:
map :: (a -> b) -> [a] -> [b]

map (1+) [1..5] = [2,3,4,5,6]

takeWhile :: (a -> Bool) -> [a] -> [a]

takeWhile (<5) [1..10] = [1,2,3,4]

(.) :: (a -> b) -> (c -> a) -> c -> b

(odd . (1+)) 2 = True

composition

35

Definitions:
So far, weve been focusing on expressions
that we might want to evaluate.

What if we wanted to:

Define a new constant (i.e., Give a name to the

result of an expression)?
Define a new function?
Define a new type?

Definitions are placed in files with a .hs

suffix that can be loaded into the interpreter

36

Simple Definitions:
Put the following text in a file [Link]:
greet name = "hello " ++ name
square x = x * x
fact n = product [1..n]
37

Loading Defined Values:

Pass the filename as a command line argument to
Hugs, or use the :l command from inside Hugs:
Main> :l defs
Main> greet "everybody"
"hello everybody"
Main> square 12
144
Main> fact 32
263130836933693530167218012160000000
Main>

38

Using Libraries:
Many useful functions are provided as part
of the Prelude
Many more are provided by libraries that
must be imported before they can be used
Example:
import Char
nextChar c = chr (1 + ord c)

(The Char library also provides functions for

converting to upper/lower case, testing for
alphabetic or numeric chars, etc)

39

Typeful Programming:
Types are an inescapable feature of
programming in Haskell

Programs, definitions, and expressions that do

not type check are not valid Haskell programs
Compilation of Haskell code depends on
information that is obtained by type checking

Haskell provides several predefined types:

Some built-in (functions, numeric types, )

Some defined in the Prelude (Bool, lists, )

What if you need a type that isnt built-in?

40

Type Synonyms:

41

Type Synonym:
A type synonym (or type abbreviation) gives
a new name for an existing type.

Examples:
type
type
type
type
type
type

String
Length
Angle
Radius
Point
Set a

= [Char]
= Float
= Float
= Length
= (Float, Float)
= a -> Bool
42

Algebraic Datatypes:

43

In Haskell Notation:
data Bool = False | True
introduces:

A type, Bool
A constructor function, False :: Bool
A constructor function, True :: Bool

data List a = Nil | Cons a (List a)

introduces

A type, List t, for each type t

A constructor function, Nil :: List a
A constructor function, Cons :: a -> List a -> List a
44

More Enumerations:
data Rainbow = Red | Orange | Yellow
| Green | Blue | Indigo | Violet
introduces:
A type, Rainbow
A constructor function, Red :: Rainbow

A constructor function, Violet :: Rainbow

45

More Recursive Types:

data Shape

= Circle Radius
| Rect Length Length
| Transform Transform Shape
data Transform
= Translate Point
| Rotate Angle
| Compose Transform Transform
introduces:
Two types, Shape and Transform
Circle :: Radius -> Shape
Rect :: Length -> Length -> Shape
Transform :: Transform -> Shape -> Shape

46

Using New Data Types:

Building values of these new types is
easy:

Nil
:: List Rainbow
Cons Red Nil
:: List Rainbow
Cons Blue (Cons Red Nil) :: List Rainbow

But how do we inspect them or take

them apart?

47

Pattern Matching:
In addition to introducing a new type and a

collection of constructor functions, each data

definition also adds the ability to pattern match
over values of the new type

Example:
first
first (x, y)

:: (a, b) -> a
=x

wavelengths
:: Rainbow -> (Length,Length)
wavelengths Red
= (620*nm, 750*nm)
wavelengths Orange = (590*nm, 620*nm)

nm = 1e-9 :: Float

48

More Examples:
head
head []
head (x:xs)

:: [a] -> a
= error head of []
=x

length
length []
length (x:xs)

:: [a] -> Int

=0
= 1 + length xs

area
area (Circle r)
area (Rect w h)
area (Transform t s)

:: Shape -> Float

= pi * r * r
=w*h
= area s
49

Pattern Matching & Substitution:

The result of a pattern match is either:
A failure
A success, accompanied by a substitution
that provides a value for each of the
values in the pattern

Examples:
[] does not match the pattern (x:xs)
[1,2,3] matches the pattern (x:xs) with
x=1 and xs=[2,3]

50

Patterns:
More formally, a pattern is either:
An identifier

Matches any value, binds result to the identifier

An underscore (a wildcard)

Matches any value, discards the result

A constructed pattern of the form C p1 pn,

where C is a constructor of arity n and p1, ,pn

are patterns of the appropriate type

Matches any value of the form C e1 en, provided that

each of the ei values matches the corresponding pi
pattern.
51

Other Pattern Forms:

For completeness:

Sugared constructor patterns:

Tuple patterns (p1,p2)

Cons patterns (ph : pt)
List patterns [p1, p2, p3]
Strings, for example: "hi" = (h : i : [])

Character and numeric Literals:

Can be considered as constructor patterns, but the

implementation uses equality (==) to test for matches
52

Function Definitions:
In general, a function definition is written as
a list of adjacent equations of the form:
f p1 pn = rhs
where:

f is the name of the function that is being defined

p1, , pn are patterns, and rhs is an expression

All equations in the definition of f must have

the same number of arguments (the arity
of f)
53

 continued:
Given a function definition with m
equations:
f p1,1 pn,1 = rhs1
f p1,2 pn,2 = rhs2

f p1,m pn,m = rhsm

The value of f e1 en is S rhsi, where i is

the smallest integer such that the

expressions ej match the patterns pj,i and S
54
is the corresponding substitution.

Example: filter
filter
:: (a -> Bool) -> [a] -> [a]
filter p []
= []
filter p (x:xs)
|px
= x : rest
| otherwise = rest
where rest = filter p xs
guards

where clause
55

Example: Binary Search Trees

data Tree

= Leaf | Fork Tree Int Tree

insert
insert n Leaf
insert n (Fork l m r)
| n <= m
| otherwise

:: Int -> Tree -> Tree

= Fork Leaf n Leaf
= Fork (insert n l) m r
= Fork l m (insert n r)

lookup
:: Int -> Tree -> Bool
lookup n Leaf
= False
lookup n (Fork l m r)
|n<m
= lookup n l
|n>m
= lookup n r
| otherwise
= True
56

Summary:
An appealing, high-level approach to
program construction in which
independent aspects of program
behavior are neatly separated

It is possible to program in a similar

compositional / calculational manner in

other languages

but it seems particularly natural in a

functional language like Haskell

57

Assignment #1
Your goal is to write a function:

toInt :: String -> Int

To accomplish this, consider the following functions:

explode :: String -> [Char]

digitValue :: [Char] -> [Int]
reverse :: [Int] -> [Int]
pairedWithPowersOf10 :: [Int] -> [(Int,Int)]
pairwiseProduct :: [(Int,Int)] -> [Int]
sum :: [Int] -> Int

Write definitions for four of these functions (reverse and sum are builtin), using pattern matching and recursion where necessary

Turn in an elegant program that communicates your solution well,

including appropriate tests for each part.

58