# 1 Introduction

## 1.1 Functional Programming

What is functional programming?

• 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.

• Concise programs (ch2 & ch4)
• Powerful type system (ch3 & ch8)
• List comprehensions (ch5)
• Recursive functions (ch6)
• Higher-order functions (ch7)
• Effectful functions (ch10 & ch12)
• Generic functions (ch12 & ch14)
• Lazy evaluation (ch15)
• Equational reasoning (ch16 & ch17)

# 2 First Steps

## 2.2 Standard Prelude

More most commonly used definitions see appendix B.

## 2.3 Function Application

In mathematics: f(a, b) + c d means apply the function f to a and b, and add the result to the product of c and d.

In Haskell, function application is denoted using space. Multiplication is denoted using *.

Priority: function application is the highest. f a + b means (f a) + b rather than f (a + b).

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

Note that in the 2rd and 4th cases. Without parentheses, f g x and f x g y means apply the function f to g and x ( x, g and y).

Useful GHCi Commands

Command Meaning
:set editor name set editor to name
:edit name edit script name
:edit edit current script
:type expr show type of expr
:? show all commands
:quit quit GHCi

## 2.5 Naming Requirements

• Function and argument names must begin with a lower-case letter.
• myFun
• fun1
• arg_2
• x'
• By convention, list arguments usually have an s suffix on their name.
• xs (a list of arbitrary values)
• ns (a list of numbers)
• nss (a list of lists of numbers)
• css (a list of lists of characters)

# 3 Types and Classes

## 3.1 Types

• A type is a name for a collection of related values. Examples:
• the type Bool contains the two logical values False and True.
• the type Bool -> Bool contains all functions that map arguments from Bool to results from Bool (like the logical negation function not)
• v :: T means that v is a value in the type T, and say that v has a type T. Examples:
• False :: Bool
• True :: Bool
• not :: Bool -> Bool
• More generally, e :: T means that evaluation of the expression e will produce a value of type T. Example:
• not False :: Bool
• not Ture :: Bool
• not (not False) :: Bool

Every well formed expression has a type, which can be automatically calculated at compile time using a process called type inference.

In GHCi, the :type command calculates the type of an expression, without evaluating it:

## 3.2 Basic Types

Type Meaning
Bool logical values
Char single characters
String strings of characters
Int fixed-precision integers (2147483647 ~ -2147483647 for 32-bit machine)
Integer arbitrary-precision integers (no bound but with lower efficiency)
Float single-precision floating-point numbers
Double double-precision floating-point numbers

## 3.3 List Types

• A list is a sequence of elements of the same type. [t] is the type of lists with elements of type t. Examples:
• [False, False, Ture] :: [Bool]
• ['a', 'b', 'c', 'd'] :: [Char]
• [['a'], ['b', 'c']] :: [[Char]]

## 3.4 Tuple Types

• A tuple is a sequence of values of different types. (t1,t2,...,tn) is the type of n-tuples whose ith components have type ti for any i in 1n. Examples:
• (False,True) :: (Bool,Bool)
• (False,'a',True) :: (Bool,Char,Bool)
• ('a',(False,'b')) :: (Char,(Bool,Char))
• (True,['a','b']) :: (Bool,[Char])

## 3.5 Function Types

• A function is a mapping from values of one type to values of another type. t1 → t2 is the type of functions that map values of type t1 to values to type t2. Examples:
• not :: Bool → Bool
• even :: Int → Bool
• add :: (Int,Int) → Int
• add (x,y) = x+y
• zeroto :: Int → [Int]
• zeroto n = [0..n]

## 3.6 Curried Fucntions

• Functions with multiple arguments are also possible by returning functions as results. Functions that take their arguments one at a time are called curried functions. Examples:

• add' :: Int → (Int → Int)

• add' x y = x + y

add' takes an integer x and returns a function add' x. In turn, this function takes

an integer y and returns the result x+y.

Comparison:

• add :: (Int, Int) -> Int
• mult :: Int -> (Int -> (Int -> Int))

• mult x y z = x * y * z

To avoid excess parentheses when working with curried functions, two conventions are adopted:

1. The funciton arrow -> in types is assumed to associate to the right.
• Int -> Int -> Int -> Int means Int -> (Int -> (Int -> Int))
2. Consequently, function application, which is denoted silently using spacing, is assumed to associated to the left.
• mult x y z means ((mult x) y) z

Unless tupling is explicitly required, all functions in Haskell with multiple arguments are normally defined as curried functions.

## 3.7 Polymorphic Types

• A function is called polymorphic (“of many forms”) if its type contains one or more type variables. Examples:
• length :: [a] → Int
• fst :: (a,b) → a
• head :: [a] → a
• take :: Int → [a] → [a]
• zip :: [a] → [b] → [(a,b)]
• id::a → a

• A polymorphic function is called overloaded if its type contains one or more class constraints. Examples:

• (+) :: Num a ⇒ a -> a -> a

For any numeric type a, (+) takes two values of type a and returns a value of type a.

• (==) :: Eq a ⇒ a → a → Bool
• (<) :: Ord a ⇒ a → a → Bool
• negate :: Num a => a -> a
• abs :: Num a => a -> a
• 3 :: Num a => a

## 3.9 Classes

• A class is a collection of types that support certain overloaded operations called methods.

## 3.10 Basic Classes

Class Meaning
Eq equality types (/=, ==)
Ord ordered types (<, >, <=, >=)
Show showable types
Read readable types
Num numeric types
Integral integral types
Fractional fractional types

# 4 Defining Functions

## 4.1 New from Old

The most straightforward way to define new functions is simply by combining one or more existing functions.

• Decide if an integer is even:
• even :: Integral a => a -> Bool
• even n = n mod 2 == 0
• Split a list at the nth element:
• splitAt :: Int -> [a] -> ([a], [a])
• splitAt n xs = (take n xs, drop n xs)
• Reciprocation:
• recip :: Fractional a => a -> a
• recip n = 1/n

## 4.2 Conditional Expressions

As in most programming languages, functions can be defined using conditional expressions.

• The absolute value of an integer:

• abs :: Int -> Int
• abs n = if n >= 0 then n else -n
• The sign of an integer:

• signum :: Int -> Int

• haskell signum n = if n < 0 then -1 else if n == 0 then 0 else 1

• The sign of an integer:

• haskell signum n | n < 0 = n | n == 0 = 0 | otherwise = 1
• The names teller:

• haskell initials :: String -> String -> String initials firstname lastname = [f] ++ ". " ++ [l] ++ "." where (f:) = firstname (l:) = lastname
• The conjunction of two logical values:

• haskell (&&) :: Bool → Bool → Bool True && True = True True && False = False False && True = False False && False = False

• haskell -- can be defined more efficiently by Ture && b = b Flase && _ = False

> > Patterns may not repeat variables. For example, the following definition gives an error: > >

## 4.5 Tuple Patterns

A tuple of patterns is itself a pattern, which matches any tuple of the same arity whose components all match the corresponding patterns in order.

• Select the first and second components of a pair:

• haskell fst :: (a, b) -> a fst (x, _) = x

## 4.6 List Patterns

A list of patterns is itself a pattern, which matches any list of the same length whose elements all match the corresponding patterns in order.

• Decide if a list contains precisely three characters beginning with the letter "a":

• haskell test :: [Char] -> Bool test ['a', , ] = True test _ = False

-- more generally: test :: [Char] -> Bool test ['a':_] = True test _ = False

• haskell capital :: String -> String capital "" = "Empty string, whoops!" capital [email protected](x:xs) = "The first letter of " ++ all ++ " is " ++ [x]

x:xs patterns only match non-empty lists

x:xs patterns must be parenthesised, because application has priority over (:). For example, the following definition gives an error:

## 4.7 Lambda Expressions

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

• The nameless function that takes a number x and returns the result x + x:

• λx → x + x

• haskell -- typed version -> x + x

• Lambda expressions can be used to avoid naming functions that are only referenced once:

• haskell odds n = map f [0..n-1] where f x = x*2 + 1

-- can be simplified to

odds n = map (-> x*2 + 1) [0..n-1]

• This convention also allows one of the arguments of the operator to be included in the parentheses:

• bash > (1+) 2 3 > (+2) 1 3

# 5 List Comprehensions

## 5.1 Set Comprehensions

In mathematics, the comprehension notation can be used to construct new sets from old sets:

{x2 | x ∈ {1..5}}

The set {1,4,9,16,25} of all numbers x2 such that x is an element of the set {1...5}.

## 5.2 List Comprehensions

In Haskell, a similiar comprehension notation can be used to construct new lists from existing lists:

• | is read as such that
• <- is read as is drawn from
• x <- [1..5] is called a generator

## 5.3 Dependant Generators

Later generators can depend on the variables that are introduced by earlier generators:

Using a dependant generator we can define the library function that concatenates a list of lists:

## 5.4 Wildcard Generators

The wildcard pattern _ is sometimes useful in generators to discard certain elements from a list:

Similarly, the library function that calculates the length of a list:

## 5.5 Guards

List comprehensions can use guards to restrict the values produced by earlier generators:

Using a guard we can define a function that maps a positive integer to its list of factors:

A positive integer is prime if its only factors are 1 and itself. Hence, using factors we can define a function that decides if a number is prime:

Using a guard we can now define a function that returns the list of all primes up to a given limit:

Suppose we represent a lookup table by a list of pairs of keys and values. Then for any type of keys that supports equality, a function find that returns the list of all values that are associated with a given key in a table can be defined as:

## 5.6 The zip Function

A useful library function is zip, which maps two lists to a list of pairs of their corresponding elements:

Using zip we can define a function returns the list of all pairs of adjacent elements from a list:

Using pairs we can define a function that decides if the elements in a list are sorted:

Using zip we can define a function that returns the list of all positions of a value in a list:

## 5.7 String Comprehensions

A string is a sequence of characters enclosed in double quotes. Internally, however, strings are represented as lists of characters:

"abc" :: String means ['a', 'b', 'c'] :: [Char]

Because strings are just special kinds of lists, any polymorphic function that operates on lists can also be applied to strings:

Similarly, list comprehensions can also be used to define functions on strings, such counting how many times a character occurs in a string:

## 5.8 Some Notes

• [1,2,3] is the syntax sugar for 1:2:3:[]

• bash # Compare the first elements in two lists, if equals, compare next one, so on and so forth > [3,2,1] > [2,1,0] True > [3,2,1] > [2,10,100] True > [3,4,2] > [3,4] True > [3,4,2] > [2,4] True > [3,4,2] == [3,4,2] True

• bash > [1,20] [1,20] > [2,4..20] [2,4,6,8,10,12,14,16,18,20] > [20,19..1] [20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1] > take 24 [13,26..] [13,26,39,52,65,78,91,104,117,130,143,156,169,182,195,208,221,234,247,260,273,286,299,312] # No floating numbers when using range > [0.1,0.3..1] [0.1,0.3,0.5,0.7,0.8999999999999999,1.0999999999999999] > take 10 (cycle [1,2,3]) [1,2,3,1,2,3,1,2,3,1] > take 10 (repeat 5) [5,5,5,5,5,5,5,5,5,5] > replicate 10 3 [3,3,3,3,3,3,3,3,3,3]

The recursive definition diverges on integers < 0 because the base case is never reached:

## 6.2 Recursion on Lists

Recursion is not restricted to numbers, but can also be used to define functions on lists:

Using the same pattern of recursion as in product we can define the length function on lists:

Using a similar pattern of recursion we can define the reverse function on lists:

In turn, the append operator ++ can itself be defined using recursion on its first argument:

More examples:

## 6.3 Multiple Arguments

Functions with more than one argument can also be defined using recursion:

Zipping the elements of two lists:

Remove the first n elements from a list:

Appending two lists:

## 6.4 Multiple Recursion

Functions can also be defined using multiple recursions:

The quicksort algorithm for sorting a list of values can be specified by the following two rules:

• The empty list is already sorted;
• Non-empty lists can be sorted by sorting the tail values ≤ the head, sorting the tail values > the head, and then appending the resulting lists on either side of the head value.

Using recursion, this specification can be translated directly into an implementation:

## 6.5 Mutual Recursion

Functions can also be defined using mutual recursion, in which two or more functions are all defined recursively in terms of each other:

Similarly, functions that select the elements from a list at all even and odd positions (counting from zero) can be defined as:

# 7 Higher-Order Functions

## 7.1 Basic Concepts

A function is called higher-order if it takes a function as an argument or returns a function as a result:

Why Are They Useful?

• Common programming idioms can be encoded as functions within the language itself.
• Domain specific languages can be defined as collections of higher-order functions.
• Algebraic properties of higher-order functions can be used to reason about programs.

## 7.2 Processing Lists

### 7.2.1 The map Function

The higher-order library function called map applies a function to every element of a list:

### 7.2.2 The filter Function

The higher-order library function filter selects every element from a list that satisfies a predicate:

### 7.2.3 The foldr Function

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

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. Examples:

The higher-order library function foldr (fold right) encapsulates this simple pattern of recursion, with the function ⊕ and the value v as arguments:

Foldr itself can be defined using recursion:

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. Example:

Other Foldr Examples

Even though foldr encapsulates a simple pattern of recursion, it can be used to define many more functions than might first be expected. Recall the length function:

Hence, we have:

...

Finally, we note that the append function (++) has a particularly compact definition using foldr:

Why Is Foldr Useful?

• Some recursive functions on lists, such as sum, are simpler to define using foldr.
• Properties of functions defined using foldr can be proved using algebraic properties of foldr, such as fusion and the banana split rule.
• Advanced program optimisations can be simpler if foldr is used in place of explicit recursion.

## 7.3 The Composition Operator

The library function . returns the composition of two functions as a single function:

Example:

## 7.4 Some Other Library Functions

### 7.4.1 The all Function

The library function all decides if every element of a list satisfies a given predicate:

### 7.4.2 The any Function

Dually, the library function any decides if at least one element of a list satisfies a predicate:

### 7.4.3 The takeWhile Function

The library function takeWhile selects elements from a list while a predicate holds of all the elements:

### 7.4.4 The dropWhile Function

Dually, the function dropWhile removes elements while a predicate holds of all the elements:

# 8 Declaring Types and Classes

## 8.1 Type Declarations

A new name for an existing type can be defined using a type declaration:

Type declarations can be used to make other types easier to read. For example, given:

we can define:

However, type declarations cannot be recursive.

Like function definitions, type declarations can also have parameters. For example, given:

we can define:

Example: a phone book type:

## 8.2 Data Declarations

A completely new type can be defined by specifying its values using a data declaration:

• The two values False and True are called the value constructors for the type Bool.
• Type and constructor names must always 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.

Values of new types can be used in the same ways as those of built in types. For example, given:

we can define:

The constructors in a data declaration can also have parameters. For example, given:

we can define:

• 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:

Data declarations themselves can also have parameters. For example, given:

we can define:

## 8.3 Newtype Declarations

If a new type has a single constructor witha single argument, then it can also be declared using the newtype mechanism.

For example, a type of natural numbers:

## 8.4 Recursive Types

Types can be recursive through data or newtype declarations:

A value of type Nat is either Zero, or of the form Succ n where n :: Nat. That is, Nat contains the following infinite sequence of values:

We can think of values of type Nat as natural numbers, where Zero represents 0, and Succ represents the successor function 1+:

Using recursion, it is easy to define functions that convert between values of type Nat and Int:

Two naturals can be added by converting them to integers, adding, and then converting back:

However, using recursion the function add can be defined without the need for conversions:

## 8.5 Arithmetic Expressions

Using recursion, a suitable new type to represent such expressions can be declared by:

Example:

Using recursion, it is now easy to define functions that process expressions. For example:

• The three constructors have types:

• Many functions on expressions can be defined by replacing the constructors by other functions using a suitable fold function. For example:

## 8.6 Binary Trees

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

Using recursion, a suitable new type to represent such binary trees can be declared by:

We can now define a function that decides if a given value occurs in a binary tree:

But... in the worst case, when the value does not occur, this function traverses the entire tree.

Now consider the function flatten that returns the list of all the values contained in a tree:

A tree is a search tree if it flattens to a list that is ordered. Our example tree is a search tree, as it flattens to the ordered list [1,3,4,5,6,7,9].

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:

This new definition is more efficient, because it only traverses one path down the tree.

# 9 The Countdown Problem

## 9.1 Basic Concept

Given a sequence of numbers and a target number, attempt to construct an expression whose value is the target, by combining one or more numbers from the sequence using addition, subtraction, multiplication, division and parentheses.

More Rules:

• All the numbers, including intermediate results, must be positive naturals (1,2,3,...).
• Each of the source numbers can be used at most once when constructing the expression.

Example:

## 9.2 Evaluating Expressions

Operators:

Apply an operator:

Decide if the result of applying an operator to two positive natural numbers is another such:

Expressions:

Return the overall value of an expression, provided that it is a positive natural number:

## 9.3 Formalising The Problem

Return a list of all possible ways of choosing zero or more elements from a list:

For example:

Return a list of all the values in an expression:

Decide if an expression is a solution for a given list of source numbers and a target number:

## 9.4 Brute Force Solution

Return a list of all possible ways of splitting a list into two non-empty parts:

For example:

Return a list of all possible expressions whose values are precisely a given list of numbers:

Combine two expressions using each operator:

Return a list of all possible expressions that solve an instance of the countdown problem:

How Fast Is It?

Can We Do Better?

• Many of the expressions that are considered will typically be invalid - fail to evaluate.
• For our example, only around 5 million of the 33 million possible expressions are valid.
• Combining generation with evaluation would allow earlier rejection of invalid expressions.

## 9.5 Fusing Two Functions

Valid expressions and their values:

We seek to define a function that fuses together the generation and evaluation of expressions:

This behaviour is achieved by defining:

where:

Combining results:

New function that solves countdown problems:

How Fast Is It Now?

Can We Do Better?

• Many expressions will be essentially the same using simple arithmetic properties, such as:
• x*y = y*x
• x*1 = x`
• Exploiting such properties would considerably reduce the search and solution spaces.

## 9.6 Exploiting Properties

Strengthening the valid predicate to take account of commutativity and identity properties:

How Fast Is It Now?

# 10 Interactive Programming

## 10.1 Basic Concepts

To date, we have seen how Haskell can be used to write batch programs that take all their inputs at the start and give all their outputs at the end.

However, we would also like to use Haskell to write interactive programs that read from the keyboard and write to the screen, as they are running.

## 10.2 The Problem

Haskell programs are pure mathematical functions:

• Haskell programs have no side effects.

However, reading from the keyboard and writing to the screen are side effects:

• Interactive programs have side effects.

## 10.3 The Solution

Interactive programs can be written in Haskell by using types to distinguish pure expressions from impure actions that may involve side effects.

For example:

## 10.4 Basic Actions

The standard library provides a number of actions, including the following three primitives:

• The action getChar reads a character from the keyboard, echoes it to the screen, and returns the character as its result value:

• The action putChar c writes the character c to the screen, and returns no result value:

• The action return v simply returns the value v, without performing any interaction:

## 10.5 Sequencing

A sequence of actions can be combined as a single composite action using the keyword do:

## 10.6 Derived Primitives

• Reading a string from the keyboard:

• Writing a string to the screen:

• Writing a string and moving to a new line:

## 10.7 Example

We can now define an action that prompts for a string to be entered and displays its length:

For example:

Evaluating an action executes its side effects, with the final result value being discarded.

## 10.8 Hangman

Consider the following version of hangman:

• One player secretly types in a word.
• The other player tries to deduce the word, by entering a sequence of guesses.
• For each guess, the computer indicates which letters in the secret word occur in the guess.
• The game ends when the guess is correct.

We adopt a top down approach to implementing hangman in Haskell, starting as follows:

The action sgetLine reads a line of text from the keyboard, echoing each character as a dash:

The action getCh reads a single character from the keyboard, without echoing it to the screen:

The function play is the main loop, which requests and processes guesses until the game ends.

The function match indicates which characters in one string occur in a second string:

For example: