Content

## Introduction

Haskell is a pure functional programming language. Two free well-known haskell compilers are availbale on the intranet:

Some references to learn the language:

### What is functional programming ?

To answer this question we first look at a function.

A function is a transformation of input data (arguments) to output data.

A computer progam consists of a collection of functions. Each function within a computer program can be a high-level or primitive function. A primitive function is a function that can be uniquely mapped by the compiler to a CPU instruction. A CPU instruction is the ultimate transformation step that can be applied to data in the memory of a computer.

It is only the data in the memory of a computer that we can transform and we transform it by applying a function to this data. All computer languages have predefined primitive functions, like mathematical operators, such as: add (+),subtract (-),multiply (*), divide (/), boolean operators. Only these primitive functions can change the data in the computer memory. A computer program consists of user defined functions that apply the primitive functions to data in the memory of the computer. However specifying the data transformation is only one aspect of a computer program another as important aspect is the sequence of instructions. This sequence of instructions is called the control flow. It allows the programmer to specify the flow of the transformations by branching and jumping (if .. then .. else) and repetition (loop). Next the computer language must also be able to assign to a certain location in the computer memory a value and to move data in and out of the computer memory to other devices (screen, printer, network,...). So, any computer language must specify in a certain way these type of actions: assiging data, modifying data, branching and looping, and transferring data.

For the design of a computer language different methodologies have been followed. The traditional approach, imperative languages, define the data to be used, and then the functions to transform this data. Functional programming languages define only functions. That is the main difference.

To show the difference in approach between an imperative and function language we take a look at a simple function that sums n the first n integers. Here is the imperative variant of such a function:

and here the functional variant

Note that in a functional language we do not define the variables list, n and s. A lot of code in an imperative language is used to define variables and updating the value of these variables. However as functional languages show we could specify the same function with less detail, and let the computer figure out (by the compiler) how to complete the specified task. The functional langauge gives a more 'mathematically' definition of what a sum really means. First it says that the sum of nothing, the empty list, is zero. Then for the other cases the sum is the addition of the first element to the sum of the remaining elements. This is a recursive definition. So the computer can now iterate through the list without the need for the programmer to define this low level iteration process. You also notice that the syntax is far more concise, no curly braces, no semicolon to end a statement. It is an elegant way of programming which focus more on defining concepts and less on the sequential steps to perform mechanical calculations.

• Concise programs: much shorter programs
• Powerful type system: little type information needed from the programmer
• List comprehensions: lists as a basic concept in the language to define functions on
• Recursive functions: avoiding explicit loops by using recursion as the main mechanism for loops
• High-order functions: functions can take functions as arguments and output functions
• Monadic effects: to interact with the real world (input/output devices) the mathematical notian of a monad is introduced
• Lazy evaluation: no computation is performed until the result is needed

### History

• In the 1930s, Alonzo Church developed the lambda calculus, a simple but powerful mathematical theory of functions.
• In the 1950s, John McCarthy developed Lisp (“LISt Processor”), generally regarded as being the first functional programming language. Lisp had some influences from the lambda calculus, but still adopted variable assignments as a central feature of the language.
• In the 1970s, John Backus developed FP (“Functional Programming”), a functional programming language that particularly emphasised the idea of higher-order functions and reasoning about programs. Also in the 1970s, Robin Milner and others developed ML (“Meta-Language”), the first of the modern functional programming languages,which introduced the idea of polymorphic types and type inference.
• In the 1970s and 1980s, David Turner developed a number of lazy functional programming languages, culminating in the commercially produced language Miranda (meaning “admirable”).
• In 1987, an international committee of researchers initiated the development of Haskell (named after the logician Haskell Curry), a standard lazy functional programming language.
• In 2003, the committee published the Haskell Report, which defines a longawaited stable version of Haskell, and is the culmination of fifteen years of work on the language by its designers.

We assume the Hugs system is used. The Hugs system is an interactive environment. Commands and Haskell instructions are typed at the the command prompt $>$. To see the build in commands type :?. Any command can be started by its first letter. During startup the Hugs systems loads prelude.hs. This module defines a number of basic functions, type :names to see the list of functions or open prelude.hs in a text editor.

Haskell defines the standard operations on numbers:

• subtraction:>4-2
• multiplication:>3*5
• exponentiation:>2^3
• integer division:>7 'div' 3 or div 7 3 (any function with two arguments can be written in infix notation by putting the function name between single back quotes)

These operators follow the normal precedence rules. With parentheses (,) this order can be overruled or shown explicitly. The operators can be called also in prefix notation: (+) a b

Haskell has many standard functions which operate on lists: head, tail, length, take, drop, sum and many more. A list argument has by convention an s as suffix, e.g. a list of numbers: ns, a list of arbitrary values: xs and a list of characters: cs.

The following list of keywords can not be used as function names:

• case class data default deriving do else
• if import in infix infixl infixr instance
• let module newtype of then type where

A function definition is defined in a text file with .hs as file extension. The file is loaded or after changing reloaded in the Hugs environment with the commands :load and :reload. Function names start with a small letter. A function in mathematics is denoted by $f(a,b,c)$ whereas in Haskell this is denoted by $f a\:b\:c$. A composition of functions in mathematics is denoted by $f(a,g(b))$ and in Haskell by $f \:a \:(g\:x)$.

A function definition relies on a lay-out rule: the elements of a function definition at the same level are aligned in the same column and different levels are indicated by indention.

### Types and classes

A type is a collection of related values. We use the notation $v :: T$ to denote that $v$ is a value of type $T$ and $f:T_1 \rightarrow T_2$ to denote that $f$ is a function transforming values of $T_1$ to values of $T_2$ and $e::T$ to denote that the expression $e$ result in a value of type $T$. In Haskell, every expression must have a type, which is calculated prior to evaluating the expression by a process called type inference. $\frac{f::A \rightarrow B \;\;\; e::A}{f \;\; e::B}$ If a proper type can not be derived, the expression is in error. Haskell is type safe because type inference precedes evaluation.

### Basic Types

Bool
This type contains the logical values False and True. Basic operations: && (and), || (or), not
Char
This type contains all single characters that are available from a normal keyboard, as well as a number of control characters that have a special effect, such as ’\n’ (move to a new line) and ’\t’ (move to the next tab stop). As is standard in most programming languages, single characters must be enclosed in single forward quotes ’ ’.
String
This type contains all sequences of characters, such as "abc", "1+2=3", and the empty string "". Again, as is standard in most programming languages, strings of characters must be enclosed in double quotes" ".
Int - fixed precision integers
For example, the Hugs system has values of type Int in the range -231 to 231 - 1
Integer – arbitrary-precision integers
This type contains all integers, with as much memory as necessary being used for their storage, thus avoiding the imposition of lower and upper limits on the range of numbers.
Float – single-precision floating-point numbers
The term floating-point comes from the fact that the number of digits permitted after the decimal point depends upon the magnitude of the number.
[T] - list type
• A list is a sequence of elements of the same type, with the elements being enclosed in square parentheses and separated by commas e.g. [1,2,3]
• The list [ ] of length zero is called the empty list.
• Lists of length one are called singleton lists.
• Due to the use of lazy evaluation in Haskell, lists with an infinite length are allowed e.g. the list of positvie integers:[1..]
• lists are not primitive as such, but are actually constructed one element at a time starting from the empty list [ ] using an operator : called cons that constructs a new list by prepending a new element to the start of an existing list. So [1,2,3] is in fact 1:(2:(3:[])).
• The list [T] denotes a list whose elements are of type T. The list [a], where a is a variable, denotes a list whose elements are all of any type.
• Lists can be appended (concatenated) with the ++ operator.
• A string is a list of characters, that is, it has type [Char]. For convenience, a string may be written with double quotes, e.g. "Haskell" is the same thing as ['H','a','s','k','e','l','l'].

### Functions

#### Comment

: a -> [a] -> [a] (infix) Add an element to the front of the list
++ [a] -> [a] -> [a] (infix) Append two lists
!! [a] -> Int -> a (infix) Return element Int of the list, counting from zero
head [a] -> a Return the first element of the list
tail [a] -> [a] Return the list with the first element removed
last [a] -> a Return the last element in the list
init [a] -> [a] Return the list with the last element removed
reverse [a] -> [a] Return the list with the elements in reverse order
take Int -> [a] -> [a] Return the first Int elements of the list
drop Int -> [a] -> [a] Return the list with the first Int elements removed
nub [a] -> [a] Return the list with all duplicate elements removed
elem notElem [a] -> a -> Bool Test for membership in the list
length [a] -> Int The number of elements in the list
concat [[a]] -> [a] Given a list of lists, concatenate all the lists into one list

### List Notations

#### Example

[a..b] A list of integers from a to b [1..5]=[1,2,3,4,5]
[a..] A list of integers >=a [1..] all positive integers
[a,b..c] A list starting at a with step b-a and up till <=c [1,3..10]=[1,3,5,7,9]
[a,b..] A list of integers from a with step b-a [1,3..] all positive odd numbers
[ exp_x | x <-list] A list of values of the expression with x drawn from list [x^2 | x <-[1,..]] list of squares of positive integers
[ exp_x | x <-list, y<-list] A list of values of the expression with x and y drawn from two lists [[x,y] | x<-['a'..'b'], y<-['x'..'z']]
[ exp_x_y | x <-list, y<-list] A list of values of the expression with x and y drawn from two lists [[x,y] | x<-['a'..'b'], y<-['x'..'z']]
[ exp_x | x <-list, condition_x] A list of values of the expression with x drawn from a list and for which condition is true [ x^2 | x<-[1..10], even x] = [4,16,36,64,100]
[ exp_x_y | x <-list,condition_x, y<-list, condition_y] A list of values of the expression with x and y drawn from two lists and with condition on x and y [x+y | x<-[1..5], even x, y<-[1..5], odd y]=[3,5,7,5,7,9]
$(T_1,T_2,...,T_n)$ - tuple
A tuple is a finite sequence of components of possibly different types, with the components being enclosed in round parentheses and separated by commas. The number of components in a tuple is called its arity. The tuple () of arity zero is called the empty tuple, tuples of arity two are called pairs, tuples of arity three are called triples, and so on. Tuples of arity one, such as (False), are not permitted because they would conflict with the use of parentheses to make the evaluation order explicit, such as in (1 + 2) * 3. Finally, note that tuples must have a finite arity, in order to ensure that tuple types can always be calculated prior to evaluation.
$T_1 T_2 ... T_n \rightarrow T_{n+1}$ - function type
A function is a mapping from arguments of any type to results of any other type.
$T_1 \rightarrow T_2 \rightarrow T_3 ... \rightarrow T_n$ - curried function type
Curried functions are where the arguments are taken one by one and returning a function.
$[a] \rightarrow b$ - polymorphic function type
Polymorphic functions can be applied to one or more variable types. Variable types are denoted by small letters.
$C \;\; a \rightarrow a \rightarrow b$ overloaded function types
An overloaded function is a function that is defined with a class constraint, limiting the appropriate values from a class. There are some basic classes with allowable operations. A function can belong two more than one class.
• Eq: equality class: ==, /=
• Ord: ordered class: >, >= <. <=
• Num: numeric class:^,+,-,*,negate,signum,abs
• Show: showable class
All the basic types Bool , Char, String, Int, Integer, and Float are instances of the Eq, Ord, Show and Read class, as are list and tuple types, provided that their element and component types are instances of the class. Int and Integer are also instances of Num and Integral. Float is an instance of Num and Fractional.

## Functions

A function definition consists of a name, arguments and expressions containing these arguments. Expressions are evaluated to values of a certain type. A function is nothing more than the value to which the related expression evaluates. Functions in Haskell can be treated in the same way as any other value.

The expression on the right of the equals sign indicates an (anonymous) function of two arguments, x and y, with the body of the function following the arrow; this function is "assigned to" the identifier on the left of the equals sign. (The backslash in this expression is pronounced "lambda.") Anonymous functions are used frequently in Haskell, usually surrounded by parentheses. A more compact notation is:

Athough it looks that averageof2 is a function with two arguments this is just an illusion. It consists of two anonymous functions: \x and \y. Application of this function:

So all Haskell functions are in fact single argument functions, the function operator -> has a right to left association and the function application on the arguments a left to right association.

There are several mechanisms to choose which part of a function body should be executed depending on the parameters of the function.

### Pattern matching

A function can be defined by different equations. The equation with a pattern that matches the actual arguments in a function call is executed. The pattern is used also to bind some values of the arguments being matched.

The following are patterns: literals, [], _, if p1 and p2 are different patterns then also p1:p2, if p1..pn are different patterns then also (p1,...,pn) is a pattern. The same identifier must not come more than once in a pattern, so (x,x) is not a valid pattern in Haskell.

The two equations for the definition of length are exhaustive for lists, so for any list the concept of length is defined.

A function can also be defined by one equation and different branches defined by so called guards.

using otherwise informs Haskell that the braching is exhaustive. If a function branching is not exhaustive an exception is generated when the arguments can not be matched with any pattern. The compiler warns the programmer for non-exhaustive patterns if the following option is set:

> :set -fwarn-incomplete-patterns


If patterns are overlapping then Haskell applies the following rule: when multiple equations apply, the one that occurs first (from top to bottom) is the one chosen.

Another construct with patterns are ascriptions. An ascription is a reference to the matched pattern.

## Types

Instead of using build in types like Bool, Int, Float, Double, Char, Maybe, one can define its own types. Defining types is often usefull to make the code more human readable and to avoid that we perform incompatible operations, like adding apples and peers. There are different ways to define a type.

The name of the data type is left of the =-sign. The parts after the =-sign are value constructors. Multiple value constructors are separated by | (or). Both the type name and the value constructors have to be capital cased. A value constructor is a function that returns a ultimately a value of te data type. The value constructor can take therefore parameters like functions.

The data type itself can also take parameter(s), we call it a type constructor.

Maybe is a type, but depending on whether or not it receives another type as a parameter it will return Nothing or Maybe a. We usually use type parameters when the type that's contained inside the data type's various value constructors isn't really that important for the type to work. With the type parameter we give some flexibility to the use of the type.

### Record syntax

Especially when there are a large number of value constructors the record syntax can be usefull. Instead of:

following record syntax is much easier to read and use: The resulting data type is exactly the same. The main benefit of this is that it creates functions that lookup fields in the data type. We don't have to necessarily put the fields in the proper order, as long as we list all of them in creating a new value.

### Typeclasses

Another thing we need in working with types are generic functions that apply the same kind of behavior to differtent types. For each type the same function name can be used, but each type has its own implementation of the functionality. Haskell solves this with a typeclass. A typeclass is a sort of interface that defines some behavior. If a type is a part of a typeclass, that means that it supports and implements the behavior the typeclass describes. Haskell has a predefined a number of typeclasses. For many simple data types, the Haskell compiler can automatically derive instances of the following typeclasses: Read, Show, Bounded, Enum, Eq, and Ord for your own defined types.

Typeclasses are not equivalent to the concept of a class in OOP.

Let us take a look at the type signature of the function (==) which tests for equality (or we could also use the negation /=):

We see left of => the type class constraint, in this case (==) is a binary function that can be applied to two values of the same type and the type must belong to the typeclass Eq, the function returns a value of type Bool.

We give now some examples of apply the generic functions belonging to the standard typeclasses: Eq,Show,Read,Ord:

Another example of a function with multiple class constraints is fromIntegral.

This function is used to convert an integral type to a more general number type.

Avoid using type constraints in the definition of a new type. Because we don't benefit a lot, but we end up writing more class constraints for functions using this type, even when we don't need them.

We can define typeclasses ourselves. This is how the Eq class is defined in the standard prelude:

a is a type that is an instance of the typeclass Eq. In the typeclass we define the type of the functions belonging to the typeclass. We can also define these functions in the typeclass. In this case we have defined them in terms of mutual recursion. That way instances need only to define one of them.

Let us bnow define a new type:

and make this type an instance of the typeclass Eq:

You can also make typeclasses that are subclasses of other typeclasses. The class declaration for Num is a bit long, but here's the first part:

We state that our type a must be an instance of Eq.That's all there is to subclassing really, it's just a class constraint on a class declaration.

Let us see another example of an instance declaration for Maybe. Note that Maybe is a type constructor, so Maybe m is a concrete type which can be defined as an instance of a typeclass.

we have to define a class constraint on m. We want all types of the form Maybe m to be part of the Eq typeclass, but only those types where the m (so what's contained inside the Maybe) is also a part of Eq. Most of the times, class constraints in class declarations are used for making a typeclass a subclass of another typeclass and class constraints in instance declarations are used to express requirements about the contents of some type.

To see the instances of a typeclass type: :info YourTypeClass, or to see the typeclasses of a type or type constructor use :info YourType.