This is the second module (out of 5) of my English summary of the Haskell MOOC on Stepik, available only in Russian. Read the first part in the *Introduction* module.

- Introduction
**Programming fundamentals**(this page)- Lists
- Data types
- Monads

## Programming fundamentals

### Parametric polymorphism

A function is said to be *polymorphic* if it can be used on values of different types. For example, the `+`

operator may be used on values of type `Int`

, returning an `Int`

value, or `Double`

values, returning a `Double`

. This makes `+`

a polymorphic operator.

There are two kinds of polymorphism: *parametric polymorphism* and *ad hoc polymorphism*. The former means that the function implementation is identical for all types which this function can be used with, the latter implies that for each type used with this function, there exists a special implementation, specific to the type. Examples above, for using the `+`

operator with `Int`

and `Double`

types is an example of ad hoc polymorphism, since the implementation of addition for those types behaves differently.

#### Polymorphic functions

The simplest example of a polymorphic function is `id`

(which exists in the standard library), which returns its argument:

> id x = x |

This function’s type is `t -> t`

. Here, `t`

is called a *type variable*, meaning it can be applied to any arbitrary type. In Haskell, concrete types (such as `Integer`

) start with a capital letter, and type variables start with a lowercase letter.

This function is parametrically polymorphic since there are no further restrictions on the input parameter - it is returned unchanged from the function. We can call this function on values of arbitrary types:

> id True |

We can also call `id`

on the function `id`

itself. The result is the function `id`

itself, which can be further applied to any value:

> (id id) 4 |

The type of a fully applied polymorphic function, e.g. `id True`

, is a `Bool`

type:

> :t id True |

What is the type of `(id id)`

? The function itself is passed as an argument, making the return type the same type as the argument, namely `t -> t`

:

> :t (id id) |

Let’s define a two-argument function `k`

with parameters `x`

and `y`

. Not knowing anything about `x`

and `y`

, so the only thing we can do here is to return either `x`

or `y`

. Let’s return `x`

:

> k x y = x |

We’ll get a function that always ignores its second argument, always returning the first:

> k 42 True |

The type of our function `k`

is:

> :t k |

Here we see the use of type variables `t1`

and `t`

, meaning that the actual types are not important, `t1`

and `t`

could be different types. The return value is the first argument `t1`

. This function already exists in the standard library, and it’s called `const`

. The `const`

function always returns its first argument, ignoring the second. Here’s the signature of `const`

:

> :t const |

This type is using different names for its type variables, but it is identical to our `k`

function.

If we partially apply `const`

to one argument, e.g. `const True`

, its type is:

> :t const True |

This partially-applied `const`

can accept any arbitrary value, ignore it, and will always return a `Bool`

value, namely `True`

.

In the previous module, we talked about the `error`

and `undefined`

functions, which immediately halt the execution, printing an error message:

> undefined |

The type of `undefined`

is also parametrically polymorphic:

> :t undefined |

The `undefined`

function has a type variable `a`

, which means it can be substituted for any type. It can be written anywhere an arbitrary type is expected, and it will still be correctly type-checked. The `error`

function, when given an error message, also inhabits all types:

> :t error "boom |

The `undefined`

and `error`

functions in Haskell halt program execution, which is why it’s possible to define them using the highest (unconstrained) level of polymorphism, namely an arbitrary type parameter. Without any additional context, it’s impossible to create a value of type `a`

, so the only thing these functions can do is either hang forever or terminate with an error message. Those functions are called *bottom* values and denoted with a mathematical symbol ⊥.

#### Most general type

We can limit function polymorphism by explicitly specifying its type. Consider an example:

mono :: Char -> Char |

The implementation of the `mono`

function above does not differ from the implementation of `id`

, however, we specified that it can only be applied to values of type `Char`

. Calling it with a `Char`

value will return the value, otherwise, it will cause an error:

> mono 'x' |

A function that operates on concrete types is called a *monomorphic* function.

We can partially limit polymorphism, demonstrated by the function `semiMono`

. It is a two-argument function, with an arbitrary second parameter.

If we do not explicitly specify the function type, Haskell will infer the *most general type* available for the function. If we comment out the `semiMono :: Char -> a -> Char`

declaration above, Haskell will infer the following type for `semiMono`

:

> :t semiMono |

The type inference algorithm that Haskell uses is based on the Hindley-Damas-Milner algorithm. This algorithm infers the most general type for any given expression. If an expression has no further restrictions, Haskell infers a generic type variable, otherwise, it will infer a monomorphised type parameter, such as `Char`

in the example above.

#### Higher-order functions

A *higher-order function* is a function that takes another function as an argument. In Haskell and other functional languages, higher-order functions are used pervasively. We’ve already encountered one such function, the `$`

operator, the low-precedence function application operator.

Let’s look at the type of the `$`

operator:

> :t ($) |

It is a polymorphic type, a function of two arguments. Its first argument (left) is a function, the second argument (right) is a value of an arbitrary type. The `$`

operator applies its left argument to the right. This requires the types to match - the type of the right argument `a`

must match the type of the input parameter of the left argument `a -> b`

. The result of the `$`

operator is the result of the left argument function. Since the result of `a -> b`

is the type `b`

, it is the resulting type of applying `$`

operator.

Let’s look at another example. Suppose the function `apply2`

which applies the function twice:

> apply2 f x = f (f x) |

What is the type of this expression? If we look at the above definition of `f`

, it’s a function from `a -> b`

. The inner `(f x)`

, therefore, results in a type `b`

. But now the outer function `f`

is applied to the result of `(f x)`

, which is `b`

, however, it expects `a -> b`

? How can this be, if this function compiles just fine?

Since both types `a`

and `b`

of our function `f :: a -> b`

are completely arbitrary, the type checker can infer that in this case, the types `a`

and `b`

are the same. Applying a function `a -> b`

on a value of type `b`

only works if `a`

and `b`

are the same type.

The Haskell compiler understands this, and it’s able to monomorphise the function to the following signature:

> :t apply2 |

Making the first argument, `f`

, a function where the input and output types are the same. The second argument, `x`

is a value of the same type, which is also the return type of the `apply2`

function. This means our `apply2`

function can be used on fewer types of values than `$`

.

> apply2 (+5) 22 |

Here we see the function `apply2`

used with values of the same type: the first applies the function `(+5)`

twice to the integer 22, and the second appends the string “AB” twice to the string “CD”.

Now let’s look at a more useful function from the standard library, `flip`

:

flip f y x = f x y |

This function has 3 parameters: the function `f`

, and two additional parameters `y`

and `x`

. It ends up applying the function `f`

to the parameters in the reversed order, flipping between `y`

and `x`

. Here’s an example using division:

> (/) 4 2 |

Here, because `flip`

switches the order of parameters, we get `2 / 4`

instead of `4 / 2`

, resulting in 0.5.

Let’s see what happens when `flip`

is applied to the function `const`

. As you may recall, the `const`

function always returns the first argument, ignoring the second. By flipping the arguments, `flip const`

is now a function that always returns the second argument, ignoring the first!

> flip const 5 True |

The `flip`

function has the following type:

> :t flip |

Recall that in Haskell, any function can be considered a function of one argument, returning another function. In this case we can see that `flip`

is a function that accepts a two-argument function `(a -> b -> c)`

and returns a function `(b -> a -> c)`

with the arguments reversed.

We can see from the type of `flip const`

that it takes two arguments, and always returns the second:

> :t flip const |

#### Anonymous functions - Lambda

In Haskell, similar to mathematics, functions have names, and we apply the function by calling its name. However, there’s an alternative - *anonymous functions*. Consider the expression:

2 * x + 7 |

This expression contains an unknown variable `x`

, and cannot be used in this form as a bound expression:

> 2 * x + 7 |

To compute the expression for any given `x`

we usually resort to declaring a function that takes an `x`

as an argument:

> f x = 2 * x + 7 |

Now it’s a regular function that can be applied to any `x`

, e.g.:

> f 10 |

However, instead of creating a named function, we can bind the value `x`

using a *lambda expression*, by using the following syntax:

> \x -> 2 * x + 7 |

We start by writing a backslash symbol (`\`

), followed by the variable `x`

, followed by an arrow `->`

, after which we can refer to `x`

in the body of the expression. The character `\`

was chosen because it visually resembles the Greek letter lambda (λ).

This creates an anonymous function (also called a lambda function or lambda expression), which behaves exactly like the named function `f`

above. We can use this expression to apply it to the same value:

> (\x -> 2 * x + 7) 10 |

We can define another function, `f'`

, binding it to the lambda expression:

> f' = \x -> 2 * x + 7 |

Using those definitions, both `f`

and `f'`

are equivalent.

We can pass multiple arguments to the lambda expression. Consider a function `lenVec`

which calculates vector length:

> lenVec x y = sqrt $ x^2 + y^2 |

We can rewrite this function as a series of lambda expressions, by moving the formal parameters to the right-hand side, turning them into lambda parameters:

> lenVec = \x -> \y -> sqrt $ x^2 + y^2 |

Haskell has a convenient syntactic sugar for specifying lambdas with multiple parameters:

> lenVec = \x y -> sqrt $ x^2 + y^2 |

Anonymous functions are most commonly used when using higher-order functions. Recall that a higher-order function is a function that accepts another function as an argument. Consider the following example:

> p1 = ((1,2), (3,4)) |

Here, `p1`

and `p2`

are pairs of pairs. Let’s write a function that sums the first elements of each pair. To get the first element of the first pair we could use the function `fst`

twice, like so:

> fst $ fst p1 |

Let’s now use it in a function that looks like this:

import Data.Functions |

The `on`

function is defined in the `Data.Functions`

module, and has the following signature:

on :: (b -> b -> c) -> (a -> b) -> a -> a -> c |

It is used to run a binary function `op`

on the results of applying the unary function `f`

to two arguments `x`

and `y`

. It can be used, for example, to define the `sumSquares`

function from the previous module:

sumSquares = (+) `on` (^2) |

The `x`

and `y`

arguments here are omitted. Following the definition of `on`

, substituting the values, we get:

(^2) x + (^2) y |

Our `sumFstFst`

is a function of two arguments. We apply the operator `+`

to the result of applying `helper`

to both arguments:

> sumFstFst p1 p2 |

Visualized as the following:

((+) `on` helper) p1 p2 |

It extracts the first element from `p1`

, which is 1, the first element from `p2`

which is 3, giving us the desired result 4.

This works, but we would like to avoid declaring the named `helper`

function, so we can use a lambda expression instead, omitting the `where`

clause entirely:

sumFstFst' = (+) `on` (\pp -> fst $ fst pp) |

### Parametric polymorphism (2)

Suppose we have two polymorphic functions, `f`

and `g`

. We would like to create a composite function, that takes both functions `f`

and `g`

, and applies them to the argument `x`

in the following manner: first, apply `g`

to `x`

, and then apply `f`

to the result. Let’s look at how we can define such a composition operator.

#### Function composition

Suppose our `f`

and `g`

functions have the following signatures:

f :: b -> c |

Also, we have an argument `x`

of type `a`

:

x :: a |

To apply the function `f`

to the result of applying `g`

, the result type of `g`

must be the same as the input type of `f`

, namely `b`

. The function `g`

accepts an argument of type `a`

:

f (g x) |

This gives us a result of type `c`

, but we want instead to get a composite function from `a -> c`

.

We can achieve this by abstracting over `x`

using a lambda expression:

\x -> f (g x) |

And this gives us the expected result, a function `a -> c`

.

The complete composition function, therefore, can be defined thus:

compose f g = \x -> f (g x) |

This operator already exists in Haskell, and it is called `.`

. Its type is:

> :i (.) |

Which is precisely what we wanted: it takes a function `b -> c`

, another function `a -> b`

, and returns a composite function `a -> c`

.

Note the use of `:i`

(short for `:info`

) in GHCi - it returns additional information about the definition, such as where it is defined and its fixity, if available.

Now let’s look at how we can use this operator. In the previous section, we defined a function `sumFstFst'`

:

sumFstFst = (+) `on` (\pp -> fst $ fst pp) |

In the lambda expression that extracts the first element from a pair of pairs, we used the `fst`

function twice, to first extract the first pair, and then extract the first element from that pair. We are applying the function `fst`

to the result of applying `fst`

to the argument `pp`

, and this is exactly what the composition operator gives us, allowing us to simplify the expression to the following:

sumFstFst'' = (+) `on` (fst . fst) |

The function `(fst . fst)`

is a more compact equivalent of `(\pp -> fst $ fst pp)`

, called the *point-free* style, allowing us to omit the the argument. Chains of function applications can be rewritten to this style:

doIt x = f (g (h x)) == f ((g . h) x) == (f . (g . h)) x |

Allowing us to drop the argument `x`

on both sides, giving us:

doIt = f . g . h |

#### Tuple and list polymorphism

Until now, when talking about parametric polymorphism, we used functions. However, built-in Haskell types, such as tuples and lists are also parametrically polymorphic. Let’s start with a list. Suppose we have a list of `Bool`

values:

> :t [True,False] |

A list in Haskell is written by using square brackets `[]`

, and its type is polymorphic, depending on the type of its elements. Since lists are homogeneous, they can only contain values of the same type.

If we look at the type of an empty list:

> :t [] |

We’ll see that its type is a type variable `a`

, meaning the list is polymorphic in its elements.

This is also apparent from functions that operate on lists, such as the concatenation operator `++`

, taking two lists of the same type and produces another list of the same type:

> :t (++) |

Similar to the `:`

operator that adds an element to the head of the list:

> :t (:) |

Tuples in Haskell are also polymorphic. Let’s recall the syntax of creating a tuple:

> (True,3) |

However, there’s an alternative syntax for creating a tuple. Instead of specifying the values inside the tuple braces, we can use it in a prefix style:

> (,) True 3 |

The first syntax is called a *mixfix* style, where the values are mixed with the tuple structure. The prefix style can be used to create tuples of any length, e.g.:

> (,,) True 3 'c' |

Let’s look at the types of tuple construction operators:

> :t (,) |

The type variables can be substituted for any type. We can also partially-apply the tuple operator, resulting in:

> :t (,,) True 'x' |

We can create a function that turns a single value into a pair, with the value duplicated:

> dup x = (x,x) |

Since there are no constraints on the value `x`

, the Haskell compiler infers a type variable `t`

, meaning that the input and the first and second elements of the resulting pair must be the same type.

The projection functions `fst`

and `snd`

that we encountered earlier have the types:

> :t fst |

Resulting in `fst`

to return the first element `a`

, ignoring the second, and `snd`

does the opposite - returns the second element `b`

, ignoring the first.

#### Currying

In most programming languages, function calls are made by specifying the function name, followed by parentheses, followed by a list of arguments, separated with a comma, e.g. `max(3, 7)`

.

In Haskell, function application is done without any additional punctuation, but by specifying the arguments after the function name with a space between them: `max 3 7`

. Haskell allows us to not specify all the arguments to the function, resulting in a partially-applied function that can later be passed the rest of the arguments.

This technique of turning an *n* argument function into a sequence of functions accepting one argument is called *currying*, named after a logician Haskell Curry, who formalized it after it was discovered by a Russian mathematician Moses Schönfinkel. The Haskell language is named after Haskell Curry.

However, not all functions in Haskell are curried. Functions that operate on tuples bare resemblance to function calls in imperative languages, i.e. `fst (1, 2)`

. To move between curried and uncurried forms, we can use two combinators, `curry`

and `uncurry`

. Let’s look at a few examples:

Recall the function `on`

we learned in the previous section. It takes 4 parameters, the first being a function of two arguments:

> :t on |

In other words, the first expected argument `(b -> b -> c)`

is a *curried* function. If we try to use a function `fst`

as the first argument, we will get a type error, saying the types don’t match - our `fst`

function is the wrong shape - it is an *uncurried* function `(a, b) -> a`

:

> :t fst `on` (^2) |

To turn an uncurried function into a curried one, we can use the `curry`

combinator that does just that:

> :t curry fst |

turning the `fst`

function into the correct shape to use with the `on`

function:

> :t curry fst `on` (^2) |

Let’s define another function `avg`

that averages the values of a pair:

avg :: (Double,Double) -> Double |

This is another example of an uncurried function, and if we want to use it with a higher-order function, such as `on`

, we need to turn it into a curried one, using `curry`

:

> :t curry avg `on` (^2) |

How would we define the `curry`

function ourselves? Let’s define a function `curry'`

with the arguments:

curry' f x y = ... |

The `curry'`

function expects a function `f`

to operate on a tuple. To do this, we need to turn our arguments `x`

and `y`

into a tuple, resulting in:

> curry' f x y = f (x,y) |

Looking at the inferred type signature we can see that it does exactly what is expected:

> :t curry' |

it takes an uncurried function `(a, b) -> c`

, giving us back a curried function `a -> b -> c`

.

This signature matches exactly the definition of `curry`

from the standard library.

The opposite operation is called `uncurry`

, a function that takes a curried function and returns a function that operates on a pair:

> :t uncurry |

### Type classes

In the previous section, we learned about parametric polymorphism. A function is polymorphic if it can be applied to arbitrary types, without any additional restrictions. This section talks about a specialized, *ad hoc polymorphism*. A function can be still applied to arguments of various types, as long as those types provide an implementation of an interface that defines the specialized behavior. This type of interface in Haskell is called a *type class*, and its implementations are called *instances*.

#### Contexts

Numeric constants in Haskell have the following representation:

> :t 7 |

Whenever we encounter a “fat arrow” (sometimes called an *implication*) in the type signature, it splits the type into two parts: on the right-hand side is the type of the expression (in this case we say that 7 has the type `a`

), and on the left-hand side we have a so-called *context*. The context contains two parts: the name of the *interface* that the type must provide an implementation for, and the type parameter for which this interface is defined. In our case, we say that 7 has a polymorphic type `a`

, but this type `a`

must have an implementation for the interface `Num`

.

We will use the terms *type class* instead of “interface”, and *instance* instead of “implementation”.

The type class `Num`

contains a series of operations on numbers, such as *addition*, *multiplication*, and others.

Looking at the definition of the addition operator `+`

:

> :t (+) |

we see that it is also a polymorphic function that takes two arguments of the same type `a`

, returning an argument of type `a`

, provided the type `a`

has an instance of `Num`

(we can also say “belongs to the `Num`

type class”, or “members of the `Num`

type class”).

There are many different type classes, providing various behaviors, such as comparison. The operator `>`

(greater than) has the following definition:

> :t (>) |

It takes two arguments of the same type and returns a boolean value, indicating whether the first argument is greater than the second. The type `a`

must belong to the type class `Ord`

which defines this behavior.

Let’s see what happens when we partially-apply the `>`

operator with a number, e.g.:

> :t (> 7) |

Due to the operator section, `(> 7)`

becomes a unary predicate of type `a -> Bool`

, however, its context has expanded: it is now required that the type `a`

belongs to both `Num`

and `Ord`

type classes - the `Ord`

constraint due to the use of `>`

, and the `Num`

constraint due to the use of a numeric value 7.

A slightly more complicated example is using the operator section on a pair:

> :t (> (1,2)) |

Pairs are also members of the `Ord`

type class if the elements of the pair are members of that type class. Pair elements can be of different types, evident here by the use of `t`

and `t1`

type variables. Both types have constraints of belonging to the `Num`

and `Ord`

type classes.

Now that we know how to read type class constraints, we can tell more about the errors that happen in case Haskell cannot satisfy such constraints. Consider the example:

> :t (* 'c') |

We are trying to use the multiplication operator `*`

with a character value `'c'`

. Here, Haskell reports and error that there are no instances of type class `Num`

(which `*`

requires) for the type `Char`

. We could fix this by defining our own instance of `Num Char`

, providing we could implement such behavior.

#### Type class declaration

A type class provides an interface which can be implemented for concrete types. The type class declaration is a collection of named functions, having certain signatures. Here’s an example:

class Eq a where |

A type class is defined by starting with the keyword `class`

, followed by the name of the type class, followed by the type parameter for which this type class can be defined. After which, the keyword `where`

, followed by the functions the type class instance must implement. The function definitions must start at the next indentation level.

In our case, `Eq`

can be defined for any arbitrary type `a`

. Each instance of `Eq`

will replace `a`

with the concrete type for which it is implemented. The two functions defined in the interface, namely `==`

and `/=`

check for equality and inequality, respectively. Both have the signature `a -> a -> Bool`

.

The `Eq`

type class is already defined in the Haskell standard library. Let’s look at how it is used:

> :t (==) |

The equality operator is a polymorphic function with a constraint that type `a`

must be a member of `Eq`

. This constraint remains as long as the values themselves remain polymorphic. In the expression:

> :t (== 42) |

We can see that operator section, applied to a polymorphic value (recall that numbers in Haskell are polymorphic with a `Num`

constraint), we can see that the `Eq`

requirement remains, but also the `Num`

requirement was added, meaning that the remaining argument must be a member of both `Eq`

and `Num`

type classes.

If we partially apply the operator to a concrete type, e.g. `Char`

:

> :t (== 'x') |

we see that the `Eq`

requirement was removed, as Haskell monomorphised this expression to the concrete `Char`

type.

Let’s now look at a few functions that use the `Eq`

constraint. One such function, `elem`

from the standard library, checks whether the value is an element in a list:

> :t elem |

The arguments to `elem`

is the value we’re checking, as well as the list of those values. It works by equating the value with each element in the list, returning `True`

in case such element was found, otherwise `False`

. In order to perform such an equality check, the type `a`

must be a member of the `Eq`

type class.

Reading type class constraints on type signatures is a powerful reasoning mechanism in Haskell, allowing us to deduce a lot about how a function behaves just from reading the type signature, without looking at the implementation.

#### Type class instances

A type is considered a member of a type class, if there exists an implementation (called *instance*), implementing that type class. Here’s an example:

class Eq a where |

The `Eq`

definition has two functions, checking for equality and inequality. Here we are using a more compact style of writing, as both functions have the same signature, Haskell allows placing them in a single line, separated by commas.

To declare a type class instance, we use the `instance`

keyword, followed by the type class name, followed by the type for which we implement this instance (`Bool`

in this case, causing our function signatures to monomorphise to `Bool -> Bool -> Bool`

). This is followed by the keyword `where`

. The next line (and the next indentation level) defines the implementations of the functions. In this case we use pattern matching to define the first signature, `==`

.

Boolean equality defined such that `True`

is always equal to `True`

, and `False`

is always equal to `False`

. Any other permutation is not equal, denoted here by using a placeholder symbol `_`

, which in Haskell can be read as “in all other cases”. Here it means that the match will always be successful, if the previous two failed, and the result will always be `False`

, regardless of the values that were matched.

The next implementation is the inequality function `/=`

. In this case, we implement it via the equality implementation, negating the result of `==`

with the function `not`

. In such cases, where a function can be implemented in terms of another, it can be defined in the type class definition itself:

class Eq a where |

In such cases, it’s often enough to implement just the functions that don’t already have a default implementation. It is also possible to define cyclic implementations:

class Eq a where |

Since GHC 7.8.1, Type classes may state a *minimal complete definition*, a specification of which minimal set of functions must be implemented by all instances.

#### Polymorphic instances

We can also define type class instances for polymorphic types. For example, an `Eq`

instance for a two element tuple (a pair). Two pairs are equal if their elements are equal. Pair elements themselves must be members of the `Eq`

type class:

instance (Eq a, Eq b) => Eq (a, b) where |

Here we implement an instance for a polymorphic `Eq (a, b)`

, with the additional constraint that `a`

and `b`

themselves must have an instance of `Eq`

, as evident by the declaration `(Eq a, Eq b)`

on the left-hand side of the `=>`

sign, allowing us to use the equality `==`

operator in the expression body. No need to place each part in parentheses, since `==`

has higher precedence than `&&`

.

Similarly, we can define an instance for lists:

instance Eq a => Eq [a] where |

All the definitions above already exist in the standard library, as well as many others, implementing all common base types.

Not all types can be checked for equality. In Haskell, there are functional types for which implementing such equality is not possible. Consider the example:

> id == (\x -> x) |

Even though as implementors we know in this case that those two functions are identical, from theoretical computer science, function equality is said to be *undecidable* in a Turing-complete language, therefore it’s not possible to implement in Haskell. Here, Haskell reports an error that there’s no instance of `Eq`

for a function type `a0 -> a0`

.

### Standard type classes

In this section we’ll talk about *type class extension*. This is similar to extension in object-oriented languages, however in Haskell we are extending the type class interfaces, never implementations.

#### Class extensions

Let’s consider an example of the `Ord`

type class (also exists in the standard library):

class Eq a where |

The `Ord`

type class is parameterized by `a`

and itself has a *context* of `Eq a`

. When placing such context in the type class definition (rather than the instance), it means that the `Ord`

type class *extends* the `Eq`

type class. In order to define an instance of `Ord`

we must first define an instance `Eq`

.

The `Ord`

type class defines the ordering behavior used in comparisons. Other than the usual ordering operators `<`

, `<=`

, `>=`

, and `>`

, we can define the `max`

and `min`

functions, as well as a function `compare`

, which can be used for a more detailed comparison. The `compare`

function returns a result `Ordering`

, which is a type comprised of 3 values: LT, EQ, and GT (less than, equals, and greater than):

Prelude> :i Ordering |

In the minimal complete definition of the `Ord`

type class it is stated that a valid instance can be defined by only implementing either the `compare`

or `<=`

functions.

We can also do a sort of *multiple inheritance*, by specifying several interfaces that extend our type class, e.g.:

class (Eq a, Printable a) => MyClass a where |

Since in Haskell we’re extending the type class interfaces themselves, and not the implementations, problems such as multiple inheritance in object-oriented languages do not occur.

`Show`

and `Read`

The standard library contains a useful type class `Show`

with a function `show`

, which can be used to create a string representation of a value.

First, let’s see how the `show`

function is defined:

> :t show |

It takes any arbitrary type `a`

and returns a String, provided our `a`

is a member of `Show`

:

> show 5 |

If `Show`

performs a sort of a serialization of a value to `String`

, the type class `Read`

performs the opposite operation: it reads an arbitrary `String`

value, and returns a type `a`

, if an instance of `Read`

exists for `a`

:

> :t read |

However, if we attempt to use it as-is, we’ll get the following error:

> read "5" |

(in older versions of GHC this would print a large message about a missing instance `(Read a0)`

)

Why did we get an error?

Our `read`

function is polymorphic in its return type, and here we must explicitly specify the return type of the function. Otherwise, Haskell has no way of knowing whether the string constant `"5"`

is an `Int`

, `Double`

, or something else. To use the `read`

function properly we must specify the return type using the syntax:

> read "5" :: Int |

The `read`

function is not defined in the `Read`

type class, because it has limited usefulness. In case it is unable to parse the input value, it will return an error. Suppose we attempt reading the string “5 rings” as an `Int`

:

> read "5 rings" :: Int |

It will fail, because it won’t be able to read the entire string. For this reason, there exists a function `reads`

, which is a safer version that is able to return unparsed elements as a pair, in addition to the parsed value:

> reads "5 rings" :: [(Int,String)] |

Returning the successful `Int`

value as the first element, and the remainder string as the second element.

`Enum`

and `Bounded`

Many types are considered *enumerations*, as if their values can be listed with a comma. For example, the `Int`

values can be listed as “1,2,3…”. Each element can be less then or greater than its predecessor, and we can move up and down the type by increasing or decreasing the value. Same goes for `Char`

and even `Bool`

- there’s a certain order to the elements, and we can enumerate this order.

The type class that defines such enumeration sequences is called `Enum`

. It defines two functions: a *successor* `succ`

, and a *predecessor* `pred`

. Here’s its definition:

class Enum a where |

The `succ`

and `pred`

function take a value and produce the next or the previous value of the same type. Each value can be considered assigned a number to it, and the functions `toEnum`

and `fromEnum`

can transform the number to a value and vice-versa. These functions, therefore, allow making the values of the type `a`

*enumerable*:

Here are `succ`

and `pred`

applied to `Int`

and `Char`

, respectively:

> succ 4 |

The `toEnum`

and `fromEnum`

operate as follows:

> fromEnum 'z' |

Note that the `toEnum`

is polymorphic in its return type, therefore the type must be explicitly specified.

We’ll cover the `Bounded`

type class next. The `Bounded`

type class specifies the lower and upper bounds, available for a type.

class Bounded a where |

Here are a few examples:

> minBound :: Int |

The only standard type that is a member of `Enum`

, but not a member of `Bounded`

is the `Integer`

type. Trying to get a bound value of an `Integer`

will result in an error:

> maxBound :: Integer |

`Num`

and its extensions

The `Num`

type class defines operations that can be performed on numeric values. It has a rich hierarchy of extensions, specifying more complex numbers and operations.

class Num a where |

The `Num`

type class defines a series of operations that must be implemented. It defines the `+`

, `-`

, and `*`

operations, however, it does not define division `/`

. This is due to the fact that division for whole numbers, and numbers with a floating point are implemented differently. The `Num`

type class has two extensions: the `Integral`

and `Fractional`

type classes, the former defines division for whole numbers, the latter - for floating-point numbers.

In reality, the `Integral`

type class does not extend `Num`

directly, it uses another type class `Real`

, which represents all real numbers.

> :i Integral |

The functions `div`

and `mod`

are responsible for the division operations, `div`

performing integer division, and `mod`

finds the remainder. The function `divMod`

simultaneously applies `div`

and `mod`

, returning the result a a pair. The `MINIMAL`

pragma suggests that a minimal complete definition requires implementing `quoteRem`

and `toInteger`

.

Haskell contains an implementation of `Integral`

for the `Int`

and `Integer`

types, as shown by the output of the `:i`

(`:info`

) command.

The other extension for `Num`

is the `Fractional`

type class:

> :i Fractional |

Here we can see that, among others, the `Fractional`

type class defines the division operation `/`

for floating-point numbers. Haskell includes an instance of this type class for `Float`

and `Double`

.

The `Floating`

type class defines a wide set of operations for floating-point arithmetic:

> :i Floating |

Another extension is the `RealFrac`

type class, which defines rounding operations:

Prelude> :i RealFrac |

There are many more type classes in the `Num`

hierarchy. Detailed documentation is available on Hoogle.

### Non-strict semantics

In imperative languages, instruction order defines the order of execution. In functional languages there are no instructions, so it’s not immediately obvious how to define an execution order of arbitrary expressions.

#### Evaluation models

As you may recall, expressions are *reduced*, and their reduction may be performed in any order. Let’s look at an example:

sumIt :: Int -> Int -> Int |

This simple function sums the two arguments together. Invoking it with the following:

> sumIt (1 + 2) 3 |

gives us the expected result 6. How can we arrive at this result? There are two possible strategies: the first, used in most programming languages, is called *eager evaluation* (sometimes *strict evaluation*). We first calculate the result of the expression `(1 + 2)`

, and only then the function is applied. The second strategy, which is used in Haskell, is called *lazy evaluation*: we first substitute the expressions in the body of the functions, and only then perform the reduction. Here is an example of lazy evaluation reduction steps in Haskell:

sumIt (2 + 3) 4 |

First, we substitute the expressions in place of the former parameters `x`

and `y`

, namely `(2 + 3)`

and `4`

, and inside the body evaluate and reduce the expressions.

Compared to the eager evaluation:

sumIt (2 + 3) 4 |

Where the expression `(2 + 3)`

is evaluated first.

Let’s introduce a bit of terminology: an expression that can be simplified further is called a *redex* (short for *reducible expression*).

In the lazy evaluation example above there are two redexes: the first is the expression `(2 + 3)`

- the `+`

operation can be further simplified. The second redex is the function application itself.

In situations where we have multiple redexes, we can employ different evaluation strategies for them.

In pure functional languages, the same result will always be produced, regardless of the evaluation strategy. This is not guaranteed in imperative languages where order of evaluation matters.

#### Lazy evaluation

Let’s look at the properties of lazy evaluation. Consider the following function:

add7 :: Int -> Int -> Int |

The number 7 is added to the first argument `x`

, the second argument is ignored.

Let’s look at the reduction steps for both lazy and eager evaluation strategies:

-- lazy |

In the first case we substitute the formal parameters `x`

and `y`

of `add7`

with the expressions `1`

and `(2 + 3)`

. Since the function uses only the first argument, the second is completely ignored, therefore the second argument is not evaluated.

In case of the eager evaluations, both expressions are first evaluated, before being bound to the function arguments.

The lazy evaluation strategy is more efficient in this case, since it does not attempt to evaluate expressions that will not be used. However, this is not always the case. Here’s an example:

dup :: Int -> (Int,Int) |

Reducing this using both strategies:

-- lazy |

The lazy evaluation strategy requires 4 steps of reduction, while the eager evaluation is more efficient.

Lazy evaluation is preferable when some of the function parameters are ignored, while eager (strict) evaluation is preferable when they are used multiple times in the body of the function.

Luckily, Haskell optimizes for such cases of duplicate use by deferring the evaluation, allowing calculating the result just once. This layer of indirection is called a *thunk*, and it works as follows:

dup (2+3) |

The thunk `t`

points to a value that hasn’t yet been calculated. The first time the value is required, it is evaluated, and now the thunk points to the evaluated result, allowing substituting it immediately where it is further required, without reevaluating.

Thunking is what allows lazy languages like Haskell to operate on huge values, such as infinite lists, however, it also slightly complicates our ability to reason about the program, as it turns simple expression trees into graphs.

#### Strict and non-strict semantics

Lazy evaluation has some interesting properties when dealing with programs that do not terminate. In many cases, using lazy evaluation we can eliminate some cases of diverging programs. Let’s look at an example:

const42 :: a -> Int |

The `const42`

function takes one argument and returns an `Int`

. It is implemented by calling `const`

, passing it the number 42 and the argument. As you recall, the `const`

function ignores its second argument, causing our `const42`

function to always return the value 42.

> const42 True |

Since `const42`

always ignores its argument, we can also apply it to a non-terminating computation:

> const42 undefined |

The `undefined`

function always produces an error, but only when it is evaluated. In our case, the `undefined`

function is never used, so it’s never evaluated. This makes lazy evaluation suitable for eliminating divergent computations.

Functions, such as `const42`

are called *non-strict*. Formally, a non-strict function is a function that accepts a non-terminating (diverging) computation as an argument, but still produces a result (converging), it is considered non-strict. Conversely, a *strict* function, given a diverging computation as an argument, becomes divergent itself.

This allows us to separate functions into two kinds: strict and non-strict. However, in some functions, the strictness of a second argument may depend on the first. This makes *strictness analysis* into a non-trivial problem. The Haskell compiler performs strictness analysis to reduce the cost of lazy evaluation, which sometimes can lead to better performing and more effective programs.

#### Weak Head Normal Form

In functional languages, expressions are reduced until they cannot be reduced further. The reduction process happens for as long as there are *redexes* remain in the expression, resulting in an expression that no longer contains any redexes. Those fully-reduced expressions are in a so-called *normal norm*, meaning that no more reductions are possible.

In Haskell, there exists an intermediate reduction stage, called *weak head normal form* (abbreviated WHNF). Let’s look at some examples:

-- Normal Form |

The three expressions above are all in a normal form (NF). The first is a number 42, which has no other reduction steps. The second is a pair constructor, which is applied to the values 3 and 4, written in a *mixfix* style. This is also a value which cannot be reduced. The third example is a lambda expression. It too cannot be further reduced, since it does not contain any redexes (the `+`

operator is considered *built-in*, and it cannot be applied until both arguments are available).

Now let’s look at expressions which are not in NF:

-- not NF |

Redexes exist in all of the above examples, meaning they can be further reduced, therefore are not considered normal form.

Weak head normal form is a special case of an expression which contain redexes, comprised of the following:

- a lambda
*abstraction* - a data constructor
- any built-in partially-applied operator

Here are some examples of WHNF:

-- WHNF |

The first example is a lambda abstraction. It’s not in NF since it contains a redex `2*3`

, however when this expression is inside the lambda body, it is considered WHNF. The second example is a data constructor (tuple, in this case), which contains a reducible expression `1+5`

. However, because it occurs inside a data constructor, this is also considered WHNF. The third and fourth examples are built-in Haskell operators, partially-applied to a redex. This is also considered a WHNF.

It is said that expressions in NF are also at the same time WHNF. In most cases, Haskell will stop reducing expressions at WHNF, not reducing it further to NF. This allows Haskell to optimize functions for strictness.

#### Forcing strictness

We now know the meaning of lazy evaluation semantics. If an expression is not required - it will not be evaluated. In most cases this is a desired property, however, there are some cases this causes problems.

Haskell uses deferred execution, or, thunking, to perform lazy computations. In working with large data structures, such as lists of an arbitrary length, thunks may accumulate in memory. Suppose we’re summing a list of 10 million elements; in the lazy evaluation model, a thunk will have accumulated 10 million deferred `+`

operations, ready for evaluation, but it cannot happen until all elements have been processed.

Memory, or more specifically, *space leaks* is a common problem in Haskell, and often requires careful solutions. Sometimes, we’d like to instruct the Haskell compiler not to defer any computations, but perform them as soon as they’re available. This is achieved by using the Haskell primitive `seq`

.

The `seq`

primitive is a function that is used to force strict evaluation for a given computation. Let’s see how this function could be defined (in pseudo-code), and its uses:

seq :: a -> b -> b |

The `seq`

function can be though of as a function of two arguments, returning the second argument and ignoring the first. If it only had one definition (line 3 of the example above), it would be the same as using `flip const`

. Such a definition is only possible in a lazy language, since it requires deferring the evaluation of the arguments. However, the definition above is not a valid Haskell syntax, as we’re using a concept called *bottom* (also called *falsum*, denoted by the Unicode symbol ⊥ or an ASCII sequence `_|_`

), which signifies non-terminating, or, divergent computations. If the first argument to `seq`

is diverging, the result will also be diverging.

This function cannot be directly implemented using Haskell syntax, however it’s a built-in Haskell primitive.

Let’s see a few examples of using `seq`

:

> seq 1 2 |

Instead of ignoring its first argument, Haskell attempts to reduce it until WHNF. If this attempt fails (if the computation is divergent), `seq`

fails as well.

Let’s see some examples where using WHNF with `seq`

does not diverge:

> seq (undefined,undefined) 2 |

Because both expressions above are already WHNF, `seq`

is satisfied and does not attempt to reduce it further, returning the second argument.

#### Strict function application (call-by-value)

Even though the `seq`

primitive is useful, it’s not very convenient. Haskell defines a a more convenient *call-by-value* operator `$!`

, which can be used instead of `seq`

:

($!) :: (a -> b) -> a -> b |

The type of the `$!`

operator is identical to the `$`

operator, taking a function `a -> b`

and and argument `a`

, producing a `b`

. Here, it is using `seq`

in the infix style, and means the following: the argument `x`

is first reduced until WHNF, and then the function `f`

is applied to the reduced `x`

. Reduction here happens before function application, allowing the operator to force strictness. Let’s see some uses of this operator:

> const 42 undefined |

In the example above, we can see that the `$!`

operator works similarly to `$`

(they have the same precedence and associativity), however, the `$!`

forces the evaluation of its arguments. Since `undefined`

diverges, the result of `$!`

diverges as well.

Let’s see a real example where this is useful. Consider our `factorial`

function:

factorial :: Integer -> Integer |

The `helper`

function will recursively call `helper`

until `n`

reaches 0, accumulating nested calls to `helper`

with decreasing `n`

values. In reality, Haskell’s strictness analysis can handle this situation, and turn them into strict calls, however if we want to make sure this optimization happens, we could use the `$!`

operator to force this strictness ourselves:

... |

This change forces Haskell to evaluate the first argument to `helper`

, allowing us to eliminate the chain of nested computations. In addition, since the `$!`

operator has a low precedence, we must enclose the expression in parentheses.

### Modules and compilation

Haskell programs are a collection of *modules*. The main module is called `Main`

, and each module should reside in a file named after the module, although that’s not required. Inside the file, a module is declared by the keyword `module`

, followed by the module name (starting with a capital letter), followed by the `where`

keyword.

#### Modules

In the file `Demo.hs`

, we have the following definition:

module Demo where |

We can now add our own definitions and imports. The `Prelude`

module, which contains many basic functions is implicitly imported in our `Demo`

module, and we can start using its functions in our module immediately.

To use a function defined in another module, that module must first be imported by using the `import`

keyword:

module Demo where |

The `import Data.Char`

directive imports all functions that are exposed in the module. Sometimes we don’t need all the functions, so we can specify in parentheses the names of the functions we wish to import:

import Data.Char (toUpper,toLower) |

Sometimes we need the opposite operation - import all functions *except* the specified ones. This is allowed by using the keyword `hiding`

:

import Data.Char hiding (toLower) |

Suppose we want to import the function `union`

from `Data.List`

. Another `union`

function is also defined in `Data.Set`

. Importing both modules, then trying to use the `union`

function will result in the following error:

import Data.List |

> :t `union` |

The error suggests an ambiguity - Haskell is unable to determine which one of the `union`

s we meant. Instead, we can use the fully-qualified name, e.g. `Data.List.union`

:

> :t Data.List.union |

However this is not often convenient. In some cases we’d like to always refer to a function by its fully-qualified name. For this, there exists a keyword `qualified`

which imports module members with a fully-qualified name:

import Data.List |

Here, the ambiguity no longer occurs, since the `union`

function from the `Data.Set`

module must always be used fully-qualified:

> :t union |

Because the module names are hierarchical, the sometimes can be very long, and using the fully-qualified name proves cumbersome. Haskell allows to alias module names, allowing to locally rename them to something shorter, by using the `as`

keyword:

import qualified Data.Set as Set |

Allowing accessing it by the shorter name:

> :t Set.union |

In rare occasions we’d like to implement a function that already exists in the `Prelude`

. In this case, the `Prelude`

module must be explicitly imported, hiding the functions that we wish to override locally. All explicitly-imported modules override any implicit ones.

#### Exporting modules

Importing modules allows us to use functions declared in other modules. There is an opposite directive - `export`

, which controls which functions from our module are visible to others.

Let’s create two modules in two separate files, `Demo.hs`

and `Test.hs`

. In the `Test`

module we declare the following functions:

module Test where |

In the `Demo`

module:

module Demo where |

Let’s load it in GHCi:

$ ghci |

The Haskell compiler first attempts to compile and load the imports, and then the actual module we’ve requested. If everything loaded without errors, we’ll see the “Ok, two modules loaded” message.

If we want to limit the functions that are available to other modules, we can *export* just some of them, by specifying their names in parentheses after the module name. In our `Test`

module, let’s only export the `sumIt`

function:

module Test (sumIt) where |

Saving, then reloading our GHCi session will produce the following error:

*Demo> :r |

The interpreter reports that the compilation failed, only the `Test`

module was loaded. The `Demo`

module reports an error that the `const42`

function is not available.

The export directive is Haskell’s only mechanism for encapsulation. Similarly to object-oriented languages, where encapsulation is a means of hiding implementation details from public API, in Haskell, exporting only certain functions is the only way to keep some of the functions *private* to the module.