Functional C++

From Tuxamito
Revision as of 14:39, 13 January 2015 by Daniel (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

C++ is a multiparadigm, many level of abstracions, and very little overhead - runtime cost.

Usually procedural, object-oriented, but functional style is also possible. Not strictly functional, but possible to use problem solving schemas and basic bulding blocks (working with values as opposed to identities)

C++ 11 standard expands this support with lambdas


immutable data structures that maintains the speed C++ is known for while providing the protection that functional languages

---

Concepts (immutable data structures)

Values vs. Identities

Passing arguments by value:

#include <iostream>

using namespace std;

void f2(int y) {
  y++;
  cout << y << endl;
}

void f1() {
  int x;
  x = 1;

  f2(x);

  cout << x << endl;
}

int main() {
  f1();
}
2
1

Passing arguments by reference (identities):

#include <iostream>

using namespace std;

void f2(int& y) {
  y++;
  cout << y << endl;
}

void f1() {
  int x;
  x = 1;

  f2(x);

  cout << x << endl;
}

int main() {
  f1();
}
2
2

Passing arguments by reference (identities) but making them non modificable:

#include <iostream>

using namespace std;

void f2(int& y) {
  y++;
  cout << y << endl;
}

void f1() {
  int x;
  x = 1;

  f2(x);

  cout << x << endl;
}

int main() {
  f1();
}
error: increment of read-only reference ‘y’
   y++;

---

Lambda (value vs reference)

Capturing by reference:

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>

using namespace std;

int main() {
  vector<function<int()>> vfunctors;
  int x;

  x = 10;

  for(int i=0; i<5; i++) {
    vfunctors.push_back([&]{return x;});
    x++;
  }

  for_each(begin(vfunctors), end(vfunctors), [](function<int()> f) {
      cout << f() << endl;
    });
}
15
15
15
15
15

Capturing by value:

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>

using namespace std;

int main() {
  vector<function<int()>> vfunctors;
  int x;

  x = 10;

  for(int i=0; i<5; i++) {
    vfunctors.push_back([=]{return x;});
    x++;
  }

  for_each(begin(vfunctors), end(vfunctors), [](function<int()> f) {
      cout << f() << endl;
    });
}
10
11
12
13
14

---


---

Building Blocks

Function Equivalence
Haskell C++
map for_each
foldl accumulate
foldr accumulate
filter copy_if
replicate fill_n

map

template<class InputIterator, class Function>
  Function for_each(InputIterator first, InputIterator last, Function fn)
{
  while (first!=last) {
    fn (*first);
    ++first;
  }
  return move(fn);
}


template <class InputIterator, class OutputIterator, class UnaryOperator>
  OutputIterator transform (InputIterator first1, InputIterator last1,
                            OutputIterator result, UnaryOperator op)
{
  while (first1 != last1) {
    *result = op(*first1);  // or: *result=binary_op(*first1,*first2++);
    ++result; ++first1;
  }
  return result;
}

foldl

template <class InputIterator, class T>
   T accumulate (InputIterator first, InputIterator last, T init)
{
  while (first!=last) {
    init = init + *first;  // or: init=binary_op(init,*first) for the binary_op version
    ++first;
  }
  return init;
}

foldr

user rbegin and rend

template <class InputIterator, class T>
   T accumulate (InputIterator first, InputIterator last, T init)
{
  while (first!=last) {
    init = init + *first;  // or: init=binary_op(init,*first) for the binary_op version
    ++first;
  }
  return init;
}

filter

template <class InputIterator, class OutputIterator, class UnaryPredicate>
  OutputIterator copy_if (InputIterator first, InputIterator last,
                          OutputIterator result, UnaryPredicate pred)
{
  while (first!=last) {
    if (pred(*first)) {
      *result = *first;
      ++result;
    }
    ++first;
  }
  return result;
}

replicate

template <class OutputIterator, class Size, class T>
  OutputIterator fill_n (OutputIterator first, Size n, const T& val)
{
  while (n>0) {
    *first = val;
    ++first; --n;
  }
  return first;
}


template <class ForwardIterator, class T>
  void fill (ForwardIterator first, ForwardIterator last, const T& val)
{
  while (first != last) {
    *first = val;
    ++first;
  }
}