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/
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 preinstalled. 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 predefined 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
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 



Exponents 
Denoted as a superscript 
Integer exponents use ^: 
Real exponents use **: x**0.5 

Functions 
Arguments enclosed in ( ) 
Arguments usually follow name 
Separated by commas 
Separated by spaces 




However, this also works:  
f(x,y) = g(x,y) + 1 
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!"
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 







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.
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 nonnumeric types in Haskell, such as lists, tuples, Booleans and strings, which will be described later on.
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 predefined, but you can create your own operators too. The most important predefined operators are explained in this document.
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 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.
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.
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: letinblocks and whereblocks. Both letinblocks and whereblocks need to be indented to the right.
A letin block starts with the keyword let, followed by the local definitions, and ends with the keyword in. The letin 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 whereblock must be placed at the end of a definition. Here is the same example with a whereblock:
x = i+j
where
i = 2
j = 3
The local definitions cannot be used outside the function where they are placed.
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
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 
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*(ba)
for a nonnegative integer k
, such that x
satisfies the inequalities a <= x
and x <= c+(ba)/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 )
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 lowlevel 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.
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
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”
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 (IO) in Haskell cannot be mixed with regular computations. IO operations are usually performed inside a doblock, 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 commandline 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 doblock, normal function and constant definitions do not work. If you need to define a regular function or a constant inside a doblock, 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 doblock
let x = 5  Correct inside a doblock
x = 5  Incorrect inside a doblock
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 doblock:
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
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.0e4)”
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.
Do not despair. Be willing to spend the time necessary to fix the error.
Read the error message entirely, even if you do not understand any of it. You will on time.
Go to the first error shown in your message. There is usually more than one error.
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.
Look at the file, line and column where the error occurred.
Check that the indentation is correct. This is the number 1 cause of errors.
Check for typos. This is number 2 cause of errors.
Check for indentation and typos again. This is number 3 cause of errors.
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.
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.
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.
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.
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 = [x1,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 runtime error
head extracts the first element of a list, which must be nonempty.
init :: [a] > [a]
init [1,2,3,4]  Result is [1,2,3]
init [1..]  Result is [1..]
init []  Produces a runtime error
init creates a new list with all the elements of the original list except the last one. The list must be nonempty.
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 nonempty.
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 runtime error
tail extract the elements after the head of a list, which must be nonempty.
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 runtime error
[1,2,3] !! 10  Produces a runtime error
[0..] !! 100  Result is 100
(!!) is the list index (subscript) operator, starting from 0.