5 Jan 2018, Friday

Lecture 1

Surway of Algorithmic Languages. Imperative and Functional Languages. Intruduction to Haskell

History of algorithmic languages. Classification of languages: traditional, object oriened, functional.

Basics of Haskell. Data types, functions, lists, list comprehensions, map function. Recursion. The conditional expresions "if... then... else" and guards. Program examples: squares of first 20 natural numbers (implemented in at least 3 different ways); prime test, lists of prime numbers.

Practical work: Find out all perfect numbers in the range [1..10000]. Do the same task also for semiperfect numbers. (A perfect number equals to the sum of ALL its proper divisors. A semiperfect number equals to the sum of SOME its proper divisors.)

Examples of Programs

Type the squares of the first 20 natural numbers

square :: Int -> Int
square x = x*x

smallNumbers :: [Int]
smallNumbers = [1..20]

squares :: [(Int,Int)]
squares = zip smallNumbers (map square smallNumbers)

main :: IO()
main = putStrLn (show squares)

Working with interpretator ghci, we can just type:

Prelude> map (\ x -> x^2) [1..20]
to obtain the result:
[1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400]
Here we use the lambda-function:
    (\ x -> x^2)
that maps each element of the list [1..20] to its square.

If we need the list of pairs (number, square of number), we may use the zip function that zips two lists and creates a single list of pairs:

Prelude> zip [1..20] (map (\ x -> x^2) [1..20])
We get:
[(1,1),(2,4),(3,9),(4,16),(5,25),(6,36),(7,49),(8,64),
(9,81),(10,100),(11,121),(12,144),(13,169),(14,196),
(15,225),(16,256),(17,289),(18,324),(19,361),(20,400)]

And the same task with the list comprehension — the most elegant solution:

Prelude> [(n, n^2) | n <- [1..20]]

Prime Test

The most simple prime test is: just check that a number n is not divisible by all odd divisors that do not exceed the square root of n. All such trial divisors make up a list:

    [d | d <- [3, 5..n-1], d^2 <= n]
We use an auxiliary function divisible n divisors, where n is an integer that we check and divisors is a list of trial divisors. The function return True iff n is divisible by some of trial divisors from the list. The implementation is recursive:
divisible :: Int->[Int]->Bool
divisible x y =
    if y == []
    then False
    else if x `mod` (head y) == 0
         then True
         else divisible x (tail y)
Here we use the conditional expressions of form "if ... then ... else ... ". But with guards this function can be rewritten in much more elegant form:
divisible :: Int->[Int]->Bool
divisible x y
    | y == []               = False
    | x `mod` (head y) == 0 = True
    | otherwise             = divisible x (tail y)

Using this auxiliary function and guards, we easily implement the prime test:

prime :: Int->Bool
prime n
    | n < 2     = False
    | n == 2    = True
    | even n    = False
    | otherwise =
      not (divisible n [3,5..n-1])

With the prime test, we can find the list of all primes not exceeding, say, 100:

Prelude> [n | n <- [1..100], prime n]
The result is:
[2,3,5,7,11,13,17,19,23,29,31,37,
41,43,47,53,59,61,67,71,73,79,83,89,97]

And, finally, calculate 10 maximal prime numbers not exceeding 1,000,000:

Prelude> take 10 [n | n <- [999999, 999997..], prime n]
We got:
[999983,999979,999961,999959,999953,999931,999917,
999907,999883,999863]


6 Jan 2018, Saturday

Lecture 2

Type Classes, Signatures of Functions, Pattern Matching in Haskell

Type classes in Haskell and type signatures of functions. Pattern matching and its use in function definitions. Combination of pattern matching and guards. More about recursion: application to lists, implementation of some mathematical algorithms: Euclid's and Extended Euclid's algorithms. The "let ... in ..." construction.

Control work, 6 variants:

1. Calculate a value of a polynomial in a given point. The coefficients of polynomial are given in a list in descending order.

2. Calculate a value of a polynomial in a given point. The coefficients of polynomial are given in a list in ascending order.

3. Calculate a derivative of a polynomial. Coefficients of a polynomial and its derivative are given in lists in descending order.

4. Calculate an undefinite integral of a polynomial. Coefficients of a polynomial and its integral are given in lists in descending order.

5. The same task as 3, but coefficients go in ascending order.

6. The same task as 4, but coefficients go in ascending order.

Examples of Programs

Euclid's algorithm

Given 2 integers, calculate their greatest common divisor (at least one integer should not be zero). We use the name myGcd for this function, because gcd function is standard and presented in the "Prelude" module.
myGcd :: (Integral a) => a->a->a
myGcd x 0 = x
myGcd x y = myGcd y (x `mod` y)

The first line of the function definition is the type signature of a function. Here the letter a denotes a type class, and the part of line in parenthesys (Integral a) is the type constrain. It says that the type a must be an integer number, i.e. it may be either Int (bounded integer number) or Integer (unbounded); both these type belongs to the type class Integral. The part after the sign => defines types of formal parameters and return value of function, here of the same type a.

The body of function uses the pattern matching. The first pattern "x 0" means that the second parameter is zero. The gcd of such pair equals x:

myGcd x 0 = x
Otherwise, we consider the general pattern "x y", where we already know that y is not zero (because pattern matching is performed in top-down order and the first pattern was not matched). For such pair,
    gcd(x, y) = gcd(y, r)
where r is the remainder of dividing x by y; we calculate r using the operation `mod`, r = x `mod` y. So, the recursive application of our function myGcd
to the pair (y, x `mod` y) solves the problem:
myGcd x y = myGcd y (x `mod` y)

Extended Euclid's algorithm

. . .

8 Jan 2018, Monday

Lecture 3

Tail Recursion

The problem with ordinary (some people say "naive") recursion is a possible stack overflow. Consider some list having a length of million. If we use a naive recursion to implement some function working with this list, then the execution of function needs a stack of size 1000000*frame size; with a stack size 4M (default for many compilers and algorithmic languages) an overflow is very probable, and that means disaster.

But with the tail recursion most compilers can implement the optimization of functions call, so that the depth of stack is kept bounded by some small size not depending of the formal depth of recursion. (The stack frame of the calling function may be released at the moment of call, because no further processing is needed in the calling function.) Moreover, the tail recursion works faster and even looks more natural and simple than naive recursion, when we got accustomed to it. Simply speaking, it corresponds in some sense to the familiar while loop.

It is not easy to give the strict definition of tail recursion. Formally, the recursion is tail when the recursive call is the last action performed in the fuction; this means that the return value of a function is returned directly as the result of recursive call.

Often the tail recursion uses an accumulator value that accumulates the result during a series of recursive calls. So sometimes instead of the term "tail recursion", people speak about recursion that uses accumulators.

Consider the most simple example of calculating the factorial of non-negative integer number. Let us write the function first in C language, using a naive recursion:

    int factorial(int n) {
        if (n == 0) {
            return 1;
        } else {
            return n*factorial(n - 1);
        }
    }
Here the recursion is not a tail recursion, because the recursive call of factorial(n - 1) is not the last action: after a completion of recursive call, the function must multiply its result by n, so the stack frame of calling function cannot be released at the moment of recursive call.

How to transform this function to use a tail recursion? We add the additional parameter called accumulator. The meaning of accumulator is following: when we have processed already a part of input data, the accumulator contains a value of function calculated for the processed part. So, instead of a single factorial function, we need two functions: in addition to factorial, we use also an auxiliary function factorial0 with an additional argument acc. The ordinary function factorial just calls the auxiliary function factorial0 with initial value of accumulator (1 for factorial). So, the function factorial does not use any recursion.

The auxiliary function factorial0 is implemented using tail recursion. It is called with some value of accumulator (the value of target function on the already processed part of data) and the part of input data that is not yet processed. If the input data is empty, then it just returns the value of accumulator. If input data is not yet empty, then the function takes the current head of input and adds it in some way to accumulator (in case of factorial, the multiplication is used for that). Then the function calls itself recursively with the new value of accumulator and the remaining tail of input data; the return value of recursive call is returned as a result of function without any additional processing.

    int factorial(int n);                  // Global function
    static int factorial0(int acc, int n); // Auxiliary function

    int factorial(int n) {
        return factorial0(1, n);
    }

    static int factorial0(int acc, int n) {
        if (n <= 0) {
            return acc;
        } else {
            return factorial0(acc*n, n - 1);
        }
    }

Let us write these functions in Haskell:

    factorial :: (Integral a, Eq a) => a->a
    factorial n = factorial' 1 n

    factorial' :: (Integral a, Eq a) => a->a->a
    factorial' acc n
        | n <= 0        = acc
        | otherwise     = factorial' (acc*n) (n - 1)

The tail recursion is useful when dealing with lists. For example, let us implement the calculation of the value of a polynomial in a given point; the coefficients of polynomial are given in a list in descending order. The idea of implementation is to use the Horner scheme. Let

    pn = a0 xn + a1 xn-1 + ... + an
is a polynomial of degree n, and pn+1 is a polynomial of degree n+1, which is obtained by adding a coefficient an+1 to the end of the list. Then we have the equation:
    pn+1 = pn x + an+1.
This equation makes it possible to calculate recursively the value of polynomial, using a tail recursion. An accumulator in this case is simply a value of the processed part of polynomial:
polvalue :: (Num a) => [a]->a->a
polvalue coeffs x = polvalue' 0 coeffs x

polvalue' :: (Num a) => a->[a]->a->a
polvalue' acc [] x = acc
polvalue' acc (h:t) x = polvalue' (acc*x + h) t x
In the last line of code, the pattern (h:t) decomposes the list of coefficients (its unprocessed part) into head and tail. We split one coefficient h from the beginning of the list (of yet unprocessed coefficients) and calculate the new value of accumulator
    acc*x + h
according to the Horner scheme. When an unprocessed part of the list is exausted, the accumulator contains the value of polynomial in the point x.

9 Jan 2018, Tuesday

Lecture 4

Parsing in Haskell

Implemenation of expression calculator in Haskell. Two stages of complation: lexical analysis (performed by scanner) and syntactic analysis (performed by parser). A scanner splits input string into a list of lexemes (tokens), then the list of lexemes is passed to a parser. A parser perform the task of parsing, as a result we can construct a derivation tree, calculate a value of expression, translate a sentence to another language etc.

The source of expression calculator: "Calc.hs".

10 Jan 2018, Wednesday

Lecture 5

Constructing Our Own Types in Haskell

The data keyword defines a new type. Two ways of defining a type: just a sequence of type fields, like

    data R2Vector = R2Vector Double Double
and structure-style definition, where we give names to data fields:
    data R2Vector = R2Vector {
        cx :: Double,
        cy :: Double
    }
Usually, new types should implement some useful interfaces ("type classes" in Haskell), like Show, Read, Eq, Ord. We use the keyword deriving for this:
    data R2Vector = R2Vector Double Double deriving (Show, Read, Eq, Ord)
or, in structure-like style,
    data R2Vector = R2Vector {
        cx :: Double,
        cy :: Double
    } deriving (Show, Read, Eq, Ord)

The field names in structure-like style act as functions that extract the corresponding values from objects. Examples:

    Prelude> let u = R2Vector 1 2
    Prelude> let v = R2Vector { cx=3, cy=4 }
    Prelude> cx u
    1.0
    Prelude> cy v
    4.0

To work with our own types, we can define various functions. For example, we can define length of vector, sum and scalar (or dot) product of vectors:

    vectorLength :: R2Vector->Double
    vectorLength v = sqrt ((cx v)^2 + (cy v)^2)

    addVectors :: R2Vector->R2Vector->R2Vector
    addVectors u v = R2Vector (cx u + cx v) (cy u + cy v)

    scalarProduct :: R2Vector->R2Vector->Double
    scalarProduct u v = cx u * cx v + cy u * cy v

A module can export our types and functions, we can indicate, which types & functions to export and which should be kept private. To do this, we use the module declaration at the beginning of file. For example, we can export the type R2Vector and 3 functions mentioned above:

    module R2Graph (
        R2Vector(..),
        vectorLength,
        addVectors,
        scalarProduct
    ) where
The text after "where" line contains all definitions of types and functions (public and private). Two dots in parentheses here
        R2Vector(..),
mean that we export all value constructors for the type R2Vector.

With the type keyword we can define type synonyms for existing types without constructing new types. For example, in Haskell the type String is just a synonym of the list of characters, it might be defined as

    type String = [Char]
Here the keyword type does not introduce a new type! New types are defined with the data keyword.

As an important example, we consider a module R2Graph that support 2-dimensional graphics: file "R2Graph.hs". It defines the types R2Vector, R2Point, Triangle and various functions to work with them. Using such objects and functions, we can solve various geometric tasks on a plane, like find an intersection of two straight lines or line segments, calculate an angle between vectors, a distance from a point to a line, an area of a triangle, etc.

Recursive Data Structures

. . .

Search tree example: "SearchTree.hs".

. . .

11 Jan 2018, Thirsday

Lecture 6

Introduction to Python

Position of Python among other programming languages: object oriented language with some features of functional languages (lists maniplations, lambda-functions, etc.). It is pure object oriented language without a strict typization (variables do not have types in Python, they just points to objects; more correctly, variables contain IDs, or handles, of objects).

Some features of Python: it supports unbounded integers; it has a nice "for" loop; it has an elegant way of list definition, so called "list comprehension". Python can be used as a compiler or an interpretator, the latter makes it possible to use Python as a fast and convenient calculator.

Examples of programs:

12 Jan 2018, Friday

Lecture 6

Classes in Python

Defining new types — the classes — in Python. Difference between classes in C++, Java and other statically typed languages and Python that uses dinamic types. Ceating enumerated types in Python; type NonType and the object None (similar to zero pointer NULL in C/C++). Implementation of constructor and typical matemathical operations for Python classes. Examples of projects: evaluation expressions in reverse polish notation. Class R2Vectoras a typical example of class that implements a mathematical object. Using of reference (or recursive) objects, like trees and graphs. Example: the program "Guess an Animal" that illustrate using a tree and have some features of artificial intelligence.

Control Work

  1. Print all permutations of length n.
  2. Print all perfect numbers <= 10000.
  3. Calculate the number of happy tickes of length n.
  4. Factorize an integer number n: program must return a list of pairs [(prime factor, its power), ...]. For example, if n=180, then the factorization of n is the following list:
            [(2, 2), (3, 2), (5, 1)]