functional

Functional programming in C++

Why

The purpose of this library is to exercise an approach to functional programming in C++ on top of the existing std C++ vocabulary types (such as std::expected and std::optional), with the aim of eventually extending the future versions of the C++ standard library with the functionality found to work well.

Example

#include <fn/and_then.hpp>
#include <fn/utility.hpp>

#include <charconv>
#include <climits>
#include <numeric>
#include <string_view>
#include <type_traits>

enum NotANumber { notANumber };
enum DivByZero { divByZero };
enum Overflow { overflow };
enum Add { add };
enum Mul { mul };
enum Side { num, den };

class Rational {
  int n_, d_;
  constexpr Rational(int n, int d) noexcept : n_(n), d_(d) {}

public:
  constexpr bool operator==(Rational const &) const noexcept = default;
  template <Side S> constexpr friend int get(Rational const &r) noexcept
  {
    return S == num ? r.n_ : r.d_;
  }

  // The invariant lives in the type: `make` is the only way to build one, so every
  // Rational is reduced, sign-normalized and representable — callers receive a value they
  // never have to re-check.
  static constexpr auto make(long long n, long long d)
      -> fn::expected<Rational, fn::sum_for<DivByZero, Overflow>>
  {
    if (d == 0) return fn::unexpected{fn::sum{divByZero}};
    if (n == LLONG_MIN || d == LLONG_MIN) return fn::unexpected{fn::sum{overflow}};
    auto const g = (d < 0 ? -1 : 1) * std::gcd(n, d);
    n /= g;
    d /= g;
    if (n < INT_MIN || n > INT_MAX || d > INT_MAX) return fn::unexpected{fn::sum{overflow}};
    return Rational(int(n), int(d));
  }
};

// `parse` turns a string into a pair of numbers (a numerator and denominator)
auto parse(std::string_view s) -> fn::expected<fn::pack<int, int>, fn::sum<NotANumber>>
{
  int n = 0, d = 1;
  auto const bar = s.find('/');
  auto const head = s.substr(0, bar);
  auto const [p, e] = std::from_chars(head.data(), head.data() + head.size(), n);
  if (e != std::errc{} || p != head.data() + head.size())
    return fn::unexpected{fn::sum{notANumber}};
  if (bar != std::string_view::npos) {
    auto const tail = s.substr(bar + 1);
    auto const [q, f] = std::from_chars(tail.data(), tail.data() + tail.size(), d);
    if (f != std::errc{} || q != tail.data() + tail.size())
      return fn::unexpected{fn::sum{notANumber}};
  }
  return fn::pack<int, int>{n, d};
}

// Helper, does not need to name any error types — let the library compose them.
constexpr auto number = [](std::string_view s) { return parse(s) | fn::and_then(Rational::make); };

// `evaluate` parses both operands, applies the operator, and lets `make` re-check the
// result. Each stage fails its own way, and the library folds those failures into one
// error sum, never spelled by hand:
auto evaluate(std::string_view a, fn::sum_for<Add, Mul> op, std::string_view b)
{
  constexpr auto apply = fn::overload{
      [](Rational x, Add, Rational y) {
        return Rational::make(1LL * get<num>(x) * get<den>(y) + 1LL * get<num>(y) * get<den>(x),
                              1LL * get<den>(x) * get<den>(y));
      },
      [](Rational x, Mul, Rational y) {
        return Rational::make(1LL * get<num>(x) * get<num>(y), 1LL * get<den>(x) * get<den>(y));
      }};
  using Op = fn::expected<decltype(op), fn::sum<>>;
  return (number(a) & Op{op} & number(b)) | fn::and_then(apply);
}

// Result is a Rational, over the sum of every way a stage can fail:
static_assert(std::is_same_v<decltype(evaluate("1/2", add, "3/4")),
                             fn::expected<Rational, fn::sum<DivByZero, NotANumber, Overflow>>>);

What

The library features demonstrated by the code example above:

• Smart constructors — Rational's constructor is private; the only way to build one is the static make, which enforces invariants and returns fn::expected. An invalid Rational cannot exist, so callers don't need to check what the type already guarantees.
• Monadic pipelines — operator| pipes fn::expected (and fn::optional) through operations: and_then above; also or_else, transform, filter, inspect, recover, fail, transform_error and more.
• Composition — operator& accumulates both operands and the operator, as monadic values, into a fn::pack — which the next operation receives as separate arguments.
• Graded errors — each stage fails in its own way — a malformed string, a zero denominator, an out-of-range result — and the library widens these into a single fn::sum, here fn::sum<DivByZero, NotANumber, Overflow>: the whole pipeline's error, composed by the library and never written by hand.
• Multidispatch — fn::sum is indexed by type, not by position like std::variant, and fn::overload dispatches over its alternatives (Add and Mul) by ordinary overload resolution — exhaustively, so a missing handler is a compile error.

Beyond the example: fn::choice (a monad over fn::sum), dispatch across any combination of fn::pack and fn::sum, and more — see examples/ and the API reference.

How

The library comes as two parts in one repository:

• pfn (include/pfn, namespace pfn) — a faithful polyfill of standard-library vocabulary types: std::expected (as specified for C++26, including has_error()) and std::optional (as specified for C++26, including monadic functions, optional<T&> and range support), plus smaller utilities such as std::invoke_r and std::unreachable. It adds nothing of its own on top of what's mandated by the C++ standard.
• fn (include/fn, namespace fn) — the functional-programming library. It extends the vocabulary types with the facilities useful in writing functional style programs — monadic operations composable with operator|, such as and_then, transform, or_else, inspect, recover, filter — and adds new vocabulary types: sum, choice, pack.

Every fn type with a pfn counterpart is a strict superset of it: switching a valid program using pfn types to use fn instead changes neither compilation nor program behaviour.

fn builds on pfn, and all of libfn requires only a C++20-compatible compiler. The minimum supported compilers are gcc 12 and clang 16; Apple Clang 16.0 and Microsoft Visual Studio 2022 (or newer) are supported as well. See CONTRIBUTING.md for how to set up a recent enough toolchain when your OS does not ship one.

Implementation note

This library requires a total ordering of types, which the standard provides only from C++26 (std::type_order) and no compiler implements yet. The library relies on an internal, naive implementation of such a feature which is not expected to work with unnamed types, types without linkage etc. When std::type_order is implemented in available compilers, the library will offer a compilation mode to make use of this feature.

Using the library

The library is header-only. The CMake package exports two targets:

find_package(libfn CONFIG REQUIRED)
target_link_libraries(main PRIVATE libfn::fn)   # or libfn::pfn for the polyfills alone

Packaging is provided — and exercised by CI — for conan, vcpkg (an in-repo port), Nix and Bazel; plain CMake FetchContent or add_subdirectory works as well. Until the first tagged release, consume a pinned git revision — and read Backwards compatibility.

Every packaging route above except Bazel also delivers the compile options the headers require. Under Bazel — and a plain copy of include/ — these options don't arrive automatically; provide them yourself: C++20 or newer (--cxxopt=-std=c++20 in Bazel), -Wno-missing-braces on clang (fn::pack initialization elides braces by design), and with MSVC /permissive- plus _HAS_CXX23. The authoritative set is the INTERFACE options in cmake/CompilationOptions.cmake.

Backwards compatibility

The maintainers will aim to maintain compatibility with the proposed changes in the C++ standard library, rather than with the existing uses of the code in this repo. In practice, this means that all code in this repo should be considered "under intensive development and unstable" until the standardization of the proposed facilities.

Versioning and ABI

Releases are numbered 0.y.z and will stay below 1.0.0 for the foreseeable future. SemVer treats any 0.y.z version as unstable — anything may change — so libfn narrows that into a usable contract:

• a bump in y is a breaking change (API and/or ABI);
• a bump in z is a bug fix or a purely additive extension: the API and ABI stay compatible, but inline function definitions may change — see below.

Because the library is header-only, use a single libfn version per binary. Mixing versions in one program is an ODR violation — and that includes two z releases of the same y line, whose inline definitions may differ even though the ABI matches.

Contributing

See CONTRIBUTING.md for the development environment, building, testing, the version-bump mechanics, and the pre-commit workflow. The design history — decisions and the ideas they obsoleted — is recorded in CHANGELOG.md.

Acknowledgments

• Gašper Ažman, for providing the inspiration in "(Fun)ctional C++ and the M-word"
• Bartosz Milewski, for taking the time to explain parametrised and graded monads and effect systems
• Ripple, for allowing the main author the time to work on this library

License