index | submit | rank | book

Computer Science by Example

<< 3. Programming Basics   |   4. Programming   |   5. Mathematical Foundations >>

4. Programming

Equipped with the programming basics, we will now learn programming in more depth. We will review all concepts of the previous chapter but try to deepen our understanding. We will also go through some new concepts such as lists, arrays and structured data types.

4.1. Data types

As we have seen in the previous chapter, in programming, we manipulate data of different types. Here are some standard data types used in programming:

There are other data types not mentioned here and it is also possible for programmers to define their own data types. This will be discussed later in the book.


Please jump to the section describing the types available in the language of your choice.

In Python, we can check the type, or class, of a value using the function type. See the interactive session below:

$ python
>>> type(360)
<class 'int'>
>>> type(3.14)
<class 'float'>
>>> type("Some text")
<class 'str'>
>>> type('Some text')
<class 'str'>
>>> type(False)
<class 'bool'>
>>> type(True)
<class 'bool'>
>>> type([1,2,3])
<class 'list'>

Here are some common types and how to use them:

  • int: the type of integers. They are usually written in decimal notation: 1, 12, 360, etc.

  • float: the type of floating point numbers, They are usually written in decimal notation: 1.0, 3.14, etc.

  • str: the type of strings. They are written either between single-quotes (') or double-quotes ("): "Hello, World!", 'A message', etc. In Python, there is no character type. These are usually represented by a string containing a single value: 'a', "b", "?", etc.

  • bool: the type of booleans or truth values. Either True or False.

  • list: the type of lists of values. They are written with values between square brackets separated by commas. In Python, lists can be heterogeneous, that is, have values of different types in a single list. Examples are: [1,2,3], [3,1,2], [False, "Message", 3.14].

In C, the type of a variable is present upon its declaration, see:

char c;
int x;
float f;

Here are some common C types:

  • int: the type of integers. They are usually written in decimal notation: 1, 12, 360, etc.

  • float: the type of floating point numbers, They are usually written in decimal notation: 1.0, 3.14, etc.

  • char: the type of characters. They are written between single-quotes ('): 'a', 'B', '?', ' ', etc.

  • booleans: we use integers to represent boolean values. By convention, the integer 0 is considered “false” and any other integer considered “true”. The default “true” value is 1.

  • arrays: An array is a sequence of values of the same type. Most of the times, arrays have a fixed size. An array is declared using the following notation:

      <type> <name>[<size>];
    

    For example, to declare an array of 10 integers, we do:

      int values[10];
    
  • strings: strings are just arrays of characters terminated by the null character '\0'. We declare a string variable that can hold up to 30 characters like so:

      char name[31];
    

    We can also write strings directly in code between double-quotes: "Hello, World!", "abcd", etc. When we write strings like this, the null character is implicit '\0'.

In Haskell, it is good practice to add type annotations to top level declarations even though they are optional. We declare types with the type binding operator :: which can be read as “has the type”:

pi :: Float
pi = 3.141592

The above can be read as: pi has the type Float; pi is 3.141592.

Here are some common Haskell types:

  • Int: the standard type of integers. They are usually written in decimal notation: 1, 12, 360, etc.

  • Float: the type of floating point numbers, They are usually written in decimal notation: 1.0, 3.14, etc.

  • Char: the type of characters. They are written between single-quotes ('): 'a', 'B', '?', ' ', etc.

  • [a]: the type of lists. They are written between square brackets ([]): [1,2,3], ['a','b','c']. Lists in Haskell are homogeneous: they can only hold items of the same type. Here are some common list types: [Int], [Float], [Char], [String].

  • String: the type of strings. They are written between double-quotes ("): "Hello, World!", "abcd". The String type is an alias to the [Char] type: strings are just lists of characters. Saying "abcd" is the same as saying ['a','b','c','d'].

  • IO: the type of IO actions, that is, functions or commands that perform IO. The main function has this type.

4.2. Variables

In programming, we often deal with variables. A variable has a name and a value. For example: a variable x, may have a value of 10 associated with it; a variable name, may have the value "Mary Smith" associated with it. ◻

Variables can appear as parameters or arguments to functions or as explicit declarations. Take for example the following piece of pseudo-code in an imaginary programming language:

1. function triple(integer variable x)
2.     integer variable y
3.     y <- x * 3
4.     return y

On line 1, we see an integer variable x which is the only parameter or argument to the function triple. On line 2, we see an integer variable y which is local to the function triple and receives the value of x times 3 on the third line. When we call triple with 7 as its argument, x has the value of 7 and on line 3, y becomes 21. During different times and in different contexts, x and y assume different values. ◻

Variables have a scope where they are valid. Consider the following piece of pseudo-code:

1. function quadruple(integer variable x)
2.     integer variable y
3.     y <- x * 4
4.     return y

The variables x and y only have meaning in the scope of the quadruple function, i.e.: inside the quadruple function. For example, if the functions triple and quadruple are part of the same program, the x and y inside triple are different than the x and y inside quadruple despite having the same name.

In cases where we have a scope-within-a-scope, the inner scope usually takes precedence when referencing a variable. ◻


In Python, we declare a variable by assiging a value to it like so:

<name> = <value>

For example:

x = 12

Even though we do not explicitly specify a type the variable gets one. In the above case, x is an int:

> type(x)
<class 'int'>

Variables can also appear as function arguments, for example:

def triple(x):
    y = x * 3
    return y

The above function returns the triple of the given number. We say x is the argument to the triple function and y is an explicitly declared local variable.

Variables in Python are by default mutable meaning you can update the value stored on them later in your program. ◻

In C, we declare a variable using the following notation:

<type> <name>;

For example:

int x;

We explicitly specify the type upon declaration. We may optionally give the variable a starting value, like so:

int x = 12;

Variables can also appear as function arguments, for example:

int triple(int x)
{
    int y;
    y = x * 3;
    return y;
}

The above function returns the triple of the given number. We say x is the argument to the triple function and y is an explicitly declared local variable.

Variables in C are by default mutable meaning you can update the value stored on them later in your program. ◻

In Haskell, we declare a variable using the following notation:

let <name> = <value>
in  <expression>

Where the declared variable will only be visible inside the expression after in. Even though we did not explicitly specify a type, the variable assumes one. For example:

let x = 12
in  ...

Variables can also appear as function arguments, for example:

triple :: Int -> Int
triple x  =  let y = x * 3
             in  y

The above function returns the triple of a given number. We say x is the argument to the triple function and y is an explicitly declared local variable.

An alternative to the above notation is to use a where clause:

triple :: Int -> Int
triple x  =  y
  where y = x * 3

This where clause can only appear in the context of declarations where let ... in ... can appear anywhere where we expect an expression.

Variables in Haskell are in immutable, once they assume a value it never changes. ◻

4.3. Input and output

In this section we will review input and output, picking up on where we left of on the last chapter. We will learn how to process input line by line and we will review how to read and write values of different types.

Processing input line by line

In the exercises of the previous chapter, each run of solution programs processed a single test case. Exercises in this chapter are different, each run of solution programs should process a series of test cases. This should be done usually line-by-line until the end of file (EOF).

When redirecting input using <in.txt, EOF is reached at the actual end of file. When typing input from the command line, you can simulate EOF by holding “Ctrl” and pressing “d” on Linux and Windows or by holding “Command” and pressing “d” on Mac. We use either Ctrl-D or ^D for short to express this key combination.

Now, please jump to the section with the explanation of how to process input line by line for the language of your choice.

In Python, at the beginning of your source file add:

import sys

then you can create a loop that processes input line by line using:

for line in sys.stdin:
    ...
    ...

You can read the above as: for each line in the standard input, do so and so.

Commands inside the for loop can reference the line variable which holds a line of input at each iteraction. The line variable will contain a trailing line break if present on the input. You can strip this line break with line = line.strip() if needed. ◻

In C, scanf returns the numbers of items read. So if you are reading a single integer with %i you can create a loop that processes input item by item using:

while ( scanf("%i", &x)==1 ) {
    ...
    ...
}

You can read the above as: while you are able to scan a single item from input, do so and so.

If you are reading two or three items at a time, replace ==1 by ==2 or ==3 respectively. ◻

In Haskell, you can use interact to declare the main function and implement the rest of your program with two other functions: io from String to String that processes the entire input and io1 from String to String that processes a single line of input:

io1 :: String -> String
io1 s  =  ...

io :: String -> String
io input  =  unlines (map io1 (lines input))

main :: IO ()
main  =  interact io

Details of how the above io function works will only be explained later in the book. For now do not worry about it, you can use the idiom as-is. ◻

When solving the exercises of this chapter, do not feel tempted to accumulate output and produce everything at the end. It is good practice to actually produce output as you go. As soon as your program has enough information to produce output, just do it.

Now, we go to our first exercise involving the above patterns.


Programming exercise (repeat)

Write a program that reads a series of numbers from standard input (usually the keyboard) and repeats the same numbers on standard output. Here is an example session of such a program:

$ ./repeat
1
1
2
2
3
3
123
123
^D

Example input

1
2
3
123

Example output

1
2
3
123

Hint: there is no need to accumulate input. Just print output as you go: as soon as you read the first number, just print it on standard output. ◻

Before looking at the example solutions, try to solve the exercise using the patterns shown earlier in the chapter. Try at least for a few minutes, if you are stuck, read on. ◻


Here is a flowchart with an outline for a repeat solution:

Flowchart for the `repeat` solution

While we are able to read a number x we print number x. ◻


Now, please jump to the section explaining the solution for your chosen programming language. Again, avoid copying and pasting for best results.

Yet again, do not try to learn more than one language at once: if you are planning to learn more than one programming language, first go through the book using a single language, only then start with the second. For example, first do most of the exercises in Python, only then start doing them in C.

In Python, here is how we can solve the repeat exercise:

import sys

for line in sys.stdin:
    x = int(line)
    print(x);

We follow the pattern defined earlier in this chapter of for line in sys.stdin:. For each line, we convert it to an integer x and then print it. ◻

In C, here is how we can solve the repeat exercise:

#include <stdio.h>

int main()
{
    int i;
    while (scanf("%i",&i)==1) {
        printf("%i\n",i);
    }
    return 0;
}

We follow the pattern defined earlier in this chapter. While we are able to scan an integer from input, we print the same integer on the output. ◻

In Haskell, here is how we can solve the repeat exercise:

main :: IO ()
main  =  interact io

io :: String -> String
io input  =  unlines (map io1 (lines input))

io1 :: String -> String
io1 line  =  show (solve (read line))

solve :: Int -> Int
solve x  =  x

We follow the pattern defined earlier in this chapter using interact and io to allow a function io1 to process input line by line. For each line, we read to transform it into an integer; we apply solve which basically returns the same result as its argument; and we apply show to transform it back into a string. Here are the types of read and show in the above context:

read :: String -> Int
show :: Int -> String

These may make io1 simpler to understand. ◻

Once more, please do:

  1. Compile your solution and run it locally. Does it behave as you expect it to?
  2. Submit your solution to the Online Judge. Can you get a perfect score there? ◻

Reading and writing different types

How to read and write different types will depend on the language you are using.

In Python, we usually just read strings, then convert them to whatever type we like.

As we have seen before, we read a line of input with:

line = input()

And we process several lines of input with:

for line in sys.stdin:
    ...

Each line will come with a trailing line break if present. If needed, you can remove this line break using .strip() like so:

line = line.strip()

If a line has multiple items, we can separate them on spaces with:

a, b, c = line.split()

To convert a string into integer, we do:

int(string)

For example:

string = "123"
x = int(string)

Note that the string "123" is different than the integer 123.

To convert a string into a float, we do:

float(string)

For example:

string = "123.45"
x = float(string)

Note that the string "123.45" is different than the float 123.45.

Finally, we can convert a string into a boolean using a comparison operator:

string = input('Would you like to continue? (y/n) ')
should_continue  =  string == "y"

The string will be read from standard input. The should_continue variable will be True if the user has typed y. The last line above contains both the assignment operator = and the comparison operator ==. An unambigous way to read this last line is: should_continue becomes the boolean value of whether string equals "y".

You can print strings, integers, floats and booleans using print:

print(value)

To print multiple values you can separate them by commas:

print(value1, value2, ..., valueN)

In C, we can read a line of input using the fgets function like so:

char line[100];
fgets(line, 100, stdin);

The fgets function requires you to pass the maximum size of the string, in this case 100 characters counting the terminating '\0'. It will include a line break if it is read.

Using scanf we can read several different types directly such as: strings, integers, floats and characters.

To read a single string (and stop at a space), do:

char string[100];
scanf("%99s", string);

To read a single integer, do:

int i;
scanf("%d", &i);

To read a single float, do:

int f;
scanf("%f", &f);

To read a single character, even if it is a space character, do:

char c;
scanf("%c", &c);

To read a single non-space character, skipping any spaces first, do:

char c;
scanf(" %c", &c);

To read strings we do not need the address operator &. To read integers, floats and characters we do need it. We will learn why later in the book.

Finally, we can convert a character into a boolean (encoded as an int) using the equality operator:

char c;
int should_continue;
printf("Do you want to continue? (y/n) ");
scanf(" %c", &c)
should_continue  =  c == 'y'

The above will read a character from standard input. If the user has typed 'y' then the should_continue will contain 1 or “true”. The last line above contains both the assignment operator = and the comparison operator ==. An unambigous way to read this last line is: should_continue becomes the boolean value of whether string equals "y".

To read multiple values, we just pass multiple directives on the format string. To read an integer, a float and a char in the same line, do:

int i;
float f;
char c;
scanf(" %i %f %c", &i, &f, &c);

We can process multiple lines of input until EOF by checking the result of scanf against the number of items to be read, for example:

while (scanf("%i %i", ...) == 2) {
    ...
}

We print values using printf. Its first argument is always a format string which indicates the message to be printed. This format string can contain %s, %i, %f and %c which are replaced respectively by the values of other arguments. We use %s for a string, %i for an int, %f for a float and %c for a char.

To print a string followed by a line break, do:

printf("%s\n", str);

To print an integer followed by a line break, do:

printf("%i\n", i);

To print a string, integer, float and character followed by a line break, do:

printf("%s %i %f %c\n", str, i, f, c);

Arguments should appear in the same order as their format sequences (%s, %i, etc). ◻

In Haskell, we read a line of input using the getLine function:

line <- getLine

We can read an Int or a Float using readLn :: Read a => IO a:

number <- readLn

To convert a string into an Int or Float we use read :: Read a => String -> a:

read "123"

To convert a string into a boolean, we can use the equality operator:

putStr "Would you like to continue? (y/n) "
line <- getLine
let shouldContinue  =  line == "y"

We can print string values followed by a line break using putStrLn like so:

putStrLn string

Use putStr to not include a line break after your string.

We can convert an Int or a Float to a string using show :: Show a => a -> String:

show 123

We can print Int and Float values directly using print :: Show a => a -> IO () like so:

print number

We can print multiple values using the string concatenation operator ++ and applications of show for non string values:

putStrLn (string ++ " " ++ show i ++ " " ++ show f)

Programming exercise (hi)

Write a program that reads several names from the standard input device and, for each name, prints Hello, <Name>! on the standard output device. Here is an example session with such a program:

$ ./hi
John
Hello, John!
Mary
Hello, Mary!
Smith
Hello, Smith!

Names are provided one per line, and do not contain spaces. Names are composed of letters of the English alphabet or dashes (-), and have no more than 30 characters.

Example input

John
Mary
Smith

Example output

Hello, John!
Hello, Mary!
Hello, Smith!

Before looking at the example solutions, try solving the exercise by yourself. Run your solution locally with the example input. Is it correct? If so, use the Online Judge to check against other test cases.


Here is a flowchart with an outline for a hi solution:

Flowchart for the `hi` solution

While we are able to read the string “name”, we print “Hello, name!”. ◻

In Python, here is how we can solve the hi exercise:

import sys

for line in sys.stdin:
    name = line.strip()
    print("Hello, " + name + "!");

For all lines in the standard input, we extract the name by stripping the trailing line break with .strip() and we print the hello message. ◻

In C, here is how we can solve the hi exercise:

#include <stdio.h>

int main()
{
    char name[31];
    while (scanf("%30s",name)==1)
        printf("Hello, %s!\n",name);
    return 0;
}

While we are able to scan a name from standard input, we print the hello message. ◻

In Haskell, here is how we can solve the hi exercise:

main :: IO ()
main  =  interact io

io :: String -> String
io input  =  unlines (map io1 (lines input))

io1 :: String -> String
io1 name  =  "Hello, " ++ name ++ "!"

Here we use the same pattern introduced earlier. For each line of input, that contains a single name, we produce the corresponding hello message by using the string concatenation operator ++. ◻

Programming exercise (age)

Write a program that reads a series of strings and integers and prints a name and age message.

Input will consist of a several lines each containing a string n and a natural number a where

|n| ≤ 30, i.e.: the string n is no more than 30 characters

0 ≤ a ≤ 180

For each line of input, your program should produce a line containing the message:

<n> is <a> years old.

with <n> replaced by n and <a> replaced by a.

Example input

John 23
Jane 32

Example output

John is 23 years old.
Jane is 32 years old.


Programming exercise (swap)

Write a program that reads a series of pairs of integers and strings and swaps them.

Input will consist of several lines each containing a number n and a string s separated by a single space where:

0 ≤ n ≤ 1000

|s| ≤ 30, i.e.: the string s is no more than 30 characters

For each line of input, you program should produce a line of output with the string s followed by number n.

Example input

123 abcdef
64 bits

Example output

abcdef 123
bits 64

Formatting floating point numbers

When printing floating point numbers, it is often useful to specify how many decimal places we want to see. How that is done depends on the language you are using. ◻

In Python, we can print a floating point number rounded to two decimal places like so:

print("%.2f" % x)

So, if x is 0.333, the above will print 0.33. If x is 0.666, the above will print 0.67. You can use %.1f for one decimal place, %.3f for three decimal places, %.4f for four decimal places, etc.

We can interpolate multiple floats in a larger message, like so:

print("Floats are %.2f and %f." % (x,y))

If x is 3.333 and y is 3.456 the above will print: Floats are 3.33 and 3.456. You can also use %i to interpolate integers and %s to interpolate strings. ◻

In C, we can print floating point numbers rounded to two decimal places like so:

printf("%.2f\n" % x)

So, if x is 0.333, the above will print 0.33. If x is 0.666, the above will print 0.67. You can use %.1f for one decimal place, %.3f for three decimal places, %.4f for four decimal places, etc.

We can interpolate multiple floats in a larger message, like so:

printf("Floats are %.2f and %f.", x, y)

If x is 3.333 and y is 3.456 the above will print: Floats are 3.33 and 3.456.

In Haskell, we can print floating point numbers rounded to two decimal places like so:

printf "%.2f\n" x

So, if x is 0.333, the above will print 0.33. If x is 0.666, the above will print 0.67. You can use %.1f for one decimal place, %.3f for three decimal places, %.4f for four decimal places, etc.

To use the above function printf you should import the Text.Printf module.

We can interpolate multiple floats in a larger message, like so:

printf "Floats are %.2f and %f." x y

If x is 3.333 and y is 3.456 the above will print: Floats are 3.33 and 3.456. You can also use %i to interpolate integers and %s to interpolate strings. ◻


Programming exercise (owes)

Write a program that reads an amount in dollars and two names then formats and prints the following message: <name1> owes $<amount> dollars to <name2>.

Input contains several lines each with a decimal number and two names separated by spaces. The decimal number is greater than 0.0 and smaller than 999.0 and has up to two decimal places. The two names have up to 30 characters.

For each line of input, output should contain a corresponding line with the following message: <name1> owes $<amount> dollars to <name2>. The amount should be rounded to two decimal places and have no leading zeroes.

Example input

1.5 John Mary
199 Jane Mario

Example output

John owes $1.50 dollars to Mary.
Jane owes $199.00 dollars to Mario.


4.4. Functions

Functions in programming are similar to mathematical functions: they take arguments and have a return value.

Consider the mathematical function f(x) = 2x + 1. The function f can be applied to different integer values yielding different results:

A similar function could be constructed in programming. The following pseudo-code in an imaginary programming language implements f.

function f(x)
begin
    return 2 * x + 1
end

Functions may take multiple arguments of different types. The return value of a function has a type as well. ◻

Functions in programming may also perform actions such as reading input, printing to the screen, creating an user entry on database, etc. A function that just performs an action and has no return value can be called a procedure. ◻

In Python, we declare functions using the following notation:

def <name>(<argument1>, <argument2>, <argument3>, ...):
    <command1>
    <command2>
    ...
    return <result>;

For example:

def f(x):
    return 2 * x + 1

In order to write a function that does not return a value in Python, simply do not use a return clause nor use the result of the function in an assignment. ◻

In C, we declare functions using the following notation:

<type> <name>(<type> <argument1>, <type> <argument2>, ...)
{
    <command1>;
    <command2>;
    ...
    return <result>;
}

For example:

int f(int x)
{
    return 2 * x + 1;
}

In order to write a function that does not return a value in C, we use the void type, like so:

void do_something()
{
    ...
}

In Haskell, we declare functions using the following notation:

<name> :: <type>
<name> <pat1>  =  <value1>
<name> <pat2>  =  <value2>
...
<name> <pat3>  =  <value3>

For example:

f :: Int -> Int
f x  =  2 * x + 1

To declare a function that performs IO in Haskell, we use the IO type and the do notation. For example:

putStrLnTwice :: String -> IO ()
putStrLnTwice s  =  do
  putStrLn s
  putStrLn s

4.5. Operators

In programming, we can use operators to manipulate numbers, booleans, strings or sometimes even functions. ◻

Operators can be classified on the number of operands. An operator is unary when it operates on a single value, e.g.: the negation operator - in -1. An operator is binary when it operates on two values, e.g.: the addition operator + in 1 + 2. ◻

Operators can be used in either prefix, infix or postfix notations. Prefix notation is when an operator appears before the operands, e.g.: the negation operator - in -1. Infix notation is when an operator appears between the operands, e.g.: the addition operator + in 1 + 2. Postfix notation is when an operator appears after the operands. ◻


Arithmetic Operators

As we have seen before, we can use operators to manipulate numbers.

In most programming languages, you can use +, - and * to perform addition, subtraction and multiplication in numbers. They are usually binary and infix. This is true in Python, C and Haskell.

In most programming languages, you can also use the unary prefix operator - to negate a number, e.g.: -1, -360. This is also true in Python, C and Haskell.

Programming languages offer a way to group expressions so the computer knows what operation to perform first. In most programming languages, round brackets ( and ) are used for that. Saying (1 - 2) - 3 is different than 1 - (2 - 3) due to which subtraction is performed first. Python, C and Haskell use round brackets to group operations.

Operators can have a precedence, that is, what is operated first. In most contexts, multiplication precedes addition, for example, 2 + 3 * 4 is interpreted as 2 + (3 * 4) and not as (2 + 3) * 4 – multiplication is performed before addition when there are no brackets.

Programming languages can also offer operators for:

The symbols for these vary for each language. ◻


We will now review how to use numeric operators in Python, C or Haskell, please jump to the explanation for your chosen language. ◻

The following table shows the arithmetic operators available in Python:

operation operator classification example
negation - unary prefix -x
addition + binary infix x + y
subtraction - binary infix x - y
multiplication * binary infix x * y
integer division // binary infix x // y
fractional division / binary infix x / y
modulus % binary infix x % y
exponentiation ** binary infix x ** y

The same symbol - is used for both negation and subtraction.

Python also has shorthands for updating variables, they are:

  • x += expr which is equivalent to x = x + (expr);
  • x -= expr which is equivalent to x = x - (expr);
  • x *= expr which is equivalent to x = x * (expr);
  • x /= expr which is equivalent to x = x / (expr);
  • x %= expr which is equivalent to x = x % (expr).
  • x //= expr which is equivalent to x = x // (expr);
  • x **= expr which is equivalent to x = x ** (expr).

The following table shows the arithmetic operators available in C:

operation operator classification example
negation - unary prefix -x
addition + binary infix x + y
subtraction - binary infix x - y
multiplication * binary infix x * y
integer division / binary infix x / y
fractional division / binary infix x / y
modulus % binary infix x % y

The same symbol - is used for both negation and subtraction.

The same operator is used for integer or fractional division, it depends on the type of values being operated. When used on values of the int type, it performs integer division. When used on values of the float type, it performs fractional division.

C also has shorthands for updating variables, they are:

  • x += expr which is equivalent to x = x + (expr);
  • x -= expr which is equivalent to x = x - (expr);
  • x *= expr which is equivalent to x = x * (expr);
  • x /= expr which is equivalent to x = x / (expr);
  • x %= expr which is equivalent to x = x % (expr).

There are also shorthands for incrementing and decrementing variables, i.e.: adding and subtracting one. They are:

  • x++, which increments x and returns the previous value;
  • x--, which decrements x and returns the previous value;
  • ++x, which increments x and returns the updated value;
  • --x, which decrements x and returns the updated value;

The following table shows arithmetic operators available in Haskell:

operation operator classification example
negation - unary prefix -x
addition + binary infix x + y
subtraction - binary infix x - y
multiplication * binary infix x * y
fractional division / binary infix x / y
integer division div function div x y
modulus mod function mod x y
exponentiation ^ binary infix x ^ y
exponentiation ** binary infix x ** y

The same symbol - is used for both negation and subtraction. Integer division and modulus is performed using the functions div and mod. They can be used in infix form using the following notation with backticks:

x `div` y
x `mod` y

We will now revisit several exercises from the previous chapter. This time you will need to process several test cases in a single run.

After compiling, running and testing your solutions locally, submit them to the Online Judge. This time, the test sets are tougher and include edge cases. Can you get a full score there?


Programming Exercise (triple)

Write a program that reads several number and prints their triple.

The input contains several lines each with one integer x where

-100 000 < x < 100 000.

Each line of output should contain a corresponding integer y where y = 3x.

Example input

2
360
123

Example output

6
1080
369

Your program should be implemented using a triple function that receives one integer as argument and returns an integer. Please refer to the information for the chosen language:

Hint. You do not need to accumulate input, print output as you go. As soon as you read a number, print its triple. On your screen typed input will be intercalated with program output. ◻


Programming Exercise (inc)

Write a program that reads several numbers and prints their increment, i.e. their value added to one.

Input contains several lines, each with a single integer x where - 100 000 000 ≤ x ≤ 100 000 000.

Each line of output contains a single corresponding integer y where y = x + 1.

Example input

2
123
1000

Example output

3
124
1001

Your program should be implemented using a inc function that receives one integer as argument and returns an integer. Please refer to the information for the chosen language:


Programming Exercise (add)

Write a program that reads several pairs of numbers and, for each pair, prints the sum.

Each line of input contains two numbers x and y where

-2 000 000 000 ≤ x, y ≤ 2 000 000 000

For each line of input there should be a line of output with the result of adding x to y.

Example input

0 0
3 7
12 21
-123 321
1234 4321

Example output

0
10
33
198
5555

Your program should be implemented using an add function that receives two integers as arguments and returns an integer. Please refer to the information for the chosen language:


Programming Exercise (mult)

Write a program that calculates the product of three numbers. Your program should read from the standard input and print to the standard output. The standard input and output devices are usually the keyboard and screen of a command line session.

Input consists of a single line with three natural numbers x, y and z where -1000 ≤ x, y, z ≤ 1000.

The output should contain a single line with an integer w where w = x × y × z.

Example input

2 3 4
3 7 1
234 321 -999

Example output

24
21
-75038886

Your program should be implemented using a mult function that takes three integers as arguments and returns an integer. Please refer to the information for the chosen language:


Programming Exercise (pi)

Given the radius of a circle, calculate its circumference and area.

diagram showing the circumference and area of a circle

The circumference of a circle with radius r is given by 2 × π × r or two times pi times the radius. The area of a circle with radius r is given by π × r ² or pi times the square of the radius. The number π, or pi, is a mathematical constant with an irrational value of 3.141 592 653 …

Each line of input contains a decimal value r indicating the radius where 0 < r < 10000.0.

For each line of input, your program should produce two numbers, c and a indicating the circumference and area. They should be rounded to two decimal places.

Example input

1
12
6.6
0.159

Example output

6.28 3.14
75.40 452.39
41.47 136.85
1.00 0.08

Your program should implement two functions circumference and area. Each should take a double-precision floating point number and return a double-precision floating point number. Please see the information for your programming language of choice:

Hint. The value of π (pi) is a real number so the only way to represent it as a floating point value is to use an approximation. Although you can use a hardcoded value of 3.141592653589793 for π it is better to use the one provided by your programming language of choice:


Programming Exercise (box)

Write a program that calculates the volume and the external surface area of a rectangular box given its width, height and depth.

A box, its width, height and depth

Input consists of several lines with three natural numbers w, h and d where 0 < w, h, d ≤ 999. These numbers indicate respectively the width, height and depth of the given box.

For each line of input, output should contain three corresponding lines. The first corresponding line should indicate the volume in the following format:

The volume of a <w> by <h> by <d> box is <v>.

The second corresponding line should indicate the area in the following format:

The surface area of a <w> by <h> by <d> box is <a>.

The third line should be blank.

Replace <w>, <h> and <d> by the dimensions of the box in the same order given in the corresponding input. Replace <v> and <a> by the volume and area respectively.

Example input

1 1 1
3 4 5
2 2 2

Example output

The volume of a 1 by 1 by 1 box is 1.
The surface area of a 1 by 1 by 1 box is 6.

The volume of a 3 by 4 by 5 box is 60.
The surface area of a 3 by 4 by 5 box is 94.

The volume of a 2 by 2 by 2 box is 8.
The surface area of a 2 by 2 by 2 box is 24.

Your program should be implemented using two functions volume and area. Each should take the 3 dimensions of a box and return its volume and surface area. Please refer to the information for your chosen language:


Operators are syntactic sugar

In theory, a programming language does not need operators to support arithmetic operations. Just functions are needed.

We could write x + y as simply add(x,y). However, that would become simply cumbersome as we create more intricate expressions. The simple x * y + z * w would become add(multiply(x,y),multiply(z,w)). For the same reason, in mathematics we write 1 + 2 instead of “one added to two”. So in practice, most languages have operators, and we do use them. ◻

In Haskell, there is a nice equivalence between binary operators and functions with two arguments:

  • f x y is equivalent to x `f` y for a given function f;
  • (?) x y is equivalent to x ? y for a given operator ?.

So the expression x + (y * z) could be rewritten in prefix notation as (+) x ((*) y z). Also, x `div` y is the same as div x y. ◻

Boolean Operators and Comparison Operators

As we have seen before, we can use operators to manipulate booleans. These booleans, or truth-values are commonly used in conditions.

In most programming languages, we find, negation, conjunction and disjunction boolean operators. These represent respectively the words “not”, “and” and “or” in natural language. These boolean operators take boolean values as arguments and return a boolean value. We also find comparison operators: equality, inequality, greater-than, greater-than-or-equal, etc. These comparison operators take two values and return a boolean value. ◻

The following table shows some boolean and comparison operators available in Python:

operation operator classification example
is equal to? == binary infix x == y
is different than? != binary infix x != y
is less than? < binary infix x < y
is greater than? > binary infix x > y
is less-than-or-equal than? <= binary infix x <= y
is greater-than-or-equal than? >= binary infix x >= y
negation / not not unary prefix not p
conjunction / and and binary infix p and q
disjunction / or or binary infix p or q

You can play with these operators on an interactive session:

$ python
>>> 1 < 2 and 2 < 3
True
>>> False or True
True
>>> not True
False

The operator precedence is: negations then conjunctions then disjunctions then comparisons. Writing not (1 < 2) or True and False is the same as writing ((not (1 < 2)) or (True and False))

The following table shows some boolean and comparison operators available in C:

operation operator classification example
is equal to? == binary infix x == y
is different than? != binary infix x != y
is less than? < binary infix x < y
is greater than? > binary infix x > y
is less-than-or-equal than? <= binary infix x <= y
is greater-than-or-equal than? >= binary infix x >= y
negation / not ! unary prefix !p
conjunction / and && binary infix p && q
disjunction / or || binary infix p || q

C has shorthands for updating boolean variables:

  • p ||= expr which is equivalent to p = p || (expr);
  • p &&= expr which is equivalent to p = p && (expr).

The operator precedence is: negations then conjunctions then disjunctions then comparisons. Writing !(1 < 2) || True && False is the same as writing ((!(1 < 2)) || (True && False))

The following table shows some boolean and comparison operators available in Haskell:

operation operator classification example
is equal to? == binary infix x == y
is different than? /= binary infix x /= y
is less than? < binary infix x < y
is greater than? > binary infix x > y
is less-than-or-equal than? <= binary infix x <= y
is greater-than-or-equal than? >= binary infix x >= y
negation / not not function not p
conjunction / and && binary infix p && q
disjunction / or || binary infix p || q

Negation is performed using the function not.

You can play with these operators on an interactive session:

$ ghci
> 1 < 2  &&  2 < 3
True
> False || True
True
> not True
False

The operator precedence is: negations then conjunctions then disjunctions then comparisons. Writing not (1 < 2) || True && False is the same as writing ((not (1 < 2)) || (True && False))

Exercises involving boolean operators will appear on the next section. ◻


4.6. Conditions

In programming, we use conditions to represent branching execution paths. If a condition is true, execute an action; otherwise, execute a different action. ◻

If-else conditions

We use if-else conditions when we want to encode two branching execution paths. Here is a quick review from previous chapter. ◻

If-else condition on a flowchart

In Python, we declare if conditions like so:

if <condition>:
    <command>
    <command>
    ...
    <command>
else:
    <command>
    <command>
    ...
    <command>

The else clause is optional. ◻

In C, we declare if conditions like so:

if (<condition>) {
    <command>;
    <command>;
    ...
    <command>;
} else {
    <command>;
    <command>;
    ...
    <command>;
}

If there is only one command, we can omit the brackets:

if (<condition>)
    <command>;
else
    <command>;

The else clause is optional. ◻

In Haskell, we declare if conditions like so:

if <condition>
then <result1>
else <result2>

Expressions in the then and else clause must have the same type or execute the same type of action. ◻


Programming Exercise (oddeven)

Write a program that prints whether a given natural number is odd or even. A number is even when it is disivible by two. A number is odd when it is not divisible by two.

Input and output

The input contains several lines each with a natural number n where -2 000 000 000 ≤ n ≤ 2 000 000 000. Input is terminated by the end-of-file (EOF).

For each line of input, the output should contain either odd or even.

Example input

0
3
12
-7

Example output

even
odd
even
odd


If-else-if conditions

We use if-else-if conditions when we want to encode several different execution paths. These conditions are simply nested if-else conditions. Here is a quick review from previous chapter. ◻

If-else-if condition on a flowchart

In Python, we declare if-else-if conditions like so:

if <condition1>:
    <command1>
elif <condition2>:
    <command2>
else:
    <command3>

The above, works the same as a nested if condition:

if <condition1>:
    <command1>
else:
    if <condition2>:
        <command2>
    else:
        <command3>

Again, the else clause is optional. ◻

In C, we declare if-else-if conditions like so:

if (<condition1>) {
    <command1>;
} else if (<condition2>) {
    <command2>;
} else {
    <command3>;
}

The above is a nested if condition. We could reformat it like so:

if (<condition1>) {
    <command1>;
} else {
    if (<condition2>) {
        <command2>;
    } else {
        <command3>;
    }
}

Again, the else clause is optional. ◻

In Haskell, we can write if-else-if conditions like so:

if <condition1> then
  <result1>
else if <condition2> then
  <result2>
else
  <result3>

The above could be alternatively indented like so:

if <condition1>
  then <result1>
  else if <condition2>
         then <result2>
         else <result3>

Again, the else clause is required and the result expressions should have the same type. ◻

Programming Exercise (order)

Write a program that reads several pairs of numbers and prints if they are in strict increasing order. In other words, if the second number is greater than the first.

Input will consist of several lines each with a pair of numbers x and y where

-1 000 000 000 ≤ x, y ≤ 1 000 000 000.

For each line of input, output should contain a single line with either Yes or No indicating whether x < y.

Example input

1 3
10 9
-31337 -1337

Example output

Yes
No
Yes

Programming Exercise (good)

In English, we greet people by “Good morning”, “Good afternoon” or “Good evening” depending on the time of day.

Write a program that given the current hour (in 24 hours format) prints a good morning, good afternoon or good evening message according to the following list:

Input will consist of several lines each with a single number h where 0 ≤ h < 24.

For each line of input, output should contain a corresponding line with either:

Example input

11
15
20

Example output

Good morning
Good afternoon
Good evening


Programming Exercise (bmi)

The Body Mass Index (BMI) can be used to classify weight in adults. The BMI of a person is given by the weight in kilogrammes divided by the square of the height in metres [WHO, CDC, NHS]. Based on the BMI, a person can be classified in one of four statistical categories: underweight, normal weight, overweight or obese. See the following table:

BMI = w/h² (kg/m²)

       BMI < 18.5  underweight
18.5 ≤ BMI < 25    normal weight
25   ≤ BMI < 30    overweight
30   ≤ BMI         obese

The above are statistical categories. To evaluate an individual’s health, one should consult with a trained healthcare provider.

Write a program that given the weight and height of a person prints the corresponding BMI classification.

The input consists of several lines, each containing two numbers h and w with up to two decimal points where

0.10 ≤ h < 3.00

1.0 ≤ w ≤ 999.9

For each line of input, the output should contain a single line with the corresponding BMI classification in lowercase letters: underweight, normal weight, overweight or obese.

Example input

1.75 69.9
1.60 65
1.91 111.1

Example output

normal weight
overweight
obese


Programming Challenge (triangle)

Every triangle can be classified as either scalene, isosceles or equilateral:

(Some authors consider equilateral to be a special case of isosceles. For the purpose of this exercise, we use Euclid’s original definition and consider isosceles triangles those with exactly two edges of the same size.)

triangle types: scalene, isosceles, equilateral, impossible

All triangles can also be classified as right, obtuse and accute:

triangle angle types: obtuse, right, acute

Write a program that given three edge sizes determines:

Input consists of a several lines, each with three natural numbers x, y and z where

0 < x, y, z < 10 000

For each line of input, output should contain a line indicating both classifications or impossible.

Example input

3 4 5
3 3 1
6 4 3
1 1 1
7 2 3

Example output

scalene right
isosceles acute
scalene obtuse
equilateral acute
impossible


Case conditions

When we want to make a decision based on the value of a variable we can use case conditions. Here is a pseudocode illustrating case conditions:

...
case x
    <A>:
        <action A>
    <B>:
        <action B>
    <C>:
        <action C>
    default:
        <default action>
...

If the value of variable x is “A”, action A is executed. If the value of variable x is “B”, action B is executed. If the value of variable x is “C”, action C is executed. Otherwise, the default action is executed. The regular program flow is continued afterwards. ◻

Case conditions on a flowchart

Here is an example, doing a different operation depending on the operator character provided on the input:

read number x, character o and number y
case o
    '+':
        r <- x + y
    '-':
        r <- x - y
    '*':
        r <- x * y
write "The result is:" r

Read a number x, a character c and a number y; let r become the result of an arithmetic operation depending on character c; write the resulting value of r.

In Python, there are no case conditions. We use regular if-else-if conditions with equality comparisons.

Here is a command line 3 operation calculator in Python:

x, o, y = input().split()
x = int(x)
y = int(y)
if o == "+":
    r = x + y
elif o == "-":
    r = x - y
elif o == "*":
    r = x * y
print(r)

In C, we can write case conditions like so:

switch (<variable>) {
case <A>:
    <command A>;
    break;
case <B>:
    <command B>;
    break;
case <C>:
    <command C>;
    break;
default:
    <default command>;
    break;
}

The switch variable can be of int and char types. Each case can contain multiple commands which should be followed by the break command. ◻

Here is a command line 3 operation calculator in C:

#include <stdio.h>
int main()
{
    int x, y, r;
    char c;
    scanf(" %d %c %d",&x,&c,&y);
    switch (c) {
    case '+':
        r = x+y;
        break;
    case '*':
        r = x*y;
        break;
    case '-':
        r = x-y;
        break;
    }
    printf("%d\n",r);
    return 0;
}

In Haskell, we can write case conditions like so:

case <expr> of
<A> -> <result A>
<B> -> <result B>
<C> -> <result C>
_   -> <default result>

The <expr> argument can be of virtually any type. The results of all options must be of the same type. ◻

Here is a command line 3 operation calculator in Haskell:

main :: IO ()
main = do
  line <- getLine
  let [x',o',y'] = words line
  let x = read x'
  let y = read y'
  let o = head o'
  case o of
    '+' -> print (x + y)
    '*' -> print (x * y)
    '-' -> print (x - y)
    _   -> print "error: unknown operator"

Programming Exercise (calc)

Write a program that is able to perform 5 operations: addition +, subtraction -, multiplication *, division / or exponentiation ^.

Input consists of several lines, each with a number x, a character o and another number y separated by spaces where

-2 000 000.00 ≤ x, y ≤ 2 000 000.00

o is +, -, *, / or ^

Output should contain a single line with the corresponding result of applying operator o to x and y. Output should be rounded to two decimal places.

Inputs are given so that the resulting value r is within the following range:

-2 000 000.00 ≤ r ≤ 2 000 000.00

Example input

1 + 2
3.5 * 6
7 - 12
20 / 3
-10 ^ 3

Example output

3.00
21.00
-5.00
6.67
-1000.00

4.7. Repetition

In this section, we will review two repetition methods introduced in the last chapter: recursion and while loops. Then we will introduce for loops.

Recursion

Recursion is the act of referring back to itself. Recalling from previous chapter, a recursive definition is one that is defined in terms of itself. In turn, a recursive function is one that calls itself, i.e.: uses recursion. ◻

The Sierpiński triangle

Example: the Sierpiński triangle. The Sierpiński triangle can be constructed by starting with a large triangle and inscribing smaller triangles in the above pattern repeatedly. The resulting image is recursive, you see the full image in parts of the image. Above, you can see it constructed up to six levels. ◻

Example: integer exponentiation. Exponentiation of integers can be defined recursively like so:

The value of b to the power of zero is one and the value of b to the power of n is b times b to the power of n-1.

The following function in pseudo-code performs integer exponentiation recursively:

function power(integer b, integer n)
    if n is equal to 0
        return 1
    else
        return b * power(b, n-1)

At each recursive step, the exponent is decremented by one and we multiply by the base once. ◻


While loops

In the previous section, we saw how to perform repetitions through recursion. In the previous chapter, we saw how to perform repetitions with a while loop which looks like the following in pseudo code:

while <condition>
    <commands>

While the <condition> is true, the computer will perform the given <commands>.

We will now review some other repetition methods. Please jump to the box describing the language of your choice. ◻

In Python, here is how we can perform a while loop:

while <condition>:
    <commands>

Anything indented under the while keyword is repeated. ◻

In C, here is how we can perform a while loop:

while (<condition>) {
    <commands>;
}

The brackets are optional if there is only one command. ◻

In Haskell, there are no while loops. Repetition can be performed through recursion. ◻

For loops

An alternative to while loops are for loops which are used to perform a certain number of repeated actions. ◻

In Python, here is how we can perform for loops:

for <name> in <sequence>:
    <commands>

As the <sequence> we can place range(<n>) to make a for loop that repeats n times where variable <name> assumes values 0 through n-1. For example:

for i in range(4):
    print(i)

Will print 4 lines with the numbers 0, 1, 2 and 3. The print command is executed 4 times, each with an increasing value of i. ◻

In C, here is how we can perform for loops:

for (<init>; <condition>; <step>) {
    <commands>;
}

The <init> command is executed once before the for loop. The <condition> is checked before at each iteration. The <step> is performed after each iteration. The above for loop is equivalent to the following while statement:

<init>;
while (<condition>) {
    <commands>;
    <step>;
}

Here is an example:

for (i=0; i<4; i++)
    printf("%i\n",i);

The above will print 4 lines with the numbers 0, 1, 2 and 3. The printf command is executed 4 times, each with an increasing value of i. ◻

In Haskell, there are no for loops. Repetition can be performed through recursion. ◻


The following exercises can be solved through any of the three repetition methods discussed in this section. You can try to solve each of them three times, each time using a different repetition method.

Programming Exercise (factorial)

Write a program that computes the factorial of a number n, or simply n!. Remember, the factorial of n is:

n! = n × (n-1) × (n-2) × … × 2 × 1 × 0

Or, recursively:

Input will contain several lines with a single integer n where 0 ≤ n ≤ 12. Output should contain a line with the factorial of n.

Example input

4
6

Example output

24
720

Your program should contain a factorial function that takes an integer and returns an integer. Please refer to the information for your chosen language:


Programming Exercise (power)

Write a program that performs integer exponentiation of a base b to the power of n.

bⁿ = 1 × b × b × … × b where b is repeated n times

for example

2⁵ = 1 × 2 × 2 × 2 × 2 × 2 = 32

Input will contain several lines each with two integers b and n where

-1000 ≤ b ≤ 1000

0 ≤ n ≤ 30

For each line of input, output should contain a corresponding line with a single integer indicating the value of bⁿ.

Input will be given so that

-1 000 000 000 < bⁿ < 1 000 000 000

Example input

2 5
5 2

Example output

32
25

Your program should contain a power function that takes two integers and returns an integer. The first integer argument should be the base and the second the exponent. Please refer to the information for your chosen language:

You should perform the exponentiation as a series of multiplications. For this exercise, you should restrain from using your programming languages' built-in exponentiation functions. ◻


Programming Exercise (fibonacci)

Write a program that computes numbers in the fibonacci sequence. This sequence is defined recursively as follows:

That is, the zeroth Fibonacci number is zero and the first Fibonacci number is one. Other Fibonacci numbers are given by the sum of its two predecessors.

The first 10 numbers in the Fibonacci sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21 and 34.

Input will consist of several lines, each with a single integer n indicating the position in the Fibonacci sequence.

For each line of input, output should contain a line with a corresponding number Fₙ indicating the Fibonacci number in position n.

Example input

3
8
6

Example output

2
21
8

Your program should contain a fibonacci function that takes an integer and returns an integer. Please refer to the information for your chosen language:

Your function is expected to have good performance. ◻


4.8. Sequences

So far, our programs involved mostly standalone variables, e.g.: an integer x, another integer i and a float f. We will now learn to deal with collections of values.

A list, array or sequence is a collection of values where the order does matter. For example, we may want to store a list of employees of a company or a queue of documents for processing. For this we use a list or array. ◻

Strings are sequences

We have already interacted with a sequences before. A string is a sequence of characters.

The "Hello" string with 5 characters numbered from 0 to 4

On sequences, we can perform indexing, that is, referring the element at a given position in a list. So, for example, in the string Hello we have character H at position 0; character e at position 1; character l at position 2; character l at position 3; character o at position 4. This string has the length of 5. ◻

In Python, we retrieve an element at position n of the list l by using l[n]. Positions are numbered starting from 0.

Here is a interactive session illustrating string indexing:

$ python
>>> str = 'Hello'
>>> str[0]
'H'
>>> str[1]
'e'
>>> str[4]
'o'

At position 0 we have 'H'; at position 1 we have 'e'; and at position 4 we have 'o'. ◻

In C, we retrieve an element at position n of an array a by using a[n]. Positions are numbered starting from 0. In C, strings are terminated by the special implicit character '\0'.

Here is an example:

char str[6] = "Hello";
printf("%c\n",str[0]);
printf("%c\n",str[1]);
printf("%c\n",str[4]);

The above code will print the characters at positions 0, 1 and 4 which are 'H', 'e' and 'o'. ◻

In Haskell, we retrieve an element at position n of a list xs by using xs !! n. Positions are numbered starting from 0.

Here is a interactive session illustrating string indexing:

$ ghci
> str !! 0
'H'
> str !! 1
'e'
> str !! 4
'o'

At position 0 we have 'H'; at position 1 we have 'e'; and at position 4 we have 'o'. ◻

Programming Exercise (index-string)

Write a program that prints the character at position n of a given string.

Each line of input consists of a string s followed by a number n separated by a single space. For each line of input, there should be a line of output containing the character in position n of the corresponding string s.

Each given string has at most 60 characters.

Positions are indexed from 0. If the number given on the input is 0, you should print the first character; if the number given on the input is 1, you should print the second character; if the number given on the input is 2, you should print the third character; etc.

Example input

abcdef 0
xyz 2
Hello 1
World 4

Example output

a
z
e
d


Sequences of integers

We can also have sequences of other types, for example, sequences of integers. Sequences of integers can be indexed in the same way we index strings.

Here is how we declare a list in Python:

<name> = [<element_0>, <element_1>, ..., <element_n>]

For example:

list = [11, 12, 13, 14]

We can access the first element at position 0, the number 11:

print(list[0])

Or the last element at position 3, the number 14:

print(list[3])

Here is how we declare an array of integers in C:

int <name>[<n_elements>];

Notice that this notation is similar to how we declare a string, as strings are just arrays of characters.

We can also provide an explicit list of initial elements:

int <name>[<n_elements>] = {<element_0>, <element_1>, ..., <element_n>};

For example:

int array[4] = {11, 12, 13, 14};

We can access the first element at position 0, the number 11:

printf("%i\n", array[0]);

Or the last element at position 3, the number 14:

printf("%i\n", array[3]);

In C, we retrieve an element at position n of an array a by using a[n]. Positions are numbered starting from 0. In C, strings are terminated by the special implicit character '\0'.

Here is an example:

char str[6] = "Hello";
printf("%c\n",str[0]);
printf("%c\n",str[1]);
printf("%c\n",str[4]);

The above code will print the characters at positions 0, 1 and 4 which are 'H', 'e' and 'o'. ◻

In Haskell, lists can be written explicitly using the following notation:

[<element_0>, <element_1>, ..., <element_n>]

Or alternatively, using the cons (:) operator:

<element_0>:<element_1>:...:[]

For example:

[11,12,13,14]

or alternatively:

11:12:13:14:[]

Lists are indexed using the !! operator as we have seen previously with strings.

> [11,12,13,14] !! 0
11
> [11,12,13,14] !! 3
14

We call the first element of a list the “head” and the other elements the “tail”. We can retrieve the head and tail of a list using the head and tail functions:

> head [11,12,13,14]
11
> tail [11,12,13,14]
[12,13,14]

Iterating

A common operation in lists is iterating through them, that is, going element by element and perform an operation.

In Python, we iterate through a list using a for loop:

for <element> in <list>:
    <commands>

For example:

for i in [11,12,13,14]
    print(i)

The above will print 4 lines with 11, 12, 13 and 14. ◻

In C, we can iterate through a list using a while loop:

int array[4] = {11,12,13,14};
int i=0;
while (i<4) {
    printf("%i\n", array[i]);
    i = i + 1;
}

The above will print 4 lines with 11, 12, 13 and 14. However, it is more common to use a for loop:

for (i=0; i<4; i++)
    printf("%i\n", array[i]);

The above for loop has the same meaning as the above while loop. ◻

In Haskell, we can use map to apply a function to each element of a list yielding a new list.

map <function> <list>

For example:

$ ghci
> map show [0,1,2,3]
["0", "1", "2", "3"]

The above transforms a list with integers into a list with integers encoded as strings.

We can use traverse to perform an IO action at each element of a list:

traverse <action> <list>

For example:

traverse print [0,1,2,3]

The above will print the number 0, 1, 2 and 3 one per line. ◻

Reading lists of values

This section explains how to read lists of values.

In Python, if we have a string with values separated by spaces, we can split it into a list of strings using the str.split function:

$ python
>>> str.split('10 apples 20 bananas')
['10', 'apples', '20', 'bananas']

The resulting list above has 4 elements. For convenience, you can call the split function by appending .split() after the string, so the following is equivalent to the above:

>>> '10 apples 20 bananas'.split()
['10', 'apples', '20', 'bananas']

The split function was being used all along in previous exercises, both when reading a line of input with input().split() and when splitting a line of input with line.split().

We can assign the resulting list to a variable and use indexing on it:

>>> list = '10 apples 20 bananas'.split()
>>> list[0]
'10'
>>> list[1]
'apples'
>>> int(list[2])
20

We can use commas to single out specific elements when splitting. We use an asterisk to specify where we want the rest of the elements. Here is an example:

>>> first, second, *rest, last = '10 a 20 b 30 c'.split()
>>> first
'10'
>>> second
'a'
>>> last
'c'
>>> rest
['20', 'b', '30']

Please play around with the above idioms on the interactive Python session until you are confortable, then move on to the next exercise. ◻

In C, we read lists of integers by iterating using a for loop. The following code reads 6 integers and stores them on an array.

int i;
int array[100];
for (i=0; i<6; i++)
    scanf("%d", &array[i]);

To read another element type we change the element type of the array, e.g. float, and the scanf % sequence, e.g.: %f. ◻

In Haskell, if we have a string with values separated by spaces, we can split it into a list of strings by using the words function:

$ ghci
> words "10 apples 20 bananas"
["10","apples","20","bananas"]

We can convert the list of strings back using unwords:

> unwords ["10","apples","20","bananas"]
"10 apples 20 bananas"

The functions lines and unlines work similarly to words and unwords but lines and unlines break and join on using line breaks.

We can assign the resulting list to a variable and use head, tail, init and last on it:

> let string = "10 apples 20 bananas"
> let list = words string
> head list
"10"
> tail list
["apples","20","bananas"]
> init list
["10","apples","20"]
> last list
"bananas"

We can even single out elements in an assignment:

$ ghci
> let (first:second:etc) = list
> first
"10"
> second
"apples"
> etc
"20 bananas"

The uses of let above assume an interactive session. In actual Haskell code, we can use the let ... in ... or where notations. ◻

Programming Exercise (repeat-list)

Write a program that reads lists of integers from standard input and replicates the same integers on standard output.

Each line of input begins with a number L, indicating the number of integers to be repeated, followed by L numbers all separated by a single space.

For each line of input there should be a line of output with the number of integers followed by elements: followed by the numbers given in the input. Output values should not contain leading zeroes and should be separated by a single space.

Each list has at least one element and at most a hundred elements, i.e., 1 ≤ L ≤ 100.

Example input

4 1 2 3 4
2 32 16
3 12 360 60

Example output

4 elements: 1 2 3 4
2 elements: 32 16
3 elements: 12 360 60


Now, let’s try to solve this exercise together. Again, avoid copy-pasting and take time to type everything.

In Python, here is how we can solve the repeat-list exercise:

import sys

for line in sys.stdin:
    length, *elements = line.split()
    length = int(length)
    print(length, "elements:", end='')
    for element in elements:
        element = int(element)
        print('', element, end='')
    print()

For each line of input the same sequence is performed. First split the line into strings, single out the length and store the other elements. Convert the length to integer. Print the length followed by elements: without a line break (end=''). Then, for each element in elements, convert it to int then print it with a preceding space ('',) and without a line break (end=''). Finally, print a line break. ◻

In C, here is how we can solve the repeat-list exercise:

#include <stdio.h>
int main()
{
    int array[100];
    int lenght;
    int i;
    while (scanf("%d",&len)==1) {
        for (i=0; i<length; i++)
            scanf("%d",&array[i]);
        printf("%d elements:", len);
        for (i=0; i<len; i++)
            printf(" %d",array[i]);
        printf("\n");
    }
    return 0;
}

The first three lines of main declare an array to hold the numbers on the input, an int variable to hold the length and a counter i. While the length of the array can be scanned, perform the same steps. In the first for loop, read each element of the array. Print the length followed by elements:. In the second for loop, print each element of the array. Finally, print a line break. ◻

In Haskell, here is how we can solve the repeat-list exercise:

io1 :: String -> String
io1 s  =  show len ++ " elements: " ++ unwords (map show elements)
  where
  len:elements = map read (words s) :: [Int]

io :: String -> String
io input  =  unlines (map io1 (lines input))

main :: IO ()
main  =  interact io

The where clause of io1 defines len and elements which are taken from reading all strings in the input line. The result of io1 is the output line: len, followed by elements:, followed by all elements joined by unwords. And now we can finally understand the function io being used all along: it splits the input into lines, applies the function io1 on each line then join the output into lines. ◻

Programming Exercise (index-ints)

Write a program that prints the character at position n of a given list.

Each line of input consists of a number n, followed by n numbers, followed by number i.

For each line of input there should be a line of output with a single integer aᵢ indicating the number at position i of the input list.

Example input

5 1 2 3 4 5 2
4 16 8 4 2 3
3 360 60 1080 0

Example output

3
2
360


Programming Exercise (replace)

Write a program that replaces the character in a given position in a string.

Each line of input will consist of a string s, a natural number i and a character c.

For each line of input, there should be a line of output with a modified version of string s where the character at position i is replaced by character c.

String s is alphanumeric and is of up to 60 characters. This string is indexed from zero.

0 < |s| ≤ 60

0 ≤ i < |s|

Example input

Hallo 1 e
Bach 3 k
bitter 1 u

Example output

Hello
Back
butter


4.11. Chapter remarks

In this chapter, we have reviewed what are data-types, what are variables, how to do input and output, how to write functions, how to use operators, how to write conditions, how to perform repetition and how to use sequences. ◻


4.12. Exercises

The exercises throughout this chapter were:

A good way to test your skills is to see if you are able to do these exercises without consulting the book or at least without looking at the example solutions. Submit your solutions to the Online Judge to make sure that they are correct. If you are comfortable with these exercises, it is time to move to the next chapter. ◻


<< 3. Programming Basics   |   4. Programming   |   5. Mathematical Foundations >>

index | submit | rank | book

Copyright © 2020-2021 Rudy Matela
All rights reserved