Awesome

(Concepts-enabled) Functional Abstraction Layer for C++

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.

Dependencies

• C++20: Also requires concepts library as well
• CMake >= 3.13.0

Available typeclasses

Monoid

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.

Instances

• basic_types - integral types and std::string
• std_containers - single socket std:: containers
• std_optional - std::optional
• with_functions - any type that has empty and append methods

Foldable

Has foldLeft function.

Instances

• std_containers - single socket std:: containers
• std_ranges - std::ranges::views
• with_functions - any type that has foldLeft or fold_left method

Functor

Has unit and map functions. Also provides innerMap function for Functor of Functors.

Instances

• from_foldable - types that have instances for Monoid and Foldable
• std_optional - std::optional
• std_ranges - std::ranges::views
  • with_functions - any type that has unit and map methods

Monad

Has flatMap function and also is a Functor. Also provides innerFlatMap function for Functor of Monads.

Instances

• from_foldable - types that have instances for Monoid and Foldable
• std_optional - std::optional
• with_functions - any type that has flatMap or flat_map method and also is a Functor

Filterable

Has filter function. Also provides innerFilter function for Functor of Filterables.

Instances

• from_foldable - types that have instances for Monoid and Foldable. Either SingletonFrom helper or Functor is also required.
• std_optional - std::optional
• std_ranges - std::ranges::views
• with_functions - any type that has filter method

Converter

Has as function. Allows to modify the shape.

Instances

• 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::containers
• from_std_optional - from std::optional to any functor+monoid

Usage

All 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.

Lvalue vs rvalue

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.

Performance

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:

• int - as an example of lightweight type without any extra memory allocations
• Expensive - custom type that has memory allocation performed in constructor and copy constructor, but can be cheaply moved
• For Maps of expensive type we use int as key and Expensive as value. There is one exception - extra map2 in 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:

• std::vector: 10kk for int and 25k for Expensive
• std::list: 1kk for int and 25k for Expensive
• std::deque: 10kk for int and 25k for Expensive
• std::set: 100k for int and 25k for Expensive
• std::unordered_set: 100k for int and 25k for Expensive
• std::map: 100k for int and 25k for Expensive
• std::unordered_map: 100k for int and 25k for Expensive

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:

• Immutable - initial container is taken by lvalue and is not modified
• Mutable - Initial container is taken by rvalue and can be modified

Std references:

• For map() we use std::transform (either to new or to same container). If it is vector and immutable - we reserve() destination as well
• For filter() we use std::erase_if either on copy of container or on initial container

Map 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.

map() for int

map() for Expensive

filter() for int

filter() for Expensive

Observations on benchmark results

• Immutable map() is on par with std::transform
• For vector-like (vector, list, deque) containers mutable 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)
• There is no mutable "single call" 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 std
• For maps - performance is similar as for set-like containers. There is one extra interesting point - std::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 accepted
• filter() 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 above
• For immutable containers except vector filter() 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)
• Benchmarks for mapping to another inner type also exist in source code (not added here for brevity).
  • For immutable containers they show pretty much the same results (i.e. almost equal between cefal and std).
  • For mutable containers of ints it is also on the same level.
  • Mutable cefal benchmarks for move-effective types though shows better performance than immutable cefal/std on all containers except unordered_set (where it is on par).

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).

Examples

Piped form

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

Curried form

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

Ranges materialization

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>();

Custom class support

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

Custom class support through class methods

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