# Fundamentals

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.

## Programs are Composed from Modules

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.

## Branches in the Control Flow

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 -> a``

This 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 y``````

Let’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 1``````

A 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  = 1``````

The 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  = 1``````

Finally, we can rephrase the definition of `max` using guards:

``````max :: Ord a => a -> a -> a
max x y | x >= y     = x
| otherwise  = y``````

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

## Binders — Associating Names with Values or Functions

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.141592653589793``````

allows 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

Sometimes, 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
where
radius = diameter / 2.0       -- local binding``````

The 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`

## Tuples: Combining Different Data Items

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)  = y``````

In 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)  = y``````

Functions 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 - y1``````

Note 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 -> b``

Important 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) = colour``````

If 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

## Lists: Many Values of a Single Type

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.

### Useful functions on lists

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 -> a``

On 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] -> Int``

For 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] -> Bool``

For 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] -> a``````

For 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"]`.

### Let's look at some of concrete examples

The following screencast illustrates list processing by way of a few examples, each of which highlights some of the functions that we just discussed.

### Lists versus tuples

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 as lists

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

## Partial Functions

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

When `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 -> a``

that 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

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.

## Layout

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 = 2``````

to

``````foo x
= a + b
where
a = 1 + x
b = 2``````

Both 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 - y1``````

There are three layout rules that we have to follow to get syntactically correct programs:

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

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

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

## Exercises

1. 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?

2. Consider a function

``almostEqual :: Eq a => (a, a) -> (a, a) -> Bool``

which 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 False``````
3. Define 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.

4. 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 ""`   ⇒   `""`

5. 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`

1. The header is optional in that the compiler will not raise an error if it is missing.

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

3. Both `fst` and `snd` are already defined in the `Prelude`.