Cefal is a C++20 header-only library with abstractions over basic functional programming concepts (and using C++20 concepts).
It is more a research pet project than a production-ready library (especially keeping in mind it compiles only on GCC/master for now).
Tests exist though and benchmarks as well.
See examples for general idea about what it looks like or check src/dummy.cpp
.
>= 3.13.0
Has empty
and append
functions. For sake of performance helpers::SingletonFrom
exists that can be used to wrap single element of monoidal container and pass it as right operand to append to avoid extra memory allocations.
basic_types
- integral types and std::stringstd_containers
- single socket std:: containersstd_optional
- std::optionalwith_functions
- any type that has empty
and append
methodsHas foldLeft
function.
std_containers
- single socket std:: containersstd_ranges
- std::ranges::viewswith_functions
- any type that has foldLeft
or fold_left
methodHas unit
and map
functions. Also provides innerMap
function for Functor of Functors.
from_foldable
- types that have instances for Monoid and Foldablestd_optional
- std::optional
std_ranges
- std::ranges::viewswith_functions
- any type that has unit
and map
methodsHas flatMap
function and also is a Functor. Also provides innerFlatMap
function for Functor of Monads.
from_foldable
- types that have instances for Monoid and Foldablestd_optional
- std::optionalwith_functions
- any type that has flatMap
or flat_map
method and also is a FunctorHas filter
function. Also provides innerFilter
function for Functor of Filterables.
from_foldable
- types that have instances for Monoid and Foldable. Either SingletonFrom helper or Functor is also required.std_optional
- std::optionalstd_ranges
- std::ranges::viewswith_functions
- any type that has filter
methodHas as
function. Allows to modify the shape.
from_self
- Converter to same type. Doesn't do anything, just returns the same object.from_std_containers
- from std::range (i.e. std::containers and range views) to std::containersfrom_std_optional
- from std::optional to any functor+monoidAll typeclasses can be loaded with cefal/cefal
header. No instances are loaded automatically, they need to be loaded on one-by-one basis (cefal/everything.h
exists though with all the instances added, but is not recommended to use).
All concepts are in cefal::concepts
namespace.
All instances should be implemented in cefal::instances
namespace.
All operations are in cefal::ops
namespace and can be used either through pipe operator or with currying.
All operations on lvalue operands expect constref arguments of functions, passed to them (except accumulator for foldLeft, which is rvalue).
All operations on rvalue operands can work with rvalue as well.
The only exception is operations on ranges. They are done in compliance with how ranges work and on both lvalue and rvalue expect either constref or ref (from where it is possible to move).
Be aware though that moving from ranges operation sometimes can be more expensive than copying due to extensive optimizations compilers could do on ranges. For example, check mutable vs immutable benchmarks for map()
on ranges for case when it works with Expensive<int>
and converts it to different type. On -O3
level immutable benchmark is faster roughly 2-3 times.
Due to cefal being mostly a wrapper around std or user implementations - overhead should be minimal.
For std::containers and map/filter operations few non-pure optimizations are in place to provide performance similar to using std
algorithms. Cefal also contains Catch2-based benchmarks for std::containers as for something that can be both heavy enough to process and comparable with other implementation (std
algorithms).
Ranges-based benchmarks are available as well, but their numbers are not presented below due to being the same across std::ranges::views
and cefal::ops
.
For benchmarks we use next value types:
map()
for Expensive as key and int as value.Container sizes are not the same for different containers (otherwise it would either take too much time for slow ones or too less for fast ones), so different containers can't be compared, but containers used for cefal and std are the same size:
Multi versions of sets are also benchmarked, but are similar to single-entry sets and are omitted in results below for brevity.
There are two types of benchmarks:
Std references:
map()
we use std::transform
(either to new or to same container). If it is vector and immutable - we reserve()
destination as wellfilter()
we use std::erase_if
either on copy of container or on initial containerMap benchmarks transform container to same type (to make it similar between lvalue and rvalue).
Filter benchmarks are also divided by percentage of items that are accepted.
All values are from mean
section of catch2 benchmarks in milliseconds (captured on MBP15'2014 with i7).
Std library is from GCC/master (commit 73dd051894b8293d35ea1c436fa408c404b80813, April 1 2020) and all benchmarks are built with -O3
.
Type | vector | list | deque | set | unordered_set | map | unordered_map |
---|---|---|---|---|---|---|---|
Immutable cefal | 23.028 | 183.425 | 58.212 | 29.585 | 21.127 | 28.193 | 21.389 |
Immutable std | 27.566 | 182.485 | 57.714 | 26.922 | 19.716 | 27.418 | 18.953 |
Mutable cefal | 2.998 | 4.191 | 6.875 | 10.857 | 6.689 | 10.912 | 6.491 |
Mutable std | 3.007 | 4.258 | 9.540 | N/A | N/A | N/A | N/A |
Type | vector | list | deque | set | unordered_set | map | map 2 | unordered_map |
---|---|---|---|---|---|---|---|---|
Immutable cefal | 60.766 | 65.032 | 61.077 | 72.307 | 74.978 | 76.555 | 76.553 | 74.536 |
Immutable std | 67.383 | 65.151 | 61.076 | 75.573 | 74.242 | 77.113 | 90.504 | 72.470 |
Mutable cefal | 0.052 | 0.102 | 0.034 | 2.051 | 1.954 | 2.378 | 2.621 | 1.958 |
Mutable std | 15.692 | 16.074 | 16.077 | N/A | N/A | N/A | N/A | N/A |
Type | 10% | 25% | 50% | 75% | 90% |
---|---|---|---|---|---|
vector | |||||
Immutable cefal | 40.744 | 43.751 | 49.754 | 53.399 | 55.552 |
Immutable std | 45.551 | 45.623 | 48.697 | 48.261 | 48.471 |
Mutable cefal | 37.466 | 37.475 | 37.419 | 37.514 | 37.774 |
Mutable std | 37.247 | 37.446 | 40.523 | 40.479 | 40.574 |
list | |||||
Immutable cefal | 21.108 | 47.129 | 94.010 | 139.376 | 164.344 |
Immutable std | 185.323 | 191.391 | 196.062 | 191.282 | 184.193 |
Mutable cefal | 98.675 | 83.869 | 59.218 | 30.941 | 14.719 |
Mutable std | 88.463 | 79.781 | 61.182 | 24.538 | 10.800 |
deque | |||||
Immutable cefal | 47.505 | 53.606 | 64.657 | 76.670 | 79.651 |
Immutable std | 88.113 | 86.789 | 86.097 | 86.738 | 83.507 |
Mutable cefal | 59.539 | 56.142 | 51.801 | 46.972 | 43.073 |
Mutable std | 59.425 | 56.518 | 51.882 | 47.131 | 43.188 |
set | |||||
Immutable cefal | 4.142 | 7.353 | 13.856 | 20.538 | 25.234 |
Immutable std | 24.654 | 23.563 | 22.448 | 21.922 | 20.884 |
Mutable cefal | 11.688 | 9.444 | 6.159 | 3.257 | 2.109 |
Mutable std | 11.397 | 9.375 | 6.332 | 3.249 | 2.075 |
unordered_set | |||||
Immutable cefal | 4.497 | 6.823 | 10.945 | 14.873 | 19.134 |
Immutable std | 17.767 | 17.242 | 16.952 | 17.331 | 16.105 |
Mutable cefal | 9.191 | 7.583 | 4.294 | 2.411 | 1.219 |
Mutable std | 9.211 | 7.589 | 4.337 | 2.531 | 1.173 |
map | |||||
Immutable cefal | 4.380 | 8.136 | 14.588 | 21.912 | 26.258 |
Immutable std | 24.813 | 23.844 | 22.642 | 22.029 | 21.045 |
Mutable cefal | 11.642 | 9.634 | 6.436 | 3.591 | 2.157 |
Mutable std | 11.673 | 9.476 | 6.278 | 3.345 | 2.078 |
unordered_map | |||||
Immutable cefal | 4.831 | 7.403 | 11.795 | 16.069 | 19.637 |
Immutable std | 18.383 | 18.710 | 17.370 | 16.854 | 16.475 |
Mutable cefal | 9.716 | 7.978 | 4.654 | 2.555 | 1.308 |
Mutable std | 9.607 | 8.018 | 4.551 | 2.499 | 1.230 |
Type | 10% | 25% | 50% | 75% | 90% |
---|---|---|---|---|---|
vector | |||||
Immutable cefal | 11.629 | 29.254 | 58.915 | 89.071 | 106.378 |
Immutable std | 68.323 | 114.938 | 283.826 | 97.746 | 64.673 |
Mutable cefal | 34.500 | 56.911 | 157.366 | 38.797 | 8.523 |
Mutable std | 34.479 | 56.636 | 156.910 | 38.953 | 8.597 |
list | |||||
Immutable cefal | 6.208 | 15.706 | 31.769 | 47.632 | 57.195 |
Immutable std | 65.371 | 66.365 | 67.938 | 66.414 | 65.897 |
Mutable cefal | 40.173 | 81.944 | 241.911 | 46.628 | 9.073 |
Mutable std | 32.853 | 28.317 | 20.106 | 10.978 | 5.090 |
deque | |||||
Immutable cefal | 6.014 | 15.288 | 29.776 | 45.084 | 53.986 |
Immutable std | 69.170 | 118.254 | 286.198 | 100.668 | 65.932 |
Mutable cefal | 39.759 | 80.341 | 240.852 | 47.481 | 8.812 |
Mutable std | 39.699 | 78.960 | 244.601 | 47.200 | 8.718 |
set | |||||
Immutable cefal | 21.834 | 31.497 | 48.266 | 65.367 | 76.619 |
Immutable std | 68.914 | 68.631 | 67.969 | 67.644 | 67.901 |
Mutable cefal | 33.821 | 29.160 | 20.652 | 11.234 | 5.362 |
Mutable std | 33.879 | 29.125 | 20.672 | 11.202 | 5.342 |
unordered_set | |||||
Immutable cefal | 21.802 | 31.021 | 47.717 | 78.145 | 77.942 |
Immutable std | 68.047 | 67.801 | 68.694 | 69.279 | 67.614 |
Mutable cefal | 33.652 | 28.704 | 20.570 | 11.367 | 5.485 |
Mutable std | 33.440 | 28.778 | 21.765 | 11.225 | 5.457 |
map | |||||
Immutable cefal | 7.176 | 18.088 | 34.954 | 53.145 | 63.102 |
Immutable std | 83.866 | 87.060 | 82.871 | 83.906 | 85.545 |
Mutable cefal | 33.768 | 30.118 | 21.740 | 11.470 | 5.764 |
Mutable std | 48.071 | 43.940 | 35.722 | 25.031 | 19.477 |
unordered_map | |||||
Immutable cefal | 7.502 | 17.510 | 34.283 | 63.619 | 65.634 |
Immutable std | 84.983 | 85.647 | 85.597 | 84.457 | 83.882 |
Mutable cefal | 35.043 | 30.765 | 21.955 | 11.599 | 5.544 |
Mutable std | 50.346 | 44.926 | 36.233 | 25.999 | 19.650 |
map()
is on par with std::transform
map()
for ints is on par, but for move-efficient types it is A LOT faster than std::transform
(numbers in table above are not a typo)std::transform
for set-like or associative containers, but mutable map()
for all inner types is much faster than immutable versions of both cefal and stdstd::transform
for std::map
of Expensive as key works slower than for case when Expensive is value. It doesn't happen for cefal::map()
and not reproducible on std::unordered_map
or on any filter/erase_if operations.filter()
is worse than std::erase_if
for mutable lists of both ints and Expensive and for vectors of Expensive in case when almost whole container is acceptedfilter()
is on par with std::erase_if
in case of immutable vector of small types and in case of all other mutable containers not mentioned abovefilter()
is either on par or better than std::erase_if
. Less elements are accepted - bigger the gap for in favor of filter()
(up to 10x in case of 10% elements accepted)As a general conclusion: there are for sure few cases where cefal shows itself worse than direct usage of std algorithm (not tremendously though), but there are also a lot of cases where cefal works faster by 1-2 orders of magnitude (especially in case of move-efficient types) and in remaining cases it is on par with std.
Cefal lacks laziness, but it can be achieved with std::ranges
(cefal has partial support for them as Foldable
, Functor
and Filterable
).
std::list<std::vector<int>> result =
cefal::unit<std::vector>(3) | cefal::ops::map ([](int x) { return ops::unit<std::vector>(x); })
| cefal::ops::innerFilter ([](int x) { return x % 2; })
| cefal::ops::innerFlatMap ([](int x) { return std::vector{x + 1, x + 2}; })
| cefal::ops::innerMap ([](int x) { return x * 3; })
| cefal::ops::as<std::list>();
auto rawToResult = cefal::ops::flatMap([](RawResult&& raw){ return maybeGetResult(std::move(raw)); };
std::optional<int> result = maybeGetRawResult() | rawToResult
| cefal::ops::map([](Result&& x) { return x.value(); });
auto mapper = cefal::ops::map([](int x) { return x * 3; });
auto result = mapper(cefal::unit<std::vector>(3));
auto left = cefal::unit<std::vector>(3);
auto anotherResult = cefal::ops::map([](int x) { return x * 3; })(left);
std::map<int, std::string> source = /*...*/;
std::unordered_map<int, std::string> mapResult =
source | std::views::filter([](const auto& x) {return x.first % 2; })
| cefal::ops::as<std::unordered_map>();
std::vector<std::pair<std::string, std::string>> vectorResult =
source | std::views::transform([](const auto& x) {return std::make_pair(std::to_string(x.first), x.second); })
| cefal::ops::as<std::vector>();
template <typename T>
class MyClass {
// ...
};
namespace cefal::instances {
template <typename T>
struct Functor<MyClass<T>> {
static MyClass<T> unit(T x) {
MyClass<T> result;
result.setValue(std::move(x));
return result;
}
static auto map(const MyClass<T>& src, Func&& func) {
using U = std::invoke_result_T<Func, T>;
MyClass<U> result;
result.setValue(func(src.value()));
return result;
}
};
}
MyClass<int> from = cefal::ops::unit<MyClass>(42);
MyClass<double> result = from | cefal::ops::map([](int x) -> double { return x * 2.0; });
template <typename T>
class MyClass {
static MyClass<T> unit(T x) {
MyClass<T> result;
result.setValue(std::move(x));
return result;
}
auto map(Func&& func) {
using U = std::invoke_result_T<Func, T>;
MyClass<U> result;
result.setValue(func(value()));
return result;
}
// ...
};
MyClass<int> from = cefal::ops::unit<MyClass>(42);
MyClass<double> result = from | cefal::ops::map([](int x) -> double { return x * 2.0; });