Functional programming

APM 50179 EP


double discount_factor(double rate, double maturity)
{
  double res = std::exp(-rate * maturity);
  return res;
}

void print_discount_factor(double rate, double maturity)
{
  double df = discount_factor(rate, maturity);
  std::cout << "DF(" << maturity << "," << rate << ") = " << df << std::endl;
  // No return statement here
}


return_type function_name(arg1_type arg1_name, arg2_type arg2_name[,...])
{
  optional_return_statement;
}

The semantic of argument passing is the same as the semantic of initialization


double discount_factor(double rate, double maturity)
{
  return std::exp(-rate * maturity);
}

double df = discount_factor(0.04, 2);

is equivalent to


double rate = 0.04;
double maturity = 2.5;
// jump to discount_factor code in memory
return std::exp(-rate * maturity);

Type checking


double discount_factor(double rate, double maturity) { ... }
int main(int argc, char* argv[])
{
  const char* rate = "0.04";
  double r = 0.04;
  double m = 2.5;
  discount_factor(rate, m); // Error
  discount_factor(r, m);    // Ok
  return 0;
}

Arguments conversion


double discount_factor(double rate, double maturity) { ... }
int main(int argc, char* argv[])
{
  const char* rate = "0.04";
  double r = 0.04;
  int m = 2;
  discount_factor(rate, m); // Error
  discount_factor(r, m);    // Ok
  return 0;
}

Default argument


double discount_factor(double rate, double maturity) { ... }
double d = discount_factor(0.04); // Error


double discount_factor(double rate, double maturity = 1.) { ... }
double d = discount_factor(0.04); // OK - Equivalent to discount_factor(0.04, 1.)
double d = discount_factor(0.04, 2.5) // OK, does not use the default argument


double discount_factor(double rate = 0.01, double maturity) { ... } // Illegal
double my_function(double a1, double a2 = 0., double a3) { ... }    // Illegal


double f1() { }             // Error: no return value
void   f2() { }             // OK
double f3() { return 1.2; } // OK
void   f4() { return 1.2; } // Error: void function
double f5() { return; }     // Error: missing return value
void   f6() { return; }     // OK
double f7() { return "7"; } // Error: wrong return type
double f8() { return 1; }   // OK: conversion from int to double

Let the compiler deduce the type


auto f1() { double d = 2.3; return d; } // OK
int  f2() { auto i = 4; return i; }     // OK
auto f3() { auto i = 2; return i; }     // OK
int  f4(auto d) { ... }                 // Error: auto cannot be used for arguments

Open the notebook quicksort and follow the instructions


void inc(int i1, int i2)
{
  ++i1;
  ++i2;
}

void client()
{
  int i = 4;
  int j = 5;
  inc(i, j);
  std::cout << "i = " << i << std::endl;
  std::cout << "j = " << j << std::endl;
}


int i = 4;
int& j = i;
++j;
std::cout << i << std::endl;


int& j; // Error: reference must be initialized
int i = 4;
int j& = i;
int k = 8;
j = k;
++j;
std::cout << i << std::endl;
std::cout << k << std::endl;


void inc(int& i1, int& i2)
{
  ++i1;
  ++i2;
}

void client()
{
  int i = 4;
  int j = 5;
  inc(i, j);
  std::cout << "i = " << i << std::endl;
  std::cout << "j = " << j << std::endl;
}


std::vector<double> discount_factor(std::vector<double>& rate, std::vector<double>& maturity)
{
  std::size_t size = rate.size();
  std::vector<double> res(size);
  for(size_t i = 0; i < size; ++i)
  {
    rate[i] = std::exp(-rate[i] * maturity[i]); // Side-effect, the passed argument is changed!
  }
  return res;
}


std::vector<double> discount_factor(const std::vector<double>& rate, const std::vector<double>& maturity)
{
  std::size_t size = rate.size();
  std::vector<double> res(size);
  for(size_t i = 0; i < size; ++i)
  {
    rate[i] = std::exp(-rate[i] * maturity[i]); // Error, cannot modify a const object
  }
  return res;
}


void discount_factor(const std::vector<double>& rate, const std::vector<double>& maturity,
std::vector<double>& res)
{
  std::size_t size = rate.size();
  res.resize(size);
  for(size_t i = 0; i < size; ++i)
  {
    res[i] = std::exp(-rate[i] * maturity[i]);
  }
}

Fix the quicksort implementation


std::vector<double> discount_factor(const std::vector<double>& rate, const std::vector<double>& maturity);

int main(int argc, char* argv[])
{
  double df = discount_factor(0.04, 1.5); // error, cannot convert parameter 1 ...
  return 0;
}


int main(int argc, char* argv[])
{
  std::vector<double> res = discount_factor(std::vector<double>(1, 0.04), std::vector<double>(1, 1.5));
  double df = res[0];
  return 0;
}


std::vector<double> discount_factor(const std::vector<double>& rate, const std::vector<double>& maturity);
double discount_factor(double rate, double maturity);

int main(int argc, char* argv[])
{
  std::vector<double> r(3, 0.04);
  std::vector<double> m(3, 1.5);
  std::vector<double> df_vec = discount_factor(r, m);
  double df = discount_factor(0.04, 1.5);
  return 0;
}


void print(long);
void print(double);

void client()
{
  long l = 1L;
  double d = 1.5;
  int i = 1;
  print(l);         // Ok, calls print(long)
  print(d);         // Ok, calls print(double)
  print(i);         // Error, ambiguous
  print(long(i));   // Ok, calls print(long)
  print(double(i)); // Ok, calls print(double)
}


int    f(int, int);
void   f(int, int); // Illegal, overloaded function cannot differ only by return type
double f(double, double); // Ok


int f(int, int);
// f's type     : int (int, int)
// f's signature: (int, int)

Containers
Iterators
Algorithms

Manage collections of objects of a certain kind
Sequential containers (vector, list, deque...)
Associative containers (map, set, unordered_map...)

Abstraction for stepping through containers
Provide decoupling between containers and algorithms

Act on containers through iterators
Non-modifying sequence operations (find, search, count...)
Modyfing sequence operations (copy, transform, generate...)

www.cppreference.com

std::vector
std::array
std::string
std::list
std::forward_list
std::stack
std::deque
std::queue
std::priority_queue


#include <vector>

std::vector<double> v1;
std::vector<double> v2(10);
std::vector<double> v3(10, 2);
std::vector<double> v4 = { 1., 2., 4., 6., 7. };


std::vector<double> v(10, 1.);
v[2] = 4.5;
double d0 = v[4];
double d1 = v.front();
double d2 = v.back();
size_t s = v.size();


std::vector<double> v5(v4);
std::vector<double> v6 = v4;


v3.resize(10);
v4.reserve(10);
v4.push_back(2.5);
v5.clear();


std::vector<double> v = { 1., 2., 3., 4., 5. };

auto iter = v.begin();
auto iter_end = v.end();
std::cout << *iter << std::endl; // 1.


++iter;
std::cout << *iter << std::endl; // 2.


iter += 2;
std::cout << *iter << std::endl; // 4.


*iter = 10; // v[3] = 10.
std::cout << *iter << std::endl; // 10


--iter;
std::cout << *iter << std::endl; // 3.


std::cout << iter[2] << std::endl; // 5.

Open the notebook Gray-Scott and follow the instructions


#include <algorithm>
#include <numeric>
#include <vector>
std::vector<double> a = { 1., 2., 3., 4., 5., 6. };
std::vector<double> b = { 4., 7., 5., 4. };


std::copy(b.begin(), b.end(), ++(a.begin()));
// => a == { 1., 4., 7., 5., 4., 6. }

auto n = std::count(a.begin(), a.end(), 4.);
// => n == 2

auto iter = std::find(a.begin(), a.end(), 7.);
// => iter == (a.begin()) + 2

double res = std::accumulate(b.begin(), b.end(), 0.);
// => res == 20


#include <functional>

void test()
{
  std::plus<double> f;
  std::cout << f(1.0, 2.0) << std::endl;
  std::multiplies<double> f2;
  std::cout << f2(1.0, 2.0) << std::endl;
}


std::vector<double> b = { 4., 7., 5., 4. };

double res = std::accumulate(b.begin(), b.end(), 1., std::multiplies<double>());
// => res == 560.


#include <algorithm>
#include <numeric>
#include <vector>
std::vector<double> a = { 1., 2., 3., 4., 5., 6. };
std::vector<double> b = { 6., 4., 2., 5., 3., 1. };
std::vector<double> res(6);


std::transform(a.begin(), a.end(), res.begin(), std::negate());
// => res == { -1., -2., -3., -4., -5., -6. }

std::transform(a.begin(), a.end(), b.begin(), res.begin(), std::plus());
// => res == { 7., 6., 5., 9., 8., 7. };

using namespace std::placeholders;
int c = std::count_if(a.begin(), a.end(), std::bind(std::greater(), _1, 3.));
// c == 3


inline bool is_odd(int i)
{
  return i % 2 == 1;
}

std::vector<int> v = { 1, 2, 3, 4 };
int n = std::count_if(a.begin(), a.end() is_odd);


auto lbd = [](int n) { return n%2 == 1; };
int n = std::count_if(a.begin(), a.end(), lbd);


int n = std::count_if(a.begin(), a.end(), [](int n) { return n%2 == 1; });


void amplify(std::vector<double>& sig, double factor, double floor, double ceil)
{
  std::transform(sig.begin(), sig.end(), [](double v)
  {
    return std::max(floor, std::min(ceil, factor*v)); // Compilation error
  });
}


void amplify(std::vector<double>& sig, double factor, double floor, double ceil)
{
  std::transform(sig.begin(), sig.end(), [factor, floor, ceil](double v)
  {
    return std::max(floor, std::min(ceil, factor*v));
  });
}

[] - captures nothing
[=] - captures all by value
[&] - captures all by reference
[var1] - captures var1 by value
[&var2] - captures var2 by reference
[=,&var2] - captures all by value, but var2 by reference
[var1, &var2]


auto get_functor(double factor)
{
  double factor_twice = 2 * factor;
  auto lambda = [&factor_twice](double arg) { return factor_twice * arg; };
  return lambda;
}


void test()
{
  auto lambda = get_functor(2.5);
  double res = lambda(1.5); // Boom!
}


std::vector<std::vector<double>> m1 = { ... };
std::vector<std::vector<double>> res = { ... };

std::for_each(m1.begin(), m1.end(), res.begin(), [](const std::vector<double>& v) {
  // ...
});


std::for_each(m1.begin(), m1.end(), res.begin(), [](const auto& v) {
  // ...
});


std::vector<double> v = { ... };
double d = 2.4;
std::gtransform(v.begin(), v.end(), v.begin(), [d](double v) { return v + d; });


std::vector<double> v = { ... };
std::gtransform(v.begin(), v.end(), v.begin(), [d=2.3](double v) { return v + d; });


std::vector<string> filename(5);
std::generate(ilename.begin(), filename.end(), [i = 0]() { return "myname" + std::to_string(i++); }); // Error


std::vector<string> filename(5);
std::generate(ilename.begin(), filename.end(), [i = 0]() mutable { return "myname" + std::to_string(i++); });

Open the notebook kmeans and follow the instructions

map
multi_map
set
multiset
unordered_map
unordered_multimap
unordered_set
unordered_multiset


#include <map>
#include <string>

std::map<std::string, int> m;
std::map<std::string, int> m = {{"a", 2}, {"c", 6}};


std::map<std::string, int> m;
m["a"] = 2;
int ma = m["a"];
int mb = m["b"]; // Creates a new entry ("b", uninitialized) in the map
auto iter = m.find("c"); // returns m.end();
size_t = m.size();


std::map<std::string, int> m;
std::map<std::string, int> m2(m);
std::map<std::string, int> m3 = m;


std::map<std::string, int> m;
auto itp = m.insert({"a", 3});
// itp.first == m.begin(), itp.second == true
auto itp2 = m.insert({"a", 4});
// itp.first == m.begin(), itp.second == false
m.clear();

Functional programming

APM 50179 EP

Function definition

Arguments

Arguments

Arguments

Arguments

Return value

auto

Exercise

Reference

Reference

Reference

Const reference

const reference

const reference

Exercise

Function overloading

Function overloading

Function overloading

Function overloading

STL concepts

Containers

Iterators

Algorithms

Documentation

Sequential containers

std::vector

std::vector

Iterators

Iterators

Exercise

Algorithms 1/2

Functors

Algorithm 2/2

Lambda

Lambda

Lambda capture

Dangling reference

Lambda and auto

Initializing in lambda capture

Exercise

Associative containers

std::map

std::map