206.md

Info

• Did you know about proposal to add support for recursive lambdas?

  • http://wg21.link/p0839

Example

// http://wg21.link/p0839
#if __has_feature(cpp_recursive_lambdas)
  auto fib = [](auto x) -> int {
    if (x <= 1) {
      return 1;
    } else {
      return fib(x-1) + fib(x-2);
    }
  };
#else
  auto fib = [](auto x, const auto& fib) -> int {
    if (x <= 1) {
      return 1;
    } else {
      return fib(x-1, fib) + fib(x-2, fib);
    }
  };
#endif

int main() {
  std::cout << fib(7, fib); // prints 21
}

https://godbolt.org/z/6zPxeM

Puzzle

• Can you implement a constexpr recursive lambda sum_years which sum up all years up to a given one?

  • It may require extending -fconstexpr-depth

constexpr auto sum_years = [](auto year) { /*TODO*/ return 0; }

static_assert(0 ==  sum_years(0));
static_assert(1 ==  sum_years(1));
static_assert(3 ==  sum_years(2));
static_assert(6 == sum_years(3));
static_assert(2'041'210 == sum_years(2020));

https://godbolt.org/z/eTYxM5

Solutions

constexpr auto sum_years = [](auto year) {
    constexpr auto sum_me = [](auto year, const auto& sum_me) {
        if (year == 0) { return 0; }
        return year + sum_me(year - 1, sum_me);
    };
    return sum_me(year, sum_me);
};

static_assert(0 ==  sum_years(0));
static_assert(1 ==  sum_years(1));
static_assert(3 ==  sum_years(2));
static_assert(6 == sum_years(3));
static_assert(2'041'210 == sum_years(2020));

https://godbolt.org/z/ao4fxa

namespace detail {
    constexpr auto sum = [] (const auto& f, auto n, auto acc) {
        if (n == 0) {
            return acc;
        } else {
            return f(f, n-1, acc + n);
        }
    };
}
constexpr auto sum_years = [](auto year) {
    return detail::sum(detail::sum, year, 0);
};

https://godbolt.org/z/5v43hq

namespace detail {
    constexpr auto accumulator = [](const auto x, const auto y){
        return x + y;
    };

    template<auto AccumulatorFn>
    constexpr auto sum = [](const auto& fn, const auto current,  const auto accumulated_value) {
        if (current == 0) {
            return accumulated_value;
        }
        else {
            return fn(fn, current - 1, AccumulatorFn(current, accumulated_value));
        }
    };
}

constexpr auto sum_years = [](const auto year) {
    return detail::sum<detail::accumulator>(detail::sum<detail::accumulator>, year, 0);
};

https://godbolt.org/z/xGEYo4

constexpr auto sum_years = [](auto year) {
  auto impl = [year](auto i, auto& impl) mutable -> std::size_t {
    if (i <= year) {
      return i + impl(i + 1, impl);
    } else {
      return {};
    }
  };
  return impl(0u, impl);
};

https://godbolt.org/z/WWfxqq

constexpr auto sum_years = [](auto year ){
    auto impl = [](auto year, auto const & impl )
    {
        if( year == 0 ) return 0;
        return year + impl(year -1, impl);
    };
    return impl(year,impl);
};

https://godbolt.org/z/c9sWcb

constexpr auto sum_years = [] (auto year) {
    constexpr auto sy_impl = [](auto year, const auto& sy_impl) -> decltype(year) {
        return year == 0 ? 0 : year + sy_impl(year-1, sy_impl);
    };
    return sy_impl(year, sy_impl);
};

https://godbolt.org/z/a68cWc

constexpr auto sum_years = []{
    constexpr auto impl = [](const auto& f, auto year) -> decltype(year) {
        return year ? year + f(f, year - 1) : 0;
    };

    return std::bind_front(impl, impl);
}();

https://godbolt.org/z/dMsMhq