A Haskell program is a list of definitions. Each definition binds a name to the value it represents. There are only two possible types of definitions: constants and functions. Apart from definitions, only comments and compiler directives are allowed at the top level in a file. The general structure of the program is as follows:

```
{- LANGUAGE xxxxx #-}
module ModuleName where
import OtherModule1(other1def1,other1def2,other1def3)
import OtherModule2(other2def1,...)
... more imports ...
{-
Block comment
Several lines long
-}
-- Line comment. It runs up to end of the line
definition
definition
definition
... more definitions ...
```

The line `{- LANGUAGE xxxxx #-}`

is used to extend the syntax with additional constructions that are not part of the Haskell standard. The only syntax extension we are using is `ParallelListComp`

.

A full program can be broken into separate files, called *modules* in Haskell jargon. The name of a file and the name of a module should be the same, and both should start with a capital letter. Otherwise, the compiler will not be able to find the modules needed in a program. If the name of the module is not declared,i.e., no line like `module Name where`

is present, then the name of the module is assumed to be `Main`

. A module can use definitions from other modules, but they must be *imported* first. Once imported, the definitions can be used just as if they were part of the module.

Apart from the compiler directives at the beginning of a file and comments, the rest of the file must consist of just function and constant definitions. If any other construction is found, the compiler will produce a *naked expression at toplevel* or a *parse* error. Compilation of the full program is initiated by passing to the compiler the name of the file containing the `main`

function, which is the starting point. The type of `main`

is `IO ()`

. `IO`

means that the only operations allowed inside it are input (`getLine,getArgs`

) and/or output (`writeFile,putStr`

) operations. The empty parentheses after `IO`

mean that once main ends, all inputs not yet processed are discarded.

IO operations must be part of a do-block, unless there is only one operation. In that case, the `do`

keyword is optional. IO operations are sequential and may have side effects. Sequential means that the order in which they are executed matters. When an operation has side effects, repeating it will typically produce different observable results each time, such as adding new lines to the console output, overwriting a file (thus changing the creation time of the file even if the content is the same) or saving unpredictable input values into the computer memory. In contrast, an operation with no side effects will produce the same result every time it is executed. In Haskell jargon, a function with no side effects is called *pure*. Pure functions are *referentially transparent*, which means that if a function call is replaced by its body anywhere in a program, the result is indistinguishable from the original. In pure functions, order of execution is determined only by how values depend on other values. When two values are independent of each other within a pure function, order does not matter, because no observable effect can be present.

For example, consider the following pure definitions:

```
z = x - y
x = 5 * 2
y = 9 + 3
```

Since `z`

depends on `x`

and `y`

, the definitions for x and y must be executed first. However, since x and y are independent, it does not matter which one is executed first. Therefore, the computer is free to do the multiplication (for x) or the addition (for y) in any order. There is no way to find out which one executed first by just observing the result. And we are also sure that the subtraction (for z) must be executed last, even if it is written first.

Contrast this with the following case:

```
do
x <- getInt -- getInt reads a line from the standard input
y <- getInt -- and saves it as an integer
let z = x - y
```

If the user enters 12 and then 10, the result for z will be different depending on whether x is read first or y is read first. Since order matters in this case, the compiler will not reorganize the lines. Instead, in a do-block, the lines will be executed in the order they are written.

A very useful tool for both novice and expert Haskell programmers is the GHCI interpreter, which is really an on-the-fly compiler. GHCI can be used to test partially completed programs, even when no `main`

function is included, for finding out about the actual types of complicated expressions and to inspect the value of constants. Once you enter `ghci`

, you can type either Haskell expressions or ghci directives. All ghci directives begin with a colon.

The most common ghci directives are:

:quit

*Exit from the ghci environment*:help

*Shows a list of all the ghci directives*:load filename

*Load the definitions from filename into the environment*:set args arg1 arg2 arg3 ....

*Simulate command-line arguments for the program*:type name

*Show the type of the value bound to name*:type expr

*Show the type of the value to which expr evaluates*:set editor vi|emacs

*Use vi|emacs to edit the source code inside the environment*:edit

*Edit the currently loaded file inside the environment*:reload

*Recompile on the fly the file currently loaded. Useful after editing it*

The ghci environment runs inside an implicit do-block, so any Haskell expression that is legal in a do-block can be entered into ghci. In versions of ghci prior to 2017, this meant that constant and function definitions needed to be preceded by the keyword `let`

, because that is how you enter definitions in the middle of a do-block. This is not needed in the current version of the Haskell interpreter. Also, due to the implicit do-block, IO operations, such as `putStr`

or `getLine`

, can be entered directly at the ghci prompt. Any other expression entered at the prompt is evaluated, and the result of the evaluation is displayed. This feature is handy for inspecting the values of constants.

The function `show`

can convert most values to strings representing them. The string representation output by `show`

is a valid Haskell expression that could be used as a literal value in a Haskell program. In addition, the string could be read back as a value with the function `read`

.

The function show, when applied to a string, produces a representation of a string as it would be entered in a Haskell program. Since a string literal in a program needs to be enclosed in double quotes, the string representation will include the double quotes as part of the output. Try this in GHCI:

```
Prelude> show "hello"
"\"hello\""
```

The backslashes are needed to *e*scape the double quotes, so that they are not interpreted as special characters. This representation is usually not what you need, so in general you should avoid applying the function `show`

to a string value.

Something similar occurs when you apply `show`

to a list. The representation of a list literal needs square brackets enclosing the string, and so the brackets will be added to the output, so that the list can be read back as a value if necessary:

```
Prelude> show [1,2,3]
"[1,2,3]"
```

Note that the double quotes in the previous output are actually *n*ot part of the string, as you can check by using the function `head`

. Remember that the head of a list is just its first element:

```
Prelude> head (show [1,2,3])
'['
```

Contrast this with:

```
Prelude> head (show "hello")
'"'
```

and with:

```
Prelude> head "hello"
'h'
```

As a general rule, do not use `show`

on strings or lists, unless you cannot do better. You will usually want to apply `show`

inside a list to its individual elements:

```
Prelude> [show i | i <- [1,2,3]]
["1","2","3"]
```

You can then use the functions `concat`

and `intersperse`

to build a string out of the individual elements so that it is nicely formatted. The function `intersperse`

adds a separator of your choice between each pair of elements. You need to add `import Data.List(intersperse)`

at the beginning of your file if you want to use it. The function `concat`

builds a string out of the individual elements by concatenating them all together. Example:

```
Prelude> import Data.List(intersperse)
Prelude Data.List> concat( intersperse "; " [show i | i <- [1,2,3]] )
"1; 2; 3"
```

**Exercise:** Try to understand the output of:

` take 3 (iterate show "")`

When you define a function whose output does not depend on one of the inputs, you can use a single underscore instead of giving a name to the corresponding parameter. A single underscore is a way to indicate that we do not care about the value of that particular parameter. For example, to define a function that results in 5 no matter what the input value is, we do:

```
Prelude> let f _ = 5
Prelude> f 3
5
Prelude> f 2
5
```

Don’t care arguments are also useful to extract parts of a tuple or a list:

```
Prelude> let abcissa(x,_) = x
Prelude> let ordinate(_,y) = y
Prelude> abcissa(2,5)
2
Prelude> ordinate(2,5)
5
```

The functions `abcissa`

and `ordinate`

are already built into the standard Haskell library under the names `fst`

and `snd`

, respectively.

Here is another example:

```
Prelude> let [_,x,_,_] = [1,2,3,4]
Prelude> x
2
```

Underscores are valid characters to use in function and constant names. However, when a single underscore is used, no definition for it is created, so trying to use a single underscore when a name is expected will result in an error:

```
Prelude> let (x_,_) = (1,2) in x_
1
Prelude> let (x_,_) = (1,2) in _
<interactive>:1:23: Pattern syntax in expression context: _
```

When an invalid floating point operation is performed, instead of an error, a special value is returned as result. There are three special values: `Infinity`

, `-Infinity`

and `NaN`

. The value `Infinity`

is returned when a non-zero positive value is divided by 0.0 or when a very large positive value overflows, and similarly for negative numbers. The value `NaN`

means *N*ot a Number, and it is returned when the result of an operation could be any value, such as `0.0/0.0`

, `0.0*Infinity`

or `Infinity - Infinity`

.

There are no pre-defined constants in Haskell with those values, but it is easy to generate them if needed by using one of the operations listed above. Special care needs to be taken to check whether the value `NaN`

is returned by a calculation, because comparing `NaN`

with itself returns `False`

:

```
Prelude> let nan = 0.0/0.0
Prelude> nan
NaN
Prelude> if nan == nan then "NaN was found" else "Everything is OK"
"Everything is OK"
```

The built-in function `isNaN`

must be used instead:

```
Prelude> if isNaN nan then "NaN was found" else "Everything is OK"
"NaN was found"
```

You can also use the function `isInfinite`

to check whether a value is `Infinity`

or `-Infinity`

.

In Functional Programming, a common pattern is to build a data structure with all the information needed to solve a problem, and then pass the data structure through a chain of functions composed to each other, so that the output of a function is immediately fed as input to another function. Each function performs a small part of the overall job, so that there is a clear decomposition of a task into small independent subtasks.

Recall that a functional chain is just a composition of functions:

` Prelude> let chain = f5 . f4 . f3 . f2 . f1`

where the composition operator was defined by the equation `(f . g) x = f (g x)`

, which is executed backwards. The previous `chain`

could be expanded into a series of individual applications, where the intermediate values can be made explicit. Assume the initial input value to the chain is `x0`

. Then:

```
chain x0 = (f5 . f4 . f3 . f2 . f1) x0
= (f5 . f4 . f3 . f2) (f1 x0)
= (f5 . f4 . f3) (f2 (f1 x0))
= (f5 . f4) (f3 (f2 (f1 x0)))
= f5 (f4 (f3 (f2 (f1 x0))))
-- Equivalently, with intermediate values:
x1 = f1 x0
x2 = f2 x1
x3 = f3 x2
x4 = f4 x3
x5 = f5 x4
```

`Therefore:`

` x5 = chain x0`

The value `x0`

is transformed into `x1`

by the function `f1`

. Then, the value `x1`

is transformed into `x2`

by the function `f2`

, and so on until the end of the chain is reached. The first function in the chain usually just builds a data structure based on the given input value, and the last function in the chain extracts the desired output from the data structure.

Data structures in Haskell are very lightweight, so it is easy to construct and deconstruct them. So far, we only used lists and tuples, but even with just those you can go far.

For example, consider the `bisection`

function below, which calculates a root of an input function `f`

by the bisection method. Given a continuous function `f`

and two points `a`

and `b`

such that `f(a)`

and `f(b)`

have opposite signs, then the point `x = bisection f (a,b)`

will be close to a root of `f`

. More precisely, `x`

will satisfy `|f(x)| < eps = 1e-15`

for this piece of code. Note that similarly to the definition of the function `chain`

, we do not need to enter the input variables in the definition of `bisection f`

.

```
bisection f =
apply2 get_midpoint
. apply1 length
. apply2 head
. span not_converged
. take max_iter
. iterate (add midpoint . select_next)
. add midpoint
. put_in_order
where
get_midpoint (_,x,_) = x
not_converged = (> eps) . abs . f . get_midpoint
select_next (xminus,x,xplus) =
if f x <= 0 then (x,xplus)
else (xminus,x)
add p (a,b) = (a,p (a,b),b)
midpoint (a,b) = 0.5*(a+b)
put_in_order (a,b) =
if f a > 0 then (b,a)
else (a,b)
-- aux --
apply1 f (x,y) = (f x,y)
apply2 g (x,y) = (x,g y)
-- config --
eps = 1e-15
max_iter = 100
```

The bisection function is defined as a functional chain, where the input to the chain is the pair `(a,b)`

, and the transformations, in order of execution, are `put_in_order`

, `add midpoint`

, `iterate ...`

, `take max_iter`

, `span not_converged`

, `apply2 head`

, `apply1 length`

and `apply2 get_midpoint`

.

Initially, we assumed only that `f`

had different signs at `a`

and `b`

, but the result of `put_in_order (a,b)`

is a pair `(a1,b1)`

that satisfies `f(a1)<=0`

and `f(b1)>=0`

. The result of `add midpoint (a1,b1)`

is a tuple `(a1,m,b1)`

in which the midpoint of `a1`

and `b1`

has been added.

The main part of the calculation is done under `iterate`

. Recall that `iterate f x`

results in the infinite list `[x,f x,f(f x),f(f(f x)),...]`

or, equivalently, `[x,(f)x,(f.f)x,(f.f.f)x,...]`

. So, `iterate f x`

is a list of composition chains of length 0,1,2,3,... all of them with initial value `x`

. Thus, `iterate (add midpoint . select_next)`

is a chain where the general term is of the form

` add midpoint . select_next . add midpoint . select_next . add midpoint . select_next ...`

The input to `select_next`

was a 3-tuple `(a1,m,b1)`

as described before. The result of `select_next`

is either the interval `(a1,m)`

or the interval `(m,b1)`

. An interval from those two is selected so that the the value of `f`

is negative for the left value and positive for the right value. The outputs can be thought of as new inputs `(a2,b2)`

that are fed into `add midpoint`

, which will produce `(a2,m2,b2)`

, which is then fed into `select_next`

, which then produces a new interval `(a3,b3)`

, which is then fed into `add_midpoint`

to get `(a3,m3,b3)`

, and so on. This infinite list is fed into `take max_iter`

, which truncates it to just the first 100 terms.

The list, after truncation, is

` [(a,m,b),(a1,m1,b1),(a2,m2,b2),...,(a99,m99,b99)],`

which is then separated by `span not_converged`

into two parts: the first part will contain the terms that did not converge, while the second part will contain the terms that converged.

Recall that the definition of `span`

is

` span predicate list = (takeWhile predicate list, dropWhile predicate list)`

In our case, the predicate is `not_converged`

, which is defined as

` not_converged = (> eps) . abs . f . get_midpoint`

`Therefore,`

```
not_converged (a,m,b) = ( (> eps) . abs . f . get_midpoint) (a,m,b)
= ( (> eps) . abs . f) (get_midpoint (a,m,b))
= ( (> eps) . abs . f) m
= ( (> eps) . abs) (f m)
= (> eps) (abs (f m))
= (abs (f m)) > eps
```

Thus, `not_converged`

means that the value of f(x) is far from being zero. Naturally, the converse is the condition |*f*(*x*)| < *ϵ*, which means that *x* is a root of *f*, within a precision of *ϵ*.

Then `apply2 head`

extracts from the terms that converged the first one, which is all that we need. Then, `apply1 length`

takes the terms that did not converge and counts them, so that we can know how long it took to converge. At this point, the data structure has been transformed into a pair `(n,(a',m',b'))`

, where `n`

tells us how long it took to converge and `(a',m',b')`

are the end points and the midpoint of the first interval that converged. Finally, `apply2 get_midpoint`

extracts just the midpoint of the interval, so that the final result is `(n,m')`

.

Let us look more carefully at how one of those steps is performed. For example, let us focus on `apply1 length`

. The input to that, which is just the output of `apply2 head`

, is a pair `(bad_terms,good_term)`

, where `bad_terms`

is a list of the terms that did not converge and `good_term`

is the first term that converged. Each term is of the form `(a,m,b)`

. Now, given the equation

` apply1 f (x,y) = (f x,y),`

we match it to `apply1 length (bad_terms,good_term)`

, which means that

`apply1 length (bad_terms,good_term) = (length bad_terms,good_term).`

So, we see that the first list is replaced by just its length and the second term is returned without any change.

Data structures in Haskell are called *records* and are similar to `structs`

in C. The name of the data structure must begin with an uppercase letter. The field names must begin with a lowercase letter, and each field name must be followed by its type. The syntax of a record definition is as follows:

```
data RecordName = RecordName
{ field1 :: Type1
, field2 :: Type2
, field3 :: Type3
, ...
, fieldN :: TypeN
}
```

Note that the record name must appear twice, once at each side of the equal sign.

Here is an example of a record with two fields: a time and a position, both of type double:

```
data State = State
{ time :: Double
, position :: Double
}
```

There are two ways to create a record: by field name and by field order. For example, to create a `State`

where the value of `time`

is 0.0 and the value of `position`

is 10.0, we can use either of these two:

```
-- Fields are filled in order (first is time, second is position)
state1 = State 0.0 10.0
-- Fields are filled according to their name
state2 = State { position = 10.0, time = 0.0 }
```

The previous examples create a `State`

record, which is then bound to a variable (`state1`

or `state2`

).

The value stored in a field is extracted by applying the name of the field to the record as if it was a function. Here is an example:

```
state3 = State 0.5 7.2
time3 = time state3 -- value of time3 will be 0.5
position3 = position state3 -- value of position3 will be 7.2
```

In an object oriented language, you would use `state3.time`

and `state3.position`

instead of `time state3`

or `position state3`

, but although the syntax is different, the meaning is the same.

In Haskell, all data structures are immutable, so it is not possible to modify the value of a field after a record is created. However, it is possible to create a *new record* that is a copy of the original record, except for a few fields that have been modified. To create a record with a modified field, you use a syntax similar to that for creating a record. However, instead of using the name of the record type, you use a reference to the instance you want to modify, and instead of listing all fields, you list only those fields that you want to modify.

Example:

```
-- Create a record of type State and bind it to variable state4
state4 = State 1.2 3.8
-- Modify the position, and bind the new record to state5
state5 = state4 { position = 4.0 }
-- Modify the time, and bind the new record to state6
state6 = state5 { time = 2.2 }
-- value of state4: { time = 1.2, position = 3.8 }
-- value of state5: { time = 1.2, position = 4.0 }
-- value of state6: { time = 2.2, position = 4.0 }
```