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.

      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.

      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.

Interactive programming in GHCI

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

String representations of values

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 escape 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 not 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])
    '['

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

    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"

    take 3 (iterate show "")

Don’t care arguments

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

    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.

    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: _

Special floating point values

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 Not 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"

    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.

Data structures and Functional Pipelines

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.

    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

    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.

    [(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.

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

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

    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),

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

Haskell Data Structures

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.

Declaring a record type

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
        }

Creating a record

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

Accessing a field in a record

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.

Modifying a field in a record

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.

    -- 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 }

Anatomy of a Haskell Program