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.)
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]]
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]
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.
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 = xOtherwise, 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
myGcd x y = myGcd y (x `mod` y)
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
p_{n} = a_{0} x^{n} + a_{1} x^{n-1} + ... + a_{n}is a polynomial of degree n, and p_{n+1} is a polynomial of degree n+1, which is obtained by adding a coefficient a_{n+1} to the end of the list. Then we have the equation:
p_{n+1} = p_{n} x + a_{n+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 xIn 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 + haccording to the Horner scheme. When an unprocessed part of the list is exausted, the accumulator contains the value of polynomial in the point x.
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".
The data keyword defines a new type. Two ways of defining a type: just a sequence of type fields, like
data R2Vector = R2Vector Double Doubleand 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 ) whereThe 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.
. . .
Search tree example: "SearchTree.hs".
. . .
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:
[(2, 2), (3, 2), (5, 1)]