Haskell

Haskell is a functional programming language we will be using in this module. It features a syntax which allows the definition of functions using mathematical-like syntax:

square x = x * x

The role of the computer is to evaluate and display the results of expressions that the programmer forms by composition of various functions, effectively like a sophisticated calculator.

Such expressions are evaluated through a series of reduction steps, for example, using the above function, the following expression:

square 6

Would be evaluated as follows:

$$square 6 \to 6\times6 \to 36$$ (1)

...finding the result of $36$. The complexity of this expression is set as $2$ then, since the total number of reduction steps required to evaluate this expression is $2$. Note that the expression normal form, refers to the form of an expression which cannot be reduced any further.