Difference between revisions of "Functional C++"
(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
---
Contents
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;
}
}