Difference between revisions of "Functional C++"

From Tuxamito
Jump to: navigation, search
(Created page with " {| class="wikitable" !colspan="2" style="text-align: center; background-color:#cccccc;"|Function Equivalence |- |style="text-align: center; background-color:#e8e8e8;"|'''Has...")
 
 
(7 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
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:
 +
<syntaxhighlight lang="cpp">
 +
#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();
 +
}
 +
</syntaxhighlight>
 +
 +
<pre>
 +
2
 +
1
 +
</pre>
 +
 +
Passing arguments by reference (identities):
 +
<syntaxhighlight lang="cpp">
 +
#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();
 +
}
 +
</syntaxhighlight>
 +
 +
<pre>
 +
2
 +
2
 +
</pre>
 +
 +
Passing arguments by reference (identities) but making them non modificable:
 +
<syntaxhighlight lang="cpp">
 +
#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();
 +
}
 +
</syntaxhighlight>
 +
 +
<pre>
 +
error: increment of read-only reference ‘y’
 +
  y++;
 +
</pre>
 +
---
 +
 +
=== Lambda (value vs reference) ===
 +
 +
Capturing by reference:
 +
<syntaxhighlight lang="cpp">
 +
#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;
 +
    });
 +
}
 +
</syntaxhighlight>
 +
 +
<pre>
 +
15
 +
15
 +
15
 +
15
 +
15
 +
</pre>
 +
 +
Capturing by value:
 +
<syntaxhighlight lang="cpp">
 +
#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;
 +
    });
 +
}
 +
</syntaxhighlight>
 +
 +
<pre>
 +
10
 +
11
 +
12
 +
13
 +
14
 +
</pre>
 +
---
 +
 +
 +
 +
---
 +
 +
== Building Blocks ==
  
 
{| class="wikitable"
 
{| class="wikitable"
Line 8: Line 189:
 
|-
 
|-
 
|map
 
|map
|
+
|for_each
 
|-
 
|-
 
|foldl
 
|foldl
|
+
|accumulate
 +
|-
 +
|foldr
 +
|accumulate
 +
|-
 +
|filter
 +
|copy_if
 
|-
 
|-
 
|replicate
 
|replicate
|
+
|fill_n
 
|}
 
|}
 +
 +
=== map ===
 +
 +
<syntaxhighlight lang="cpp">
 +
template<class InputIterator, class Function>
 +
  Function for_each(InputIterator first, InputIterator last, Function fn)
 +
{
 +
  while (first!=last) {
 +
    fn (*first);
 +
    ++first;
 +
  }
 +
  return move(fn);
 +
}
 +
</syntaxhighlight>
 +
 +
 +
<syntaxhighlight lang="cpp">
 +
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;
 +
}
 +
</syntaxhighlight>
 +
 +
=== foldl ===
 +
 +
<syntaxhighlight lang="cpp">
 +
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;
 +
}
 +
</syntaxhighlight>
 +
 +
=== foldr ===
 +
 +
user rbegin and rend
 +
 +
<syntaxhighlight lang="cpp">
 +
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;
 +
}
 +
</syntaxhighlight>
 +
 +
=== filter ===
 +
 +
<syntaxhighlight lang="cpp">
 +
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;
 +
}
 +
</syntaxhighlight>
 +
 +
=== replicate ===
 +
 +
<syntaxhighlight lang="cpp">
 +
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;
 +
}
 +
</syntaxhighlight>
 +
 +
 +
<syntaxhighlight lang="cpp">
 +
template <class ForwardIterator, class T>
 +
  void fill (ForwardIterator first, ForwardIterator last, const T& val)
 +
{
 +
  while (first != last) {
 +
    *first = val;
 +
    ++first;
 +
  }
 +
}
 +
</syntaxhighlight>

Latest revision as of 13:39, 13 January 2015

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;
  }
}