The functions we defined so far were restricted to elementary operations, such as incrementing a number. In this chapter, we will discuss some slightly more advanced functions and survey elementary operations on lists.
Usually, a program consists of a large number of function and type definitions. Obviously, putting them all into one single file is a bad idea. Modern programming languages therefore provide some means to structure the program by allowing to group related definitions into logical units which are stored in separate files. In Haskell, these units are called modules.
Let us have a look at the definition of a Haskell module, called Simple:
-- Example module
-- Gabriele Keller, August 2015
--
-- This is a simple example of a module definition
module Simple
where
-- calculates the arithmetic mean of two numbers
--
arithmetic_mean :: Fractional a => a -> a -> a
arithmetic_mean x y = (x + y) / 2
-- calculates the harmonic mean of two numbers
--
harmonic_mean :: Fractional a => a -> a -> a
harmonic_mean x y = 2 * x * y / (x + y)The module begins with a header: a comment containing a one line description of the module, the author and date of creation, and briefly describes the purpose of the module.1
The first line of code starts with the keyword module, followed by the name of the module, the keyword where, and the definitions that belong to the module. Note that a module name, in contrast to function or variable names must start with an uppercase letter.
In Haskell, there is a special module called Prelude whose contents is always available. The module Prelude contains all the functions that are pre-defined in Haskell, such as +, length, and so on.
For now, as we are starting with simple, short programs, we will add all function definitions of a program to a single module. Later we will learn how we can structure more complex programs using multiple modules. In fact, this is a central topic in software development, and modules play an essential role in structuring large software systems.
So far, each of our functions has unconditionally performed one specific computation. In general, this is too limiting; so, next, we will look at the role of conditionals in Haskell programs.
Choice by way of conditionals. How can we implement a function max which returns the greater of its two arguments? That is, the expressions max 5 2 and max 2 5 both evaluate to 5, max 1 7 to 7, and so on. For two arbitrary numbers x and y, we want max x y to return x if x >= y; otherwise, it should return y.2
We can generally compare values with types that belong to the type class Ord, which we discussed in First Steps; hence, the type of max is
max :: Ord a => a -> a -> aThis can be expressed in Haskell by a so-called conditional or if-then-else expression of the form
if ⟨condition⟩ then ⟨value if true⟩ else ⟨value if false⟩
Now, we can implement max:
max :: Ord a => a -> a -> a
max x y = if x >= y then x else yLet’s look at the evaluation of max 5 2:
max 5 2⇒if 5 >= 2 then 5 else 2⇒if True then 5 else 2⇒5
Conditionals are an essential component of programming, because they allow us to dynamically choose between different computations depending on the values of the inputs. Here is another example:
signum :: (Ord a, Num a) => a -> Int
signum x = if x < 0 then -1 else if x == 0 then 0 else 1A note about the type of signum: the type of the argument x has to be both in Ord, as we use the function < and ==, but also in Num, otherwise we would not be able to compare it to 0, which is in type class Num. We will cover type classes in more depth in a later chapter.
Guards. Cascading conditional expressions —as in the previous definition of signum— are difficult to read; therefore, some programming languages, including Haskell, provide an alternative syntax:
signum :: (Ord a, Num a) => a -> Int
signum x | x < 0 = -1
| x == 0 = 0
| x > 0 = 1The guards are checked in the order they are listed. For example, if we apply signum to the number 7, then the system first checks if the argument is less than zero. As this is not the case, it checks whether it is equal to zero, before finally the last guard succeeds:
signum 7⇒1
on the basis of the following three side computations evaluating the guards
7 < 0⇒False
7 == 0⇒False
7 > 0⇒True
Usually, the last guard should catch all the cases not covered before. For this purpose, we can use the special guard otherwise, which always evaluates to True:
signum :: (Ord a, Num a) => a -> Int
signum x | x < 0 = -1
| x == 0 = 0
| otherwise = 1Finally, we can rephrase the definition of max using guards:
max :: Ord a => a -> a -> a
max x y | x >= y = x
| otherwise = yWhich to choose is often a matter of personal style; however, idiomatic Haskell tends to favour code using guards.
The following screencast illustrates the use of conditionals and guards in Haskell for Mac.
A binder binds a value to a name. The value can subsequently be referred to by that name. For example, the Prelude definition
pi :: Floating a => a
pi = 3.141592653589793allows us to just write pi instead of spelling out 3.141592653589793. The type class Floating contains the types Float and Double (i.e., single and double precision floating point numbers).
We may use a previously introduced name in another function definition:
circleArea :: Floating a => a -> a
circleArea radius = pi * radius * radiusSometimes, we need to introduce a new name, which will only be used within a function. In that case, we should use a local binding. For example,
circleArea' :: Floating a => a -> a
circleArea' diameter = pi * radius * radius
where
radius = diameter / 2.0 -- local bindingThe evaluation of this function proceeds as follows:
circleArea' 6.0⇒pi * radius * radius where radius = 6.0 / 2.0⇒
pi * radius * radius where radius = 3.0⇒
pi * 3.0 * 3.0⇒
pi * 9.0⇒
3.141592653589793 * 9.0⇒
28.2743
So far, we have seen how to pass multiple values to a function, but not how a function can return more than one result value. We can achieve this by using tuples:
addMul :: Num a => a -> a -> (a, a)
addMul x y = (x + y, x * y)A tuple combines multiple components (two integer values, in the above example) into one compound value. The compound value can be manipulated as a single entity and, in particular, be returned as a value from a function.
However, the construction of a compound value is only half of the story. We also need a method for decomposing such values. We achieve this by using a notation dual to that of tuple construction:3
fst (x, y) = x
snd (x, y) = yIn the argument of fst, we do not use a variable to refer to the compound argument as a whole. Instead, we decompose the pair into its components x and y — this is also called decomposition by pattern matching. The combined use of addMul and fst behaves as follows:
fst (addMul 5 6)⇒fst (5 + 6, 5 * 6)⇒
fst (11, 30)⇒
11
The types of fst and snd. So far, we omitted the type annotations from the definitions of fst and snd. Generally, the Haskell system will automatically infer the types of definitions that lack a signature — however, it is good style to explicitly provide signatures. In all our previous definitions, the type was determined by the operations we applied to the arguments. For example max was restricted to work on types which are members of the type class Ord, since we needed the operator >=, which can only compare certain types of values. The functions fst and snd are different, though. We don’t actually apply any function or operation to x or y, so they could be values of any type. In fact, x and y don’t even have to have the same type. Hence, we can just use type variables to represent the types of x and y without having to add any type class restrictions:
fst :: (a, b) -> a
fst (x, y) = x
snd :: (a, b) -> b
snd (x, y) = yFunctions like fst and snd, which can handle arguments of any type are called (parametric) polymorphic functions.
Example: points. Tuples are not just useful to return multiple results, but also for the representation of data items that cannot be modeled by one primitive value alone. A useful example is given by the points in a 2-dimensional Cartesian coordinate system: they can be represented by a pair of integer values. To avoid having to write the less informative (Int, Int) whenever we denote the type of a point, we can introduce a new type name — similar to the introduction of names for repeatedly used values, which we discussed earlier:
type Point = (Int, Int)With this definition, we define some simple operations on points:
-- origin of the coordinate system
--
origin :: Point
origin = (0, 0)
-- move a given point to the right
--
moveRight :: Point -> Int -> Point
moveRight (x, y) distance = (x + distance, y)
-- move a given point to upwards
--
moveUp :: Point -> Int -> Point
moveUp (x, y) distance = (x, y + distance)Example: colour points. When we extend points to include a colour, another important property of tuples becomes obvious: tuple components may be of different types. Hence, if we denote colour values with a textual (string) representation, we have
-- we represent colours by strings
--
type Colour = String
-- new name for the type of colour points
--
type ColourPoint = (Int, Int, Colour)which enables the following operations on colour points:
-- origin of the coordinate system in a given colour
--
origin :: Colour -> ColourPoint
origin colour = (0, 0, colour)
-- move a colour point vertically and horizontally
--
move :: ColourPoint -> Int -> Int -> ColourPoint
move (x, y, colour) xDistance yDistance
= (x + xDistance, y + yDistance, colour)
-- compute the distance between two colour points
--
distance :: ColourPoint -> ColourPoint -> Float
distance (x1, y1, colour1) (x2, y2, colour2)
= sqrt (fromIntegral (dx * dx + dy * dy))
where
dx = x2 - x1
dy = y2 - y1Note how we use a where clause in the last definition to avoid repeating the expressions x2 - x1 and y2 - y1. The standard function fromIntegral converts any integral type to any other numeric type. Its signature is
fromIntegral :: (Integral a, Num b) => a -> bImportant symmetries in Haskell. If we compare the syntax of values and types of tuples, we see that they correspond. For example, consider
(10, 15, "green") :: (Int, Int, String)
If we replace the values 10, 15, and "green" with their respective types Int, Int, and String, we obtain the type of the tuple. Moreover, we have a correspondence between term construction and term decomposition (also called pattern matching). Consider,
startPoint = (0, 0, "black")
colourOfPoint (x, y, colour) = colourIf we replace the components in the tuple construction (0, 0, and "black") by variable names (in this case x, y, colour), we arrive at the pattern that can be used to decompose the corresponding tuple.
Special names for some tuples.
The following table lists a number of tuple types and their names:
# Expression Name 0 ()Unit 1 n/a n/a 2 (x_1, x_2)Pair 3 (x_1, x_2, x_3)Triple 4 (x_1, x_2, x_3, x_4)Quadruple 5 (x_1, x_2, x_3, x_4, x_5)Quintuple ⋮ n (x_1, …, x_n)n-tuple
Tuples provide the ability to bring together a fixed number of values of varying type. However, many applications, in addition, require the ability to manipulate compound types that may contain a varying number of elements of a single type. This is what lists are for.
We can create lists in a manner similar to pairs, by listing all components, separated by comma. The only difference is that we enclose these values in square brackets:
firstTenPrimes :: [Int]
firstTenPrimes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 27]Lists are a central data structure in Haskell, and the language offers a lot of convenient short cuts. We don’t need to explicitly write every single element if our list elements are just a sequence of consecutive numbers — or in fact, any type whose values can be enumerated:
oneToTwenty :: [Int]
oneToTwenty = [1..20]where
oneToTwenty⇒[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
If the elements follow a simple pattern of the form [n, n + k, n + 2*k, n + 3*k ....,m] we simply write the first two numbers and the last one, and the compiler will figure out what the elements are:
-- return all positive odd numbers up to maxNumber
oddNumbers :: Int -> [Int]
oddNumbers maxNumber = [1, 3..maxNumber]The length of the list returned by this function depends on the argument, unlike with the earlier addMul, where only the value, but not the number of values, depended on the input. For example, we have
oddNumbers 10⇒[1, 3, 5, 7, 9]
oddNumbers 15⇒[1, 3, 5, 7, 9, 11, 13, 15]
The difference between tuples and lists can be seen by comparing their types, as in
(1, 2, "green") :: (Int, Int, String)and
[1, 2, 3, 4] :: [Int]The number of components is explicit in the type of a tuple, but not in the type of a list. As a consequence, the elements of tuples may be heterogeneous, whereas those of lists must be homogeneous.
Adding elements to the front of a list. The right-associative operator (:) adds another element to the front of an existing list:
(:) :: a -> [a] -> [a]For example, we have
"blue" : []⇒["blue"]
"yellow" : ["red", "green", "blue"]⇒
["yellow", "red", "green", "blue"]
"yellow" : "red" : "green" :"blue" : []⇒
["yellow", "red", "green", "blue"]
The operator (pronounced cons) can only add elements at the front. So,
["red", "green", "blue"] : "yellow"⇒ Error!
The cons-operator is another example of a polymorphic function, as it works on lists of any type. The only restriction is that the element we are adding is of the same type as the elements of the list we pass as the second argument:
(:) :: a -> [a] -> [a]Joining two lists. We can join two lists together using the operator
(++) :: [a] -> [a] -> [a]Just as the cons operator, it works on lists of any type, as long as the two lists have the same type of elements:
[4, 2, 3] ++ [3, 1, 2, 7]⇒[4, 2, 3, 3, 1, 2, 7]
[True] ++ [False, True]⇒[True, False, True]
You may remember this operator from the previous chapter, where we used it to join two strings to define
exclaim :: String -> String
exclaim sentence = sentence ++ "!"This works, because strings are simply lists of characters in Haskell.
Extract the element at a specific index position out of a list. We can index into a list and extract an element using
(!!) :: [a] -> Int -> aOn lists of ints
[0, 1, 2, 3] !! 2⇒2
or strings (lists of characters)
"Hello" !! 4⇒'o'
As you can see, the index count starts at 0. If we apply the index operation to an index which is out of range for the given list, evaluation will raise an exception and we get an error message.
Split a list into its first element and the rest.
head :: [a] -> a
tail :: [a] -> [a] Both functions require the input list to be non-empty, and if they are applied to an empty list, we get a runtime error.
head [0, 1, 2, 3]⇒0
tail [0, 1, 2, 3]⇒[1, 2, 3]
head "mouse"⇒'m'
tail "mouse"⇒"ouse"
Length of a list.
length :: [a] -> IntFor example, we have
length [0, 1, 2, 3]⇒4
Check if an item is contained in a list. We can check if an item is element of a given list if its type is in the class Eq. This restriction is necessary because the implementation of this function needs to compare the items for equality.
elem :: Eq a => a -> [a] -> BoolFor example, we have
elem 2 [0, 1, 2, 3]⇒True
elem 5 [1, 2, 3, 4]⇒False
elem 'o' "Hello"⇒True
Add up or multiply the elements of a list. We can calculate the maximum, minumum, sum, or the product of all the elements of a list with these two functions.
maximum :: Ord a => [a] -> a
minimum :: Ord a => [a] -> a
sum :: Num a => [a] -> a
product :: Num a => [a] -> aFor example, we get
sum [0, 1, 2, 3]⇒0 + 1 + 2 + 3⇒6
product [1, 2, 3, 4]⇒1 * 2 * 3 * 4⇒24
Given these functions, how can we add "yellow" at the end of ["red", "green", "blue"]? We can’t use : (cons), since it can only add elements at the start of a list. We need to use ++ as follows:
["red", "green", "blue"] ++ ["yellow"]Note the list constructing brackets around "yellow:". In effect, we wrap "yellow" into a singleton list, which we then append to the list ["red", "green", "blue"].
The following screencast illustrates list processing by way of a few examples, each of which highlights some of the functions that we just discussed.
As lists and tuples are often confused, let us summarise the differences between them. Tuples have the following properties:
Fixed size, i.e., fixed number of components: the pair (1, 2) :: (Int, Int) and the triple (1, 2, 3) :: (Int, Int, Int) have different types.
Components may be of different type: (5, Hello) makes perfect sense.
In contrast, the following are the properties of lists:
Variable size, i.e., number of components may vary: [1, 2] :: [Int] and [1, 2, 3] :: [Int] have the same types.
Components must be of the same type: [5, Hello] is incorrect.
Strings are in fact a particular form of lists in Haskell, which are defined as follows in the Prelude:
type String = [Char]Hence, list operations work on strings. "Hello" !! 1 ⇒ 'e' In fact, in Haskell, "Hello" is exactly the same as ['H', 'e', 'l', 'l', 'o']. This is very convenient, as we will see that there are many powerful list processing operations and these are directly available for string manipulation.
Hence, if we ask the Haskell system for the type of an expression that produces a list, it may report the type as either String or as [Char]. As these two types have been deemed equal by the above type definition, they may be used interchangeably
Some list functions, such as length, may be applied to any list and always produce a meaningful result. In contrast, some other functions, such as head and tail, fail for some lists. For example, if we apply head to an empty list, we get a runtime error or runtime exception.
head []⇒ ** Exception: Prelude.head: empty list
The function head is defined by pattern matching using the same symmetry between list construction and list pattern matching as we discussed previously for tuples — i.e., it matches on the cons-operator (:):
head :: [a] -> a
head (x:xs) = xWhen head gets applied to the empty list, there is simply no function equation that matches this case. We call such functions partial functions. Their definition ignores —or is invalid for— some of the input values admitted by the function's type signature. We discussed that types represent sets of related values; hence, partial functions are functions that are only defined for a subset of the values included in their argument types. The opposite are total functions. Total functions, such as length, are defined for all values included in the sets represented by their argument types.
Partial functions are a common source of programming mistakes. Hence, good style dictates that the documentation of a partial function (e.g., as a comment preceding the function definition) includes a statement specifying the range of admissible input values (and specifies what happens if the function is incorrectly called with an argument that is outside of this range).
The Haskell Prelude includes the function
error :: String -> athat always results in a runtime error using its argument as the error message — that is, we have
error "encountered a fatal error"⇒ ** Exception: encountered a fatal error
We can use error to customise the error message of a partial function. For example, the complete definition of head in the Haskell Prelude reads as follows:
head :: [a] -> a
head (x:_) = x
head [] = error "Prelude.head: empty list"This is better than the default error message generated by the Haskell compiler, which includes the location of the failing function definition, but doesn't specify the argument value that led to the failure.
Note the use of the underscore _ as the second argument of the cons-operator in the first equation. It represents a pattern matching position whose value is not used in the body of the function definition. It is better style than using a regular variable name, such as xs, as it immediately signals that the corresponding value goes unused. Instead of a plain underscore, we can also use variable names starting with an underscore character (here, for example _xs) to indicate that the value is not used.
Unlike in many other programming languages, formatting matters in Haskell. In other words, the correct use of indentation and newlines is crucial to avoid errors. This allows the language to do away with some of the noise that is introduced by some other languages to disambiguate the input — in particular, Haskell programs don’t need curly braces or semicolon to delimit blocks and statements.
Compare
foo x
= a + b
where
a = 1 + x
b = 2to
foo x
= a + b
where
a = 1 + x
b = 2Both are legal programs. However, in the first one, the definition of b is part of the where binding and therefore local to foo whereas in the second program, the use of b is not restricted to foo.
An example of proper layout is the function distance that we discussed earlier:
distance :: ColourPoint -> ColourPoint -> Float
distance (x1, y1, colour1) (x2, y2, colour2)
= sqrt (fromIntegral (dx * dx + dy * dy))
where
dx = x2 - x1
dy = y2 - y1There are three layout rules that we have to follow to get syntactically correct programs:
All program code that belongs to a function definition has to be further to the right than the first character of that definition (i.e., the first character of the function name). In the case of distance, all code has to be further to the right than the column in which the character d of the function name distance is located.
Similarly, all code of a local definition in a where clause must be further to the right than the first character of the name of the variable defined by the binding.
All definitions within a where clause must be aligned — e.g., above the definitions of dx and dy start in the same column.
Alternatively, we can explicitly group the bindings of a where clause using curly braces, and separate the individual bindings by semicolons:
distance (x1, y1, colour1) (x2, y2, colour2)
= sqrt (fromIntegral (dx * dx + dy * dy))
where {dx = x2 - x1; dy = y2 - y1}Inside the curly braces, we can format the code anyway we like, because the compiler can still figure out what belongs where. Nevertheless, while the following program is legal
distance (x1, y1, colour1) (x2, y2, colour2)
= sqrt (fromIntegral (dx * dx + dy * dy)) where {dx
= x2 -
x1; dy = y2 - y1}it is hard to read and clearly pretty bad style. Seasoned Haskell programmers who prefer explicit bracketing align the braces and the semicolons at the beginning of each line (which looks rather strange to, say, a C-programmer, who is used to having semicolons at the end of the line):
distance (x1, y1, colour1) (x2, y2, colour2)
= sqrt (fromIntegral (dx * dx + dy * dy))
where
{ dx = x2 - x1
; dy = y2 - y1
}The following screencast illustrates proper layout and the ways in which layout can go wrong.
Write a function sort2 :: Ord a => a -> a -> (a, a) which accepts two Int values as arguments and returns them as a sorted pair, so that sort2 5 3 is equal to (3,5). How can you define the function using a conditional, how can you do it using guards?
Consider a function
almostEqual :: Eq a => (a, a) -> (a, a) -> Boolwhich compares the values of two pairs. It returns True if both pairs contain the same values, regardless of the order. For example, almostEqual (3,4) (4,3) is True, but almostEqual (3,4) (3,5) is False. Which of the following definitions return the correct value? Which of the definitions would you consider good style? Why?
(The operator (&&) is logical ”and”, the operator (||) is logical ’or’, and (==) tests if two values are equal. The first two are of type Bool -> Bool -> Bool; the third is of type Eq a => a -> a -> Bool.)
almostEqual (x1, y1) (x2, y2)
| (x1 == x2) && (y1 == y2) = True
| (x1 == y2) && (y1 == x2) = True
| otherwise = False
almostEqual (x1, y1) (x2, y2)
| (x1 == x2) = (y1 == y2)
| (x1 == y2) = (y1 == x2)
| otherwise = False
almostEqual pair1 pair2
= (pair1 == pair2) || (swap pair1 == pair2)
where
swap (x,y) = (y,x)
almostEqual pair1 pair2
= (pair1 == pair2) || (swap pair1 == swap pair2)
where
swap (x,y) = (y,x)
almostEqual (x1, y1) (x2, y2)
= if (x1 == x2)
then
if (y1 == y2)
then True
else False
else
if (x1 == y2)
then
if (x2 == y1)
then True
else False
else FalseDefine a function isLower :: Char -> Bool which returns True if a given character is a lower case letter. You can use the fact that characters are ordered, and for all lower case letters ch we have ′a′ ≤ ch and ch ≤ ′z′. Alternatively, you can use the fact that ['a'..'z'] evaluates to a list containing all lower case letters.
Write a function mangle :: String -> String which removes the first letter of a word and attaches it at the end. If the string is empty, mangle should simply return an empty string:
mangle "Hello"⇒"elloH"
mangle "I"⇒"I"
mangle ""⇒""
Implement division on Int, divide :: Int -> Int -> Int using the list functions described in this section. Hint: first, write a function that returns all the multiples of a given number up to a specific limit.
divide 5 10⇒2
divide 5 8⇒1
divide 3 10⇒3
The header is optional in that the compiler will not raise an error if it is missing.↩
The function max, as well as signum discussed later, are already defined in the Prelude; so, if we want to define these functions ourselves, we need to add the line import Prelude hiding (max, signum) right after the module header to hide the standard definitions.↩
Both fst and snd are already defined in the Prelude.↩