Haskell - part 2

Defining functions, list comprehensions, and recursive functionsMaterial adapted from Erik Meijer’s Functional ProgrammingA Jupyter notebook version of this material is available online in Google Colab. Although Colab does not support Haskell, the notebook can be downloaded and run in Jupyter Notebook, if the IHaskell extension is installed.

Deﬁning functions

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

abs takes an integer n and returns n if it is non-negative and -n otherwise

abs :: Int -> Int
abs n = if n >= 0 then n else -n

Conditional expressions can be nested:

signum  :: Int → Int
signum n = if n < 0 then -1 else
           if n == 0 then 0 else 1

Note:

In Haskell, conditional expressions must always have an else branch, which avoids any possible ambiguity problems with nested conditionals

signum :: Int -> Int
signum n = if n < 0 then -1 else
           if n == 0 then 0 else 1

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

abs n | n >= 0     = n
      | otherwise = -n

Guarded equations can be used to make definitions involving multiple conditions easier to read:

signum n | n < 0     = -1
         | n == 0    = 0
         | otherwise = 1

Note:

The catch-all condition, otherwise, is defined in the prelude by otherwise = 1

signum n | n < 0     = -1
         | n == 0    = 0
         | otherwise = 1

Pattern matching

Many functions have a particularly clear definition using pattern matching on their arguments

not :: Bool → Bool
not False = True
not True  = False

not maps False to True, and True to False

not :: Bool -> Bool
not False = True
not True  = False

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

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

can be defined more compactly by

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

(&&) :: Bool -> Bool -> Bool
True  && True  = True
True  && False = False
False && True  = False
False && False = False

(&&) :: Bool -> Bool -> Bool
True && True = True
_    && _    = 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

(&&) :: Bool -> Bool -> Bool
True  && b = b
False && _ = False

Patterns are matched in order. For example, the following definition always returns False:

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

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

b && b = b
_ && _ = False

(&&) :: Bool -> Bool -> Bool
_    && _    = False
True && True = True

(&&) :: Bool -> Bool -> Bool
b && b = b
_ && _ = False

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:[])))

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

head :: [a] -> a
head (x:_)  = x

tail :: [a] -> [a]
tail (_:xs) = xs

Note:

x:xs patterns only match non-empty lists:

head [] -- Error

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

head x:_ = x

head [] -- Error

head x:_ = x

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

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 \(\mapsto\) symbol, as in \(x \mapsto x+x\)
In Haskell, the use of the λ symbol for nameless functions comes from the lambda calculus, the theory of functions on which Haskell is based

Why are lambda’s useful?

Lambda expressions can be used to give a formal meaning to functions defined using currying

For example:

add x y = x+y

means add = λx → (λy → x+y)

add x y = x + y

Lambda expressions are also 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

const :: a -> b -> a
const x _ = x

const :: a -> (b -> a)
const x = \_ -> x

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]

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

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

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

1 + 2
(+) 1 2

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

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

## Exercises

Consider a function safetail that behaves in the same way as tail, except that safetail maps the empty list to the empty list, whereas tail gives an error in this case. Define safetail using:

a) a conditional expression;

b) guarded equations;

c) pattern matching.

Hint: the library function null :: [a] → Bool can be used to test if a list is empty.

Give three possible definitions for the logical or operator (||) using pattern matching.
Redefine the following version of (&&) using conditionals rather than patterns:

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

Do the same for the following version:

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

List comprehensions

Set comprehensions

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

\[\{x^2 | x \in \{1...5\}\}\]

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

Lists comprehensions

In Haskell, a similar comprehension notation can be used to construct new lists from old lists.

[x^2 | x ← [1..5]]

The list [1,4,9,16,25] of all numbers x^2 such that x is an element of the list [1..5].

[x^2 | x <- [1..5]]

Note:

The expression x ← [1..5] is called a generator, as it states how to generate values for x
Comprehensions can have multiple generators, separated by commas. For example:

> [(x,y) | x ← [1,2,3], y ← [4,5]]
[(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]

[(x,y) | x <- [1,2,3], y <- [4,5]]

Changing the order of the generators changes the order of the elements in the final list:

> [(x,y) | y ← [4,5], x ← [1,2,3]]
[(1,4),(2,4),(3,4),(1,5),(2,5),(3,5)]

Multiple generators are like nested loops, with later generators as more deeply nested loops whose variables change value more frequently.

[(x,y) | y <- [4,5], x <- [1,2,3]]

For example:

> [(x,y) | y ← [4,5], x ← [1,2,3]]
[(1,4),(2,4),(3,4),(1,5),(2,5),(3,5)]

x ← [1,2,3] is the last generator, so the value of the x component of each pair changes most frequently.

Dependant generators

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

[(x,y) | x ← [1..3], y ← [x..3]]

The list [(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)] of all pairs of numbers (x,y) such that x,y are elements of the list [1..3] and y ≥ x.

[(x,y) | x <- [1..3], y <- [x..3]]

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

concat :: [[a]] → [a]
concat xss = [x | xs ← xss, x ← xs]

For example:

> concat [[1,2,3],[4,5],[6]]
[1,2,3,4,5,6]

concat :: [[a]] -> [a]
concat xss = [x | xs <- xss, x <- xs]
concat [[1,2,3],[4,5],[6]]

Guards

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

[x | x ← [1..10], even x]

The list [2,4,6,8,10] of all numbers x such that x is an element of the list [1..10] and x is even

[x | x <- [1..10], even x]

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

factors :: Int → [Int]
factors n =
    [x | x ← [1..n], n `mod` x == 0]

For example:

```> factors 15 [1,3,5,15]

```haskell
factors :: Int -> [Int]
factors n =
    [x | x <- [1..n], n `mod` x == 0]

factors 15

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:

prime :: Int → Bool
prime n = factors n == [1,n]

For example:

> prime 15
False

> prime 7
True

prime :: Int -> Bool
prime n = factors n == [1,n]

prime 15

prime 7

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

primes :: Int → [Int]
primes n = [x | x ← [2..n], prime x]

For example:

> primes 40
[2,3,5,7,11,13,17,19,23,29,31,37]

primes :: Int -> [Int]
primes n = [x | x <- [2..n], prime x]

primes 40

The zip function

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

zip :: [a] → [b] → [(a,b)]

For example:

> zip ['a','b','c'] [1,2,3,4]
[('a',1),('b',2),('c',3)]

zip ['a','b','c'] [1,2,3,4]

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

pairs :: [a] → [(a,a)]
pairs xs = zip xs (tail xs)

For example:

> pairs [1,2,3,4]
[(1,2),(2,3),(3,4)]

pairs :: [a] -> [(a,a)]
pairs xs = zip xs (tail xs)

pairs [1,2,3,4]

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

sorted :: Ord a ⇒ [a] → Bool
sorted xs = and [x ≤ y | (x,y) ← pairs xs]

For example:

> sorted [1,2,3,4]
True

> sorted [1,3,2,4]
False

sorted :: Ord a => [a] -> Bool
sorted xs = and [x <= y | (x,y) <- pairs xs]

sorted [1,2,3,4]
sorted [1,3,2,4]

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

positions :: Eq a ⇒ a → [a] → [Int]
positions x xs =
    [i | (x',i) ← zip xs [0..n], x == x']
    where n = length xs - 1

For example:

> positions 0 [1,0,0,1,0,1,1,0]
[1,2,4,7]

positions :: Eq a => a -> [a] -> [Int]
positions x xs =
    [i | (x',i) <- zip xs [0..n], x == x']
    where n = length xs - 1

positions 0 [1,0,0,1,0,1,1,0]

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

"abc" :: String
['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. For example:

> length "abcde"
5

> take 3 "abcde"
"abc"

> zip "abc" [1,2,3,4]
[(’a’,1),(’b’,2),(’c’,3)]

length "abcde"

take 3 "abcde"

zip "abc" [1,2,3,4]

Similarly, list comprehensions can also be used to define functions on strings, such as a function that counts the lower-case letters in a string:

lowers :: String → Int
lowers xs =
    length [x | x ← xs, isLower x]

For example:

> lowers "Haskell"
6

-- needs to be fixed
lowers :: String -> Int
lowers xs =
    length [x | x <- xs, isLower x]

lowers "Haskell"

Exercises

A triple (x,y,z) of positive integers is called pythagorean if \(x^2 + y^2 = z^2\). Using a list comprehension, define a function

pyths :: Int → [(Int,Int,Int)]

that maps an integer n to all such triples with components in [1..n]. For example:

> pyths 5
[(3,4,5),(4,3,5)]

A positive integer is perfect if it equals the sum of all of its factors, excluding the number itself. Using a list comprehension, define a function

perfects :: Int → [Int]

that returns the list of all perfect numbers up to agiven limit. For example:

> perfects 500
[6,28,496]

The scalar product of two lists of integers xs and ys of length n is given by the sum of the products of the corresponding integers:

\[\displaystyle\sum_{i=0}^{n-1}(xs_i\cdot ys_i)\]

Using a list comprehension, define a function that returns the scalar product of two lists.

Recursive functions

Introduction

As we have seen, many functions can naturally be defined in terms of other functions.

factorial :: Int → Int
factorial n = product [1..n]

factorial maps any integer n to the product of the integers between 1 and n.

factorial :: Int -> Int
factorial n = product [1..n]

Expressions are evaluated by a stepwise process of applying functions to their arguments.

For example:

factorial 4
= product [1..4]
= product [1,2,3,4]
= 1*2*3*4
= 24

Recursive functions

In Haskell, functions can also be defined in terms of themselves. Such functions are called recursive.

factorial 0 = 1
factorial n = n * factorial (n-1)

factorial maps 0 to 1, and any other integer to the product of itself and the factorial of its predecessor.

factorial 0 = 1
factorial n = n * factorial (n-1)

For example:

factorial 3
= 3 * factorial 2
= 3 * (2 * factorial 1)
= 3 * (2 * (1 * factorial 0))
= 3 * (2 * (1 * 1))
= 3 * (2 * 1)
= 3 * 2
= 6

Note:

factorial 0 = 1 is appropriate because 1 is the identity for multiplication: 1*x = x = x*1.
The recursive definition diverges on integers < 0 because the base case is never reached:

> factorial (-1)
Exception: stack overflow

factorial (-1)

Why is recursion useful?

Some functions, such as factorial, are simpler to define in terms of other functions.

As we shall see, however, many functions can naturally be defined in terms of themselves.

Properties of functions defined using recursion can be proved using the simple but powerful mathematical technique of induction.

Recursion on Lists

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

product :: [Int] → Int
product []     = 1
product (n:ns) = n * product ns

product maps the empty list to 1, and any non-empty list to its head multiplied by the product of its tail.

product :: [Int] -> Int
product []     = 1
product (n:ns) = n * product ns

For example:

product [2,3,4]
= 2 * product [3,4]
= 2 * (3 * product [4])
= 2 * (3 * (4 * product []))
= 2 * (3 * (4 * 1))
= 24

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

length :: [a] → Int
length []     = 0
length (_:xs) = 1 + length xs

length maps the empty list to 0, and any non-empty list to the successor of the length of its tail.

length :: [a] -> Int
length []     = 0
length (_:xs) = 1 + length xs

For example:

length [1,2,3]
= 1 + length [2,3]
= 1 + (1 + length [3])
= 1 + (1 + (1 + length []))
= 1 + (1 + (1 + 0))
= 3

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

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

reverse maps the empty list to the empty list, and any non-empty list to the reverse of its tail appended to its head.

reverse :: [a] -> [a]
reverse []     = []
reverse (x:xs) = reverse xs ++ [x]

For example:

reverse [1,2,3]
= reverse [2,3] ++ [1]
= (reverse [3] ++ [2]) ++ [1]
= ((reverse [] ++ [3]) ++ [2]) ++ [1]
= (([] ++ [3]) ++ [2]) ++ [1]
= [3,2,1]

Multiple arguments

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

Zipping the elements of two lists:

zip :: [a] → [b] → [(a,b)]
zip []     _      = []
zip _      []     = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys

zip :: [a] -> [b] -> [(a,b)]
zip []     _      = []
zip _      []     = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys

Remove the first n elements from a list:

drop :: Int → [a] → [a]
drop 0 xs     = xs
drop _ []     = []
drop n (_:xs) = drop (n-1) xs

Appending two lists:

(++) :: [a] → [a] → [a]
[]     ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

drop :: Int -> [a] -> [a]
drop 0 xs     = xs
drop _ []     = []
drop n (_:xs) = drop (n-1) xs

(++) :: [a] -> [a] -> [a]
[]     ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

Quicksort

The quicksort algorithm for sorting a list of integers 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:

qsort :: [Int] → [Int]
qsort []     = []
qsort (x:xs) =
    qsort smaller ++ [x] ++ qsort larger
    where
        smaller = [a | a ← xs, a ≤ x]
        larger  = [b | b ← xs, b > x]

Note:

This is probably the simplest implementation of quicksort in any programming language, as shown below and in Figure 1.

⊕ <a name='figure1'>Figure 1</a>. Quicksort with Haskell (abbreviating qsort as q): the first element in the list, 3, is set as the pivot, with the elements of the list less than the pivot sorted in the left subtree, and the elements of the list greater than the pivot sorted in the right subtree.
Figure 1. Quicksort with Haskell (abbreviating qsort as q): the first element in the list, 3, is set as the pivot, with the elements of the list less than the pivot sorted in the left subtree, and the elements of the list greater than the pivot sorted in the right subtree.

qsort :: [Int] -> [Int]
qsort []     = []
qsort (x:xs) =
    qsort smaller ++ [x] ++ qsort larger
    where
        smaller = [a | a <- xs, a <= x]
        larger  = [b | b <- xs, b > x]

Exercises

Without looking at the standard prelude, define the following library functions using recursion:

Decide if all logical values in a list are true:

 and :: [Bool] → Bool

Concatenate a list of lists:

 concat :: [[a]] → [a]

Produce a list with n identical elements:

 replicate :: Int → a → [a]

Select the nth element of a list:

 (!!) :: [a] → Int → a

Decide if a value is an element of a list:

 elem :: Eq a ⇒ a → [a] → Bool

Define a recursive function

merge :: [Int] → [Int] → [Int]

that merges two sorted lists of integers to give a single sorted list. For example:

> merge [2,5,6] [1,3,4]
[1,2,3,4,5,6]

Define a recursive function

msort :: [Int] → [Int]

that implements merge sort, which can be specified by the following two rules:

Lists of length ≤ 1 are already sorted;
Other lists can be sorted by sorting the two halves and merging the resulting lists.

Back to course home