Y Combinator
(utilities/y_combinator.hpp)

• View this file on GitHub
• Last update: 2026-06-16 01:13:59+09:00
• Include: #include "utilities/y_combinator.hpp"

Overview

Helper for writing recursive lambdas without declaring a separate function object.

Functions

Function	Description	Complexity
y_combinator(lambda)	Wraps a lambda so it can call itself through its first argument.	$O(1)$

Calling the wrapped lambda has the same asymptotic complexity as calling the original lambda body.

Example

#include "utilities/y_combinator.hpp"
#include <iostream>

int main() {
    auto fact = m1une::utilities::y_combinator([](auto self, int n) -> long long {
        if (n == 0) return 1;
        return n * self(n - 1);
    });

    long long x = fact(10);
    std::cout << x << "\n";
}

Verified with

• verify/utilities/extra_utilities.test.cpp

Code

#ifndef M1UNE_Y_COMBINATOR_HPP
#define M1UNE_Y_COMBINATOR_HPP 1

#include <type_traits>
#include <utility>

namespace m1une {
namespace utilities {

template <typename F>
struct YCombinator {
   private:
    F _f;

   public:
    explicit YCombinator(F&& f) : _f(std::forward<F>(f)) {}

    template <typename... Args>
    decltype(auto) operator()(Args&&... args) {
        return _f(*this, std::forward<Args>(args)...);
    }

    template <typename... Args>
    decltype(auto) operator()(Args&&... args) const {
        return _f(*this, std::forward<Args>(args)...);
    }
};

template <typename F>
auto y_combinator(F&& f) {
    return YCombinator<std::decay_t<F>>(std::forward<F>(f));
}

}  // namespace utilities
}  // namespace m1une

#endif  // M1UNE_Y_COMBINATOR_HPP

#line 1 "utilities/y_combinator.hpp"



#include <type_traits>
#include <utility>

namespace m1une {
namespace utilities {

template <typename F>
struct YCombinator {
   private:
    F _f;

   public:
    explicit YCombinator(F&& f) : _f(std::forward<F>(f)) {}

    template <typename... Args>
    decltype(auto) operator()(Args&&... args) {
        return _f(*this, std::forward<Args>(args)...);
    }

    template <typename... Args>
    decltype(auto) operator()(Args&&... args) const {
        return _f(*this, std::forward<Args>(args)...);
    }
};

template <typename F>
auto y_combinator(F&& f) {
    return YCombinator<std::decay_t<F>>(std::forward<F>(f));
}

}  // namespace utilities
}  // namespace m1une

Back to top page