PHYS 2411: Computational Science

Coding Overview I

We will use a programming language called Haskell. This overview tells all you need to know about Haskell in order to do the first set of exercises. The Haskell Wikibook https://en.wikibooks.org/wiki/Haskell is an excellent resource to learn the basics of Haskell. In particular the chapter "Haskell Basics" will be useful at the beginning of the course. Another good resource is Learning Haskell by Gabriele Keller and Manuel M T Chakravarty: http://learn.hfm.io/. If you want to know more about the language, you may look at the tutorials in http://www.haskell.org/

Software Tools for Coding

Editor: An editor is a program that lets you write your code and save it to a file. It usually has features such as syntax highlighting, which marks keywords and other syntax markers in different colors. You can choose among many different editors which one to use. We recommend the following:

In Windows, use Notepad++

In OSX, use Atom

In Linux, use Emacs

Note: Indentation is important in Haskell, and tabs do not keep files properly indented. You need to change your editor settings to make it use spaces when you press the Tab button. For example, in Notepad++ go to Settings/Preferences, then choose Tab settings at the left box and check the Replace by space option.

Terminal: A terminal is a window where you can give instructions to the computer directly without going through menus or intermediate apps. Terminals are commonly used by programmers, system administrators and other computing professionals. We will use a terminal to connect to a remote server via SSH. Some systems, like MACs, come with a terminal pre-installed. In other systems, such as Windows, you need to install a third party terminal program such as Git Bash.

Compiler and Libraries: The Haskell Platform package contains the Haskell compiler and common system libraries. A compiler is a program that translates the code you write into executable machine instructions. The compiler included in the Haskell Platform is called GHC. A library is a collection of pre-defined functions that makes it easier to write programs without having to reinvent the wheel each time.

A complete Haskell program must always have an entry named main, which marks where the program starts.

Interpreter: A program that is not yet finished can still be tested in an interpreter. Unlike a compiler, an interpreter executes only small pieces of your code at a time, and you can run your code even if your program does not have an entry named main. You load your code into the interpreter and then use any function in it by giving it appropriate arguments. While an interpreter is more flexible than a compiler, it is slower and requires more work on your part to run a finished program. Also, some graphical programs cannot be run within an interpreter.

The interpreter included in the Haskell Platform is the following:

In Windows, we use WinGHCi

In OSX and Linux, we use ghci inside a terminal

Haskell Syntax

A Haskell program is a list of definitions. Each definition binds a name to the value it represents. There are two possible types of definitions: constants and functions.

Haskell syntax is similar to algebra, but there are some differences:

Item Algebra Haskell

Symbolic names

Single letter

Name can be long

Latin or Greek alphabet

Use Latin alphabet only

Uppercase or lowercase

Must start with lowercase letter

Other subscripts and

May only have letters, numbers,

superscripts are common

underscores (_) and primes (')

x = α'

my_value1 = alpha'

Multiplication

No symbol between factors

Needs * between factors

2xy + 3y(z+2)

2*x*y + 3*y*(z+2)

Exponents

Denoted as a superscript

Integer exponents use ^: x^2

Real exponents use **: x**0.5

Functions

Arguments enclosed in ( )

Arguments usually follow name

Separated by commas

Separated by spaces

f(x,y) = g(x,y) + 1

f x y = g x y + 1

However, this also works:
f(x,y) = g(x,y) + 1

Variables

A variable is defined by giving a name, an equal sign and a value. Example:

    distance_travelled = velocity * time_elapsed

In this example, the variable with name distance_travelled is defined as the product of the values of two variables, velocity and time_elapsed, which should be defined somewhere else in the program. Once a variable is defined, its value cannot be changed. A variable is just a way to give a symbolic name to a value.

Every Haskell program must contain a definition for a special variable named main, which is the entry point where execution of the program will start. For example, this is the Haskell version of the usual HelloWorld program, which prints "Hello, World!" to the standard output:

    main = putStrLn "Hello, World!"

Functions

A function is defined by giving a name followed by one or more parameters, an equal sign and a value. The value is an expression that may contain the function parameters, constants defined elsewhere, literal values and other functions.

The usual style in Haskell is to have all the parameters separated by spaces after the function name. This style is called Curried. Here is an example of a definition of a function with two parameters in Curried style:

    f x y = 2 * g x a – 3 * g b y

This example shows the definition of a function named f, which takes two parameters, x and y. The value of the function is an expression that contains the parameters, the two constants a and b, the function g, and the literal values 2 and 3. Given the values of x and y, the value of f is calculated by subtracting two terms. The first term is the product of the number 2 and the value of the function g applied to the arguments x and a, and the second term is the product of the number 3 and the value of the function g applied to the arguments b and y.

Parameters in a function definition can also be specified in a more conventional style, where they are enclosed in parentheses and separated by commas. This style is called Cartesian. Even though Cartesian style is common in mathematics and most programming languages, Haskell programmers prefer Curried style because it is more flexible, as explained below. The previous example in Cartesian style looks like this:

    f(x,y) = 2*g(x,a) – 3*g(b,y)

Please note that you cannot mix the two styles in the same function. A function defined in Cartesian style must always have its parameters in parentheses, and a function defined in Curried style must always have its parameters without parentheses. You may, however, define some functions in Cartesian style and other functions in Curried style, as long as you always use them in the same style you defined them. Functions with a single parameters are not subject to this restriction, because the expressions f(x) and f x are treated the same way by the Haskell compiler.

When you introduce a new constant or function definition in Haskell, you must put the name you want to define on the left hand side of your equation, not on the right hand side. Here are some examples:

Goal Correct Incorrect

Define constant x

x = y + z

y + z = x

Define function f

f x = 2*x

2*x = f x

Definitions are usually written in separate lines. However, it is also possible to write several different definitions in a single line if you separate them with semicolons.

Types

In Haskell, as in most other programming languages, the Int 2, the Float 2.0 and the Double 2.0 have different internal representations. In a given Haskell expression, all constants and literals must have the same type. The Haskell compiler tries to infer the type for expressions containing literal numbers. A literal number is assumed to be of type Double if it includes a decimal point or if it occurs within an expression that contains other numbers of type Double. An expression consisting of just a literal number without decimal point is assumed to be of type Int. In all other cases, the compiler will look at the definitions of constants and functions in an expression and will follow the dependency chain until it can determine their types.

For example, given these definitions:

    a = b + 2

    b = 7.3

the compiler infers that b must be Double because its value is a literal number with a decimal point, and then it infers that a must also be Double because it depends on b.

Float types are not inferred automatically by default, so you must explicitly declare them:

    x = 2 :: Float

There are other composite and non-numeric types in Haskell, such as lists, tuples, Booleans and strings, which will be described later on.

Operators

An operator is just a function with a special syntax. Its name consists of special symbols instead of letters, and it is placed between its arguments instead of before the arguments. Apart from that, operators behave exactly like functions. In fact, you can place an operator before its arguments if you enclose it in parentheses:

3 + 5

is the same as:

(+) 3 5

Many operators are already pre-defined, but you can create your own operators too. The most important pre-defined operators are explained in this document.

Comments

Comments are text included in a program but intended for humans, not for the computer. To make the computer ignore a line with comments, start it with two consecutive dashes: --

    -- This is a comment line and will not be executed

Comments are sometimes used as a quick and dirty way to temporarily disable some parts of the code. This is a useful practice while you are writing your code, but you should remove commented out code from your final program. On the other hand, you should have enough comments (text, not code) in your final program to explain anything that would not be immediately obvious to a reader of your code.

Function signatures

Function signatures allow us to explain succinctly what type of input arguments a function has and what type of output it returns. The types are separated by arrows, where the output type is the last type listed and all the others correspond to the input types. Signatures are also known as type annotations.

For example, the following signature denotes that the function f is a function of two arguments, where the first argument is an integer and the second argument is a double precision number. The function returns a list of double precision numbers that it creates from those arguments:

    f :: Int -> Double -> [Double]

Type annotations are not executable code, as they only contain information about what the data is, not about how to compute it. However, unlike comments, the Haskell compiler reads the type annotations and uses the information in them to generate better executable code. Therefore, type annotations are intended for both humans and computers.

Eliminating parentheses

A common pattern in functional programming is having a chain of functions that are applied successively. In mathematics, this is called function composition. The composition operator (.) is also used to reduce the number of parentheses. It is defined as:

    (f . g) x = f (g x)

You can use the composition operator to write expressions such as f(g(h(x))) in an equivalent but more idiomatic form with fewer parentheses: (f.g.h) x

Remember that those expressions execute backwards, as they instruct the computer to apply the function h to the value x first, then the result is fed into the function g, and the result of that is finally fed into f.

Note that it is not always possible to eliminate all parentheses, but using constructions like this makes expressions more readable in general.

Local Definitions

To avoid pollution of the global namespace, it is recommended to use as few global definitions as possible. If a definition is used only inside a function, it can be defined local to that function. There are two syntactic styles to denote local definitions: let-in-blocks and where-blocks. Both let-in-blocks and where-blocks need to be indented to the right.

A let-in block starts with the keyword let, followed by the local definitions, and ends with the keyword in. The let-in block must be the first construction in the body of a definition (i.e., it must be placed right after the = symbol).

In the following example, x is defined via auxiliary constants i and j. The resulting value for x is 5.

    x =

        let

        i = 2

        j = 3

        in

        i+j

A where-block must be placed at the end of a definition. Here is the same example with a where-block:

    x = i+j

        where

        i = 2

        j = 3

The local definitions cannot be used outside the function where they are placed.

Conditionals: Guards and if/then/else

Guards are indicated by pipes following a function's name and its parameters. Usually, they are indented a bit to the right and lined up. After each pipe there is a boolean expression. If it evaluates to True, then the corresponding expression is used for the function. If the boolean expression is False, then the next guard is check and so on until all the guards are considered. For example, the absolute function can be written as:

absolute x
    | x < 0     = - x
    | otherwise = x

In the if/then/else expressions, first the if condition is evaluated. If the condition is True the expression after the then is the value. Otherwise (if the condition is False), the construct evaluates to the else expression. Haskell always requires both a then and an else clause. The statement must return a value of the same type in both cases. if/then/else constructions can replace guards and viceversa. For example, the absolute function using if/then/else statements can be written as:

absolute x =
    if x < 0
       then -x
       else  x

Lists

In Haskell, you can group several items into a list and use the list as a single item. All items in a list must have the same type, so, for example, you cannot mix integers and strings in the same list. You can deconstruct a list into separate constants, but the number of constants must match the length of the list. Example:

    list1 = [2,3,5,7] -- list1 is constructed

    [a,b,c,d] = list1 -- list1 is deconstructed into separate constants

The previous equations will make a=2, b=3, c=5, d=7 and list1=[2,3,5,7]

The list [] denotes a list that has no elements.

The cons (:) operator lets you add an element to the front of a list:

    2 : [3,4,5] -- The result is the list [2,3,4,5]

Besides being an operator, cons is also a special pattern that can be used to deconstruct lists:

    x : y = [2,3,4,5] -- This results in x=2, y=[3,4,5]

Two lists can be concatenated with the (++) operator. For example, list1 and list2 below are exactly the same lists.

    list1 = [2,3] ++ [4,5]

    list2 = [2,3,4,5]

There is no operator for adding elements at the end of a list, but you can still do it by using concatenation:

    [3,4,5] ++ [6] –- The result is the list [3,4,5,6]

When constructing and deconstructing lists, what you have on each side of the equal sign depends on your goal, as the following table illustrates:

Goal Correct Incorrect

Define a and b

[a,b] = p

p = [a,b]

Define p

p = [a,b]

[a,b] = p

Ranges

A range is a special type of list containing consecutive numbers. The most general form of a range is the expression [a,b..c], which represents a list of either increasing numbers (when a < b) or decreasing numbers (when a > b.) In the increasing case, the list consists of numbers x of the form x = a + k*(b-a) for a non-negative integer k, such that x satisfies the inequalities a <= x and x <= c+(b-a)/2. The decreasing case is similar but with the inequality symbols reversed. The value a must always be present, but the values b and c are optional. If b is missing, it is assumed to be +1. If c is missing, then the list is infinite. When a, b and c are integers, the last number in the list will always be c, but when they are not integers, the last number may be greater (or, in the decreasing case, less) than c. This behavior minimizes the error in many discretization algorithms, and that is the reason why it was chosen this way.

Examples of ranges:

    [1..5] –- Same as [1,2,3,4,5]

    [2,4..10] –- Same as [2,4,6,8,10] (increment is 2)

    [0.1,0.2..1] –- Same as [0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0]

    [1..] -- Same as the infinite list of all positive integers

    [5,4..1] -- Same as [5,4,3,2,1] (The increment is -1)

    [3..1] -- Same as [] (because no integer n satisfies 3 <= n <=1.5)

    [0.1..1.6] -- Same as [0.1,1.1,2.1] (note that 2.1 <= 1.6+0.5 )

    [0.1..1.5] -- Same as [0.1,1.1] (note that 1.1+1 > 1.5+0.5 )

List Comprehensions

You can also create lists by picking those elements from another list (called the base) that satisfy some condition, and then applying some transformation to the chosen elements. For example, to create the list

    [(2,3),(3,4),(5,6),(6,7)]  

you can write the following list comprehension:

    [(x,x+1) | x <- [2..6], x /= 4 ] –- The base is the list [2..6]

You can read that as: the list of pairs (x,x+1) such that x is taken from the base [2..6] and x is not 4.

The compiler converts ranges and list comprehensions into internal low-level loops, so be aware that some list comprehensions may be slow to calculate, and if you use them with an infinite list as the base it is possible for the calculation to never terminate. For example, this list comprehension will never terminate:

    [x | x <- [1..], even(x), x<100]

In the expression above, the program will generate an infinite list of positive integers, and then select those elements from the list that are even and also less than 100. The problem is that the computer does not know that it can safely stop its search as soon as it reaches 100, so it will keep checking all numbers up to infinity in case it finds one that is less than 100. Instead, you should use one of these alternative, terminating expressions:

    [x | x <- [1..100], even(x)] -- The base list is finite

    takeWhile (< 100) [x | x <- [1..],even(x)] -- takeWhile handles infinite lists well

The function takeWhile searches a list to pick elements that satisfy a given condition, and it stops the search as soon as it finds an element that does not satisfy the condition.

List Comprehensions with multiple indices

A list comprehension is a compact way to specify a loop that transforms a base list into a new list. List comprehensions can use more than one index. For example, this list comprehension

    [(i,j) | i <- [1,2,3], j <- [11,12,13,14]]

results in the list of pairs of all values of i combined with all values of j:

    [(1,11),(1,12),(1,13),(1,14),(2,11),(2,12),(2,13),(2,14),(3,11),(3,12),(3,13),(3,14)]

You can also combine several lists into one by using parallel list comprehensions. If you use vertical bars instead of commas to separate the indices, the indices run in sync with each other instead of independently. For example, the following parallel list comprehension

    [(i,j) | i <- [1,2,3] | j <- [11,12,13,14]]

results in the list [(1,11),(2,12),(3,13)]

Note that the first element of the first list is combined with the first element of the second list, then the second elements of each list are combined, and so on, until the shortest list is covered. Parallel list comprehensions can use more than two indices and can also use infinite lists as bases. Here is another example:

    [x+y+z | x <- [1..] | y <- [3,4,5] | z <- [100,100] ] -- Result is [104,106]

Warning: do not mix commas and vertical bars in a list comprehension with multiple indices, because the result is usually not what you expect.

To use parallel list comprehensions in your program, you need to include the following line at the top of your file:

    {-\# LANGUAGE ParallelListComp \#-}

In ghci, you need to do the following before using parallel list comprehensions:

    :set -XParallelListComp

Strings

In addition to numbers, you can manipulate other objects such as literal character strings, which you can use, for example, to print messages in your program. String literals are enclosed in double quotes, but single character literals are enclosed in single quotes. A string is just a list of single characters. For example, greeting1 and greeting2 below are the same string:

    greeting1 = “hello”

    greeting2 = [‘h’, ’e’, ’l’, ’l’, ’o’]

Strings can be concatenated with the (++) operator. For example, text1 and text2 below are the same exact text:

    text1 =Once upon “ ++ “a time”

    text2 =Once upon a time”

Type conversions between integer and floating point numbers

Haskell does not implicitly convert numbers between integer and floating point types in either direction. All conversions must be explicit. To convert from an integer to a floating point type (i.e., Float or Double,) use the function fromIntegral. To convert from a floating point type to an integer, you can use either truncate, floor, ceiling or round.

    fromIntegral :: Int -> floating_point

    fromIntegral 4 -- Result is 4.0

Convert an integer to a floating point type

    truncate :: floating_point -> Int

    truncate 4.2 -- Result is 4

    truncate (-4.2) -- Result is -4

truncate x returns the integer nearest x between zero and x

    round :: floating_point -> Int

    round 4.5 -- Result is 4

    round 5.5 -- Result is 6

round x returns the nearest integer to x; the even integer if x is equidistant between two integers

    ceiling :: floating_point -> Int

ceiling x returns the least integer not less than x

    floor :: floating_point -> Int

    floor 4.2 -- Result is 4

    floor (-4.2) -- Result is -5

floor x returns the greatest integer not greater than x

Input and Output operations

Input and output operations (IO) in Haskell cannot be mixed with regular computations. IO operations are usually performed inside a do-block, which is a block of lines that follow the keyword do. The most common output operations are putStr, putStrLn and writeFile. The most common input operations are getLine, getArgs and getProgName. A more comprehensive list of IO operations can be found in the Prelude documentation:

    putStr :: String -> IO ()

Write a string to the standard output. The type of the output is IO (), which means that this function is actually an IO operation and not a regular function. The () after IO means that no result is returned to the program after the IO is performed.

    putStrLn :: String -> IO ()

Write a string and then a newline character to the standard output

    writeFile :: String -> String -> IO ()

    writeFile filename content

Write the string content to the file named after filename. This operation overwrites the previous contents of the file.

    getLine :: IO String

    line <- getLine

A line is read from the standard input and the content of the line (without the newline character) is saved into the string constant line. The type IO String means that this is an IO operation that results in a string returned to the program. The symbol <- is used to indicate that the result of this IO operation is saved into the constant preceding the symbol.

    getArgs :: IO [String]

    args <- getArgs

This operation returns the command-line arguments passed to the program as a list of strings, which, in the example above, are saved into the constant args. The name of the program is not returned by this operation.

    getProgName :: IO String

    prog <- getProgName

This operation returns the name of the program, which is saved into the string prog.

To use getArgs and getProgName in a program, you must include the following line at the beginning:

    import System.Environment(getArgs,getProgName)

In a do-block, normal function and constant definitions do not work. If you need to define a regular function or a constant inside a do-block, you must precede it with the keyword let. If you want to save the content of an input operation into a constant, use the symbol <- instead of = to define it. In general, you can define regular functions inside IO blocks, but you cannot use IO operations inside regular functions. Some examples of correct and incorrect syntax follow.

If you Goal is to define a regular constant inside a do-block

    let x = 5  -- Correct inside a do-block 
    x = 5      -- Incorrect inside a do-block 

If you Goal is to save the standard input into a constant

    x <- getLine   -- Correct
    x = getLine   -- Incorrect  

To print a variable inside a regular function, e.g., for debugging is not possible. For example this piece of code is incorrect:

    f x y =              -- Incorrect piece of code
        putStrLn x
        putStrLn y
        x – 2*y
    putStrLn (show (f 2 5))

The correct way to do it is to define a regular function inside a do-block:

    debug_f x y = do  -- Correct piece of code
       putStrLn x
       putStrLn y
       let f x y = x – 2*y
       putStrLn (show (f x y))
    debug_f 2 5

Formatting with printf

Haskell includes a printf function that behaves like the equivalent C function. To use it in a program, include the following line at the beginning:

    import Text.Printf(printf)

Details of the function can be found at the Prelude documentation

Examples:

    printf "(%f,%f)" 2 3.5 -- Result is the string "(2.0,3.5)"

    printf “(%d,%g)” 5 0.0001 -- Result is the string “(5,1.0e-4)”

Understanding and fixing compiler errors

When you make mistakes in your code, the compiler will produce an error message. Sometimes, error messages are long, and they may be confusing to inexperienced programmers. If you follow the advice here, you will be able to understand and fix the errors faster.

  1. Do not despair. Be willing to spend the time necessary to fix the error.

  2. Read the error message entirely, even if you do not understand any of it. You will on time.

  3. Go to the first error shown in your message. There is usually more than one error.

  4. Look at the first line in your message. It shows the name of the file where the error was found followed by two numbers: the line and the column in that file.

  5. Look at the file, line and column where the error occurred.

  6. Check that the indentation is correct. This is the number 1 cause of errors.

  7. Check for typos. This is number 2 cause of errors.

  8. Check for indentation and typos again. This is number 3 cause of errors.

  9. If the message mentions “parse error”, then the problem is most likely wrong indentation or typos. Check lines above the error line, as sometimes the error is before that line.

  10. If the message mentions “No instance of” or “Couldn’t match type”, then the problem is that you are using the wrong value in some of the constants mentioned in the error message. Try to understand the message, as it is giving you the information you need to fix the error.

  11. The probability of the compiler being wrong is extremely small, so if it says you have an error, look for it until you find it. People make mistakes often. Computers do not.

  12. Add type annotations to the functions where you suspect the error is. Type annotations will help the compiler produce error messages that are easier to understand.

Useful Functions

This section lists a selection of utility functions that are very common. The first line of each entry below is the function signature. The next few lines are examples of use with concrete inputs and outputs. The last line shows the use of the function in a definitional context, which is followed by an explanation in the lines below it.

    break :: (a -> Bool)-> [a] -> ([a], [a])

    break (> 3) [1,2,3,4,1,2,3,4] -- Result is ([1,2,3],[4,1,2,3,4])

    break (< 9) [1,2,3] -- Result is ([],[1,2,3])

    break (> 9) [1,2,3] -- Result is ([1,2,3],[])

    (listnotp, listp) = break p xs

break, applied to a predicate p and a list xs, returns a pair where first element is longest prefix (possibly empty) of xs of elements that do not satisfy p and second element is the remainder of the list. break p is equivalent to span (not . p).

    concat :: [[a]] -> [a]

    concat [[1],[2],[3,4,5]] -- Result is [1,2,3,4,5]

    concat ["Hello, ", "how ", "are ", "you?"] -- Result is "Hello, how are you?"

concat concatenates all the elements of a list of lists. Since a string is just a list of characters, you can also concatenate a list of strings, as in the last line.

    concatMap :: (a -> [b]) -> [a] -> [b]

    -- The example below results in [0,2,1,3,2,4,3,5]

    concatMap f [1,2,3,4]

          where f x = [x-1,x+1]

concatMap maps a function over all the elements of a list and concatenate the resulting lists.

    cycle :: [a] -> [a]

    cycle [1,2,3,4] -- Result is [1,2,3,4,1,2,3,4,1,2,3,4,...]

cycle ties a finite list into a circular one, or equivalently, the infinite repetition of the original list.

    drop :: Int -> [any] -> [any]

    drop 6 "Hello World!" -- Result is "World!"

    drop 3 [1,2,3,4,5] -- Result is [4,5]

    drop 3 [1,2] -- Result is []

    drop 3 [] -- Result is []

    drop (-1) [1,2] -- Result is [1,2]

    drop 0 [1,2] -- Result is [1,2]
    
    new_points = drop n points

drop n xs returns the suffix of xs after the first n elements, or [] (empty set) if n >length xs. The last line creates the list new_points, which contains the same elements as the list points, except that the first n elements of points are deleted and do not appear in new_points.

    dropWhile :: (a -> Bool) -> [a] -> [a]

    dropWhile (< 3) [1,2,3,4,5,1,2,3] -- Result is [3,4,5,1,2,3]

    dropWhile (< 9) [1,2,3] -- Result is []

    dropWhile (< 0) [1,2,3] -- Result is [1,2,3]

dropWhile p xs returns the suffix remaining after takeWhile p xs. It stops after it finds the first element of xs that does not satisfy p, which becomes the first element of the returned list.

    filter :: (a -> Bool) -> [a] -> [a]

    filter (<= 3) [1,3,5,7,5,3,1] -- Result is [1,3,3,1]

    filter p xs = [ x | x <- xs, p x]

filter, applied to a predicate and a list, returns the list of those elements that satisfy the predicate. It is an alternative to using conditions in list comprehensions. Unlike takeWhile, the function filter does not stop until the end of the list is reached, so it must be used with caution in infinite lists.

    foldl :: (accum -> any -> accum) -> accum -> [any] -> accum

    foldl (+) 0 [3,4,5,6] -- result is: 18

    total = foldl reduction initial values

The function foldl (with the letter l at the end) is known as reduce in other languages. It implements a loop with accumulator pattern that is common in many algorithms. An accumulator is initialized with the value initial, and then its value is successively updated by combining each element of the list values with the current value of the accumulator. The l means that the accumulator go through the list from left to right. The function reduction is used to perform the combination. Typical reductions are addition and multiplication. A reduction must be associative, so that the result is independent of the implementation.

    head :: [a] -> a

    head [7,5,1,2] -- Result is 7

    head [] -- Produces a run-time error

head extracts the first element of a list, which must be non-empty.

    init :: [a] -> [a]

    init [1,2,3,4] -- Result is [1,2,3]

    init [1..] -- Result is [1..]

    init [] -- Produces a run-time error

init creates a new list with all the elements of the original list except the last one. The list must be non-empty.

    iterate :: (any -> any) -> any -> [any]

    iterate (+3) 7 -- result is: [7,10,13,16,19,…]

    iterations = iterate f x -- Result is [x, f x, f (f x), ...]

iterate f x returns an infinite list of repeated applications of f to x. The infinite list iterations is [x,f(x),f(f(x)),f(f(f(x))),...], i.e., it is the list that results from iterating the function f with argument x zero times, once, twice, three times, and so on.

    last :: [a] -> a

    last [7,5,1,2] -- Result is 2

last extracts the last element of a list, which must be finite and non-empty.

    length :: [any] -> Int

    length [] -- Result is 0

    length [1,2,3,4] -- Result is 4

    length [1..] -- Infinite loop (program gets stuck here)

    length [2,2,2,2,2] -- result is: 5

    l = length lst

length returns the length of a finite list as an integer Int. length lst computes the number of elements in the list lst.

    map :: (a -> b) -> [a] -> [b]

    map sqrt [1,4,9,16,25] -- result is: [1,2,3,4,5]

    map f [x1, x2 .. xn] -- Result is [f x1, f x2 .. f xn]
    
    outputs = map f inputs

map f xs is the list obtained by applying f to each element of xs. In map f inputs the function f is applied to each element of the list inputs, and the results are collected into the list outputs.

    null :: [a] -> Bool

    null [] -- Result is True

    null [1..] -- Result is False

null tests whether the structure is empty.

    repeat :: any -> [any]

    repeat 7 -- result is: [7,7,7,7,7…]

    repeat 3 -- Result is [3,3,3,3,…]

    repeated = repeat x

repeat x is an infinite list, with x the value of every element. The list repeated is an infinite list in which each element is equal to x.

    replicate ::Int-> a -> [a]

replicate n x is a list of length n with x the value of every element.

    reverse :: [a] -> [a]

    reverse [] -- Result is []

    reverse [1,2,3,4] -- Result is [4,3,2,1]

reverse xs returns the elements of xs in reverse order. xs must be finite.

    scanl :: (accum -> any -> accum) -> accum -> [any] -> [accum]

    scanl (+) 0 [3,4,5,6] -- result is: [0,3,7,12,18]

    partials = scanl reduction initial values

The function scanl works like foldl (see above.) The only difference is that scanl creates a list with all the partial values of the accumulator instead of returning just the total. Note that the last element of partials is always the value returned by foldl. Scanl goes through the list from left to right.

    show :: number -> String

    show 5 -- result is: "5"
    
    text = show num

show converts a number in a string. For example, the string text is the textual representation of the number num.

    span :: (a -> Bool) -> [a] -> ([a], [a])

    span (< 3) [1,2,3,4,1,2,3,4] -- Result is ([1,2],[3,4,1,2,3,4])

    span (< 9) [1,2,3] -- Result is ([1,2,3],[])

    span (< 0) [1,2,3] -- Result is ([],[1,2,3])

span, applied to a predicate p and a list xs, returns a pair where the first element is the longest prefix (possibly empty) of xs of elements that satisfy p and second element is the remainder of the list. span p xs is equivalent to the tuple (takeWhile p xs, dropWhile p xs).

    splitAt :: Int -> [a] -> ([a], [a])

    splitAt 6 "Hello World!" -- Result is ("Hello ","World!")

    splitAt 3 [1,2,3,4,5] -- Result is ([1,2,3],[4,5])

    splitAt 1 [1,2,3] -- Result is ([1],[2,3])

    splitAt 3 [1,2,3] -- Result is ([1,2,3],[])

    splitAt 4 [1,2,3] -- Result is ([1,2,3],[])

    splitAt 0 [1,2,3] -- Result is ([],[1,2,3])

    splitAt (-1) [1,2,3] -- Result is ([],[1,2,3])

splitAt n xs returns a pair where first element is xs prefix of length n and second element is the remainder of the list. It is similar to (take n xs, drop n xs) for finite n.

    sum :: [number] -> number

    sum [1,2,3,4] -- result is: 10

    total = sum weights

The sum function computes the sum of the numbers of a list. In the example the number total is the sum of the numbers in the list weights. Note that the function sum can be implemented in terms of foldl as follows: sum numbers = foldl (+) 0 numbers.

    tail :: [a] -> [a]

    tail [1,2,3,4] -- Result is [2,3,4]

    tail [1..] -- Result is [2..]

    tail [] -- Produces a run-time error

tail extract the elements after the head of a list, which must be non-empty.

    take :: Int -> [any] -> [any]

    take 2 [1,2,3,4,5] -- result is: [1,2]

    take 5 "Hello World!" -- Result is "Hello"

    take 3 [1,2,3,4,5] -- Result is [1,2,3]

    take 3 [1,2] -- Result is [1,2]

    take 3 [] -- Result is []

    take (-1) [1,2] -- Result is []

    take 0 [1,2] -- Result is []

    extracted_points = take n points

take n, applied to a list xs, returns the prefix of xs of length n, or xs itself if n > length xs. In the example, the list extracted_points consists of the first n elements of the list points, which are copied into a new list. Note that the original list points is not modified in this process.

    takeWhile :: (a -> Bool) -> [a] -> [a]

    takeWhile (< 3) [1,2,3,4,1,2,3,4] -- Result is [1,2]

    takeWhile (< 9) [1,2,3] -- Result is [1,2,3]

    takeWhile (< 0) [1,2,3] -- Result is []

takeWhile, applied to a predicate p and a list xs, returns the longest prefix (possibly empty) of xs of elements that satisfy p. It stops after finding the first element that does not satisfy p, which is not returned. This function, when combined with infinite list comprehensions, provides a functionality similar to a while loop in other languages.

    (++) :: [any] -> [any] -> [any]

    [1,2,3] ++ [4,5] -- result is: [1,2,3,4,5]

    [1 .. 4] ++ [11 .. 13] -- Result is [1,2,3,4,11,12,13]

    [1..4] ++ [100, ...] -- Result is [1,2,3,4,100,101,102,...]

    [1..] ++ [4,5,6,7] -- Result is [1..]

    combined = list1 ++ list2

(++) appends two lists. If the first list is not finite, the result is the first list. In the example, the new list combined contains the concatenation of a copy of list1 with a copy of list2. Note that the original lists are not modified. This operator actually works on any list, including on strings.

    (!!) :: [a] -> Int -> a

    [1,2,3,4] !! 1 -- Result is 2

    [] !! 0 -- Produces a run-time error

    [1,2,3] !! 10 -- Produces a run-time error

    [0..] !! 100 -- Result is 100

(!!) is the list index (subscript) operator, starting from 0.