#include <functional> constexpr auto multiply = std::multiplies{}; // Caveat: Multiplies instances of same type.
#include <utility>- #include <functional>
template<typename T, typename U>constexpr auto multiply(T a, U b) -> decltype(std::declval<T>() * std::declval<U>()){return a * b;}- constexpr auto multiply = std::multiplies{}; // Caveat: Multiplies instances of same type.
#pragma push_macro("It") #undef It #include <string> #include <vector> #include <range/v3/all.hpp> #pragma pop_macro("It") auto split(const std::string& str, char sep) { return str | ranges::views::split(sep) | ranges::to<std::vector<std::string>>; }
- #pragma push_macro("It")
- #undef It
- #include <string>
- #include <vector>
- #include <range/v3/all.hpp>
- #pragma pop_macro("It")
auto split(const std::string& str, char sep) {auto result = std::vector<std::string>{};std::string::size_type pos = 0, pos2 = 0;while ((pos2 = str.find(sep, pos)) != std::string::npos) {result.push_back(str.substr(pos, pos2 - pos));pos = pos2 + 1;}result.push_back(str.substr(pos));return result;}- auto split(const std::string& str, char sep)
- {
- return str | ranges::views::split(sep) | ranges::to<std::vector<std::string>>;
- }
#include <string> #include <string_view> #include <range/v3/view/join.hpp> #include <range/v3/range/conversion.hpp> std::string Jointup(const std::vector<std::string>& name, std::string_view delim = " , ") { return name | ranges::views::join(delim) | ranges::to<std::string>; }
- #include <string>
- #include <string_view>
#include <vector>#include <numeric>#include <sstream>- #include <range/v3/view/join.hpp>
- #include <range/v3/range/conversion.hpp>
std::string Jointup(const std::vector<std::string> &name , const std::string_view delim = " , ")- std::string Jointup(const std::vector<std::string>& name, std::string_view delim = " , ")
- {
if (name.empty()) return "";std::stringstream ss;ss << name.front();std::for_each(std::next(name.cbegin()), name.cend(), [&ss, delim](auto const& s) { ss << delim << s; });return ss.str();- return name | ranges::views::join(delim) | ranges::to<std::string>;
- }
Background
This task assumes familiarity with template metaprogramming and std::ratio
.
Overview
In this task, you’ll represent and manipulate polynomials through C++'s type system by means of template metaprogramming and the std::ratio
type. The key idea is to define a Polynomial
class template, where each term in the polynomial is represented by a coefficient using std::ratio
.
Polynomial Structure
Create a class Polynomial
that takes, as a parameter pack, a series of std::ratio
s representing the coefficients. Each ratio corresponds to the coefficient of a term, starting from the highest degree on the left and down to the constant term on the right.
For example, the polynomial
$ 10x^3 + 2.5x^2 + 5x + 0.5 $
Is represented by the type
Polynomial<std::ratio<10>, std::ratio<5, 2>, std::ratio<5>, std::ratio<1, 2>>
Each std::ratio represents a coefficient (e.g., std::ratio<5, 2>
represents 2.5
).
The rightmost ratio is the constant term (degree 0), and the terms to the left represent higher degree terms (e.g., the std::ratio<10>
stands for $ 10x^3 $
here).
One important rule: your Polynomial
s shouldn't have leading zero coefficients. After all, $ 0x^4 + 0x^3 + x^2 + x $
is simply $ x^2 + x $
. The only exception is the degree 0 polynomial (i.e., constant), where a lone zero is valid and is represented as Polynomial<std::ratio<0>>
.
Objective
You'll implement three main operations (as type aliases) for this compile-time polynomial class: differentiation, integration, and addition.
-
Polynomial<...>::differentiated
Type alias to the polynomial type representing the result of differentiating the current.
Example:
Polynomial<std::ratio<30>, std::ratio<20>, std::ratio<10>>::differentiated // Differentiating 30x^2 + 20x + 10. Alias for type Polynomial<std::ratio<60>, std::ratio<20>>. Polynomial<std::ratio<60>, std::ratio<20>>::differentiated // Differentiating 60x + 20. Alias for type Polynomial<std::ratio<60>>. Polynomial<std::ratio<60>>::differentiated // Differentiating 60. Alias for type Polynomial<std::ratio<0>> (i.e., constant term 0).
-
Polynomial<...>::integrated<std::ratio<...>>
Type alias to the polynomial type representing the result of integrating the current, including an integration constant (a
std::ratio
passed as a template argument).Example:
Polynomial<std::ratio<10>>::integrated<std::ratio<20>> // 20 is the integration constant. // Alias for type Polynomial<std::ratio<10>, std::ratio<20>>. Polynomial<std::ratio<10>, std::ratio<20>>::integrated<std::ratio<5, 2>> // 2.5 is the integration constant. // Alias for type Polynomial<std::ratio<5>, std::ratio<20>, std::ratio<5, 2>>.
You may assume that that the template argument provided to
integrated
by the tests will always be astd::ratio
. Hence, there is no need to validate the type. -
Polynomial<...>::add<Polynomial<...>>
Type alias template that accepts, as a template argument, another
Polynomial
, and represents the polynomial type resulting from adding the two together.The polynomials may possibly be of different degrees.
Example:
Polynomial<std::ratio<7>, std::ratio<5>>::add<Polynomial<std::ratio<3>, std::ratio<1>>> // (7x + 5) + (3x + 1). Alias for type Polynomial<std::ratio<10>, std::ratio<6>>. Polynomial<std::ratio<10>, std::ratio<20>>::add<Polynomial<std::ratio<30>>> // (10x + 20) + (30). Alias for type Polynomial<std::ratio<10>, std::ratio<50>>. Polynomial<std::ratio<25>, std::ratio<3>>::add<Polynomial<std::ratio<-25>, std::ratio<10>>> // (25x + 3) + (-25x + 10). Alias for type Polynomial<std::ratio<13>>. // (NOT Polynomial<std::ratio<0>, std::ratio<13>>)!
Remember, the coefficients can be negative, and it is your responsibility to ensure your resulting polynomial doesn't have leading zeroes after addition.
Assumptions
- Single-variable polynomials: All polynomials involve only one variable (x).
-
No omitted terms: All coefficients are explicitly represented, even if zero. A polynomial of degree
n
will have alln + 1
coefficients embedded in the type. However, there should be no unnecessary leading zeroes.
Note
The tests are forgiving in the sense that unimplemented parts of your solution will be registered as a failed test rather than a compilation error. Also, any two std::ratio
s representing the same quantity will be marked as correct. So, std::ratio<3>
and std::ratio<6, 2>
are equivalent when testing. If the tests time out, it's likely because your solution contains unintendeed infinite recursion.
#include <ratio> #include <utility> #include <cstddef> #include <tuple> #include <type_traits> template <typename... Coeffs> struct Polynomial; // Helpers to help "trim" Polynomials of leading zeroes. template<typename...> struct trim_impl; template<> struct trim_impl<> : std::common_type<Polynomial<>> {}; template<typename R1, typename... Rs> struct trim_impl<R1, Rs...> : std::conditional<sizeof...(Rs) and std::is_same_v<R1, std::ratio<0>>, typename trim_impl<Rs...>::type, Polynomial<R1, Rs...>> {}; template <typename... Coeffs> struct Polynomial { // Degree of Polynomial. static constexpr auto degree = sizeof...(Coeffs) - 1; // Alias for type of i-th std::ratio in the parameter pack. Pre-C++26 workaround for pack indexing. template <std::size_t I> using at = std::tuple_element_t<I, std::tuple<Coeffs...>>; // Alias for Polynomial type with leading zeroes removed. using trim = typename trim_impl<Coeffs...>::type; // Pads by adding leading zeroes until the parameter pack becomes of size I. template <std::size_t... Is> static constexpr auto pad_impl(std::index_sequence<Is...> seq) -> Polynomial<std::ratio<Is & 0>..., Coeffs...>; template <std::size_t I> static constexpr auto pad = decltype(pad_impl(std::make_index_sequence<std::max(I, degree) - degree>{})){}; // Private (but not really) helpers: template <typename... R1, typename... Rs> static constexpr auto add_impl(Polynomial<R1...>, Polynomial<Rs...>) -> Polynomial<std::ratio_add<R1, Rs>...>; template <typename... Rs, std::size_t... Is> static constexpr auto diff_impl(std::index_sequence<Is...>) -> Polynomial<std::ratio_multiply<at<Is>, std::ratio<degree - Is>>...>; template <typename C, std::size_t... Is> static constexpr auto integrate_impl(std::index_sequence<Is...>) -> Polynomial<std::ratio_divide<Coeffs, std::ratio<degree + 1 - Is>>..., C>; // Public aliases. template <typename Other> using add = typename decltype(add_impl(pad<Other::degree>, Other::template pad<degree>))::trim; using differentiated = decltype(diff_impl(std::make_index_sequence<degree + not degree>{})); template<typename C> using integrated = typename decltype(integrate_impl<C>(std::make_index_sequence<degree + 1>{}))::trim; };
- #include <ratio>
- #include <utility>
- #include <cstddef>
- #include <tuple>
- #include <type_traits>
// INTIAL SOLUTION TEMPLATE:- template <typename... Coeffs>
- struct Polynomial;
- // Helpers to help "trim" Polynomials of leading zeroes.
- template<typename...> struct trim_impl;
- template<> struct trim_impl<> : std::common_type<Polynomial<>> {};
- template<typename R1, typename... Rs> struct trim_impl<R1, Rs...> : std::conditional<sizeof...(Rs) and std::is_same_v<R1, std::ratio<0>>, typename trim_impl<Rs...>::type, Polynomial<R1, Rs...>> {};
- template <typename... Coeffs>
- struct Polynomial {
// using differentiated = ???;// template <???> using add = ???;// template <???> using integrated = ???;};- // Degree of Polynomial.
- static constexpr auto degree = sizeof...(Coeffs) - 1;
- // Alias for type of i-th std::ratio in the parameter pack. Pre-C++26 workaround for pack indexing.
- template <std::size_t I> using at = std::tuple_element_t<I, std::tuple<Coeffs...>>;
- // Alias for Polynomial type with leading zeroes removed.
- using trim = typename trim_impl<Coeffs...>::type;
- // Pads by adding leading zeroes until the parameter pack becomes of size I.
- template <std::size_t... Is> static constexpr auto pad_impl(std::index_sequence<Is...> seq) -> Polynomial<std::ratio<Is & 0>..., Coeffs...>;
- template <std::size_t I> static constexpr auto pad = decltype(pad_impl(std::make_index_sequence<std::max(I, degree) - degree>{})){};
- // Private (but not really) helpers:
- template <typename... R1, typename... Rs> static constexpr auto add_impl(Polynomial<R1...>, Polynomial<Rs...>)
- -> Polynomial<std::ratio_add<R1, Rs>...>;
- template <typename... Rs, std::size_t... Is> static constexpr auto diff_impl(std::index_sequence<Is...>)
- -> Polynomial<std::ratio_multiply<at<Is>, std::ratio<degree - Is>>...>;
- template <typename C, std::size_t... Is> static constexpr auto integrate_impl(std::index_sequence<Is...>)
- -> Polynomial<std::ratio_divide<Coeffs, std::ratio<degree + 1 - Is>>..., C>;
- // Public aliases.
- template <typename Other> using add = typename decltype(add_impl(pad<Other::degree>, Other::template pad<degree>))::trim;
- using differentiated = decltype(diff_impl(std::make_index_sequence<degree + not degree>{}));
- template<typename C> using integrated = typename decltype(integrate_impl<C>(std::make_index_sequence<degree + 1>{}))::trim;
- };
Background
This task assumes familiarity with template metaprogramming and std::ratio
.
Overview
In this task, you’ll represent and manipulate polynomials through C++'s type system by means of template metaprogramming and the std::ratio
type. The key idea is to define a Polynomial
class template, where each term in the polynomial is represented by a coefficient using std::ratio
.
Polynomial Structure
Create a class Polynomial
that takes, as a parameter pack, a series of std::ratio
s representing the coefficients. Each ratio corresponds to the coefficient of a term, starting from the highest degree on the left and down to the constant term on the right.
For example, the polynomial
$ 10x^3 + 2.5x^2 + 5x + 0.5 $
Is represented by the type
Polynomial<std::ratio<10>, std::ratio<5, 2>, std::ratio<5>, std::ratio<1, 2>>
Each std::ratio represents a coefficient (e.g., std::ratio<5, 2>
represents 2.5
).
The rightmost ratio is the constant term (degree 0), and the terms to the left represent higher degree terms (e.g., the std::ratio<10>
stands for $ 10x^3 $
here).
One important rule: your Polynomial
s shouldn't have leading zero coefficients. After all, $ 0x^4 + 0x^3 + x^2 + x $
is simply $ x^2 + x $
. The only exception is the degree 0 polynomial (i.e., constant), where a lone zero is valid and is represented as Polynomial<std::ratio<0>>
.
Objective
You'll implement three main operations (as type aliases) for this compile-time polynomial class: differentiation, integration, and addition.
-
Polynomial<...>::differentiated
Type alias to the polynomial type representing the result of differentiating the current.
Example:
Polynomial<std::ratio<30>, std::ratio<20>, std::ratio<10>>::differentiated // Differentiating 30x^2 + 20x + 10. Alias for type Polynomial<std::ratio<60>, std::ratio<20>>. Polynomial<std::ratio<60>, std::ratio<20>>::differentiated // Differentiating 60x + 20. Alias for type Polynomial<std::ratio<60>>. Polynomial<std::ratio<60>>::differentiated // Differentiating 60. Alias for type Polynomial<std::ratio<0>> (i.e., constant term 0).
-
Polynomial<...>::integrated<std::ratio<...>>
Type alias to the polynomial type representing the result of integrating the current, including an integration constant (a
std::ratio
passed as a template argument).Example:
Polynomial<std::ratio<10>>::integrated<std::ratio<20>> // 20 is the integration constant. // Alias for type Polynomial<std::ratio<10>, std::ratio<20>>. Polynomial<std::ratio<10>, std::ratio<20>>::integrated<std::ratio<5, 2>> // 2.5 is the integration constant. // Alias for type Polynomial<std::ratio<5>, std::ratio<20>, std::ratio<5, 2>>.
You may assume that that the template argument provided to
integrated
by the tests will always be astd::ratio
. Hence, there is no need to validate the type. -
Polynomial<...>::add<Polynomial<...>>
Type alias template that accepts, as a template argument, another
Polynomial
, and represents the polynomial type resulting from adding the two together.The polynomials may possibly be of different degrees.
Example:
Polynomial<std::ratio<7>, std::ratio<5>>::add<Polynomial<std::ratio<3>, std::ratio<1>>> // (7x + 5) + (3x + 1). Alias for type Polynomial<std::ratio<10>, std::ratio<6>>. Polynomial<std::ratio<10>, std::ratio<20>>::add<Polynomial<std::ratio<30>>> // (10x + 20) + (30). Alias for type Polynomial<std::ratio<10>, std::ratio<50>>. Polynomial<std::ratio<25>, std::ratio<3>>::add<Polynomial<std::ratio<-25>, std::ratio<10>>> // (25x + 3) + (-25x + 10). Alias for type Polynomial<std::ratio<13>>. // (NOT Polynomial<std::ratio<0>, std::ratio<13>>)!
Remember, the coefficients can be negative, and it is your responsibility to ensure your resulting polynomial doesn't have leading zeroes after addition.
Assumptions
- Single-variable polynomials: All polynomials involve only one variable (x).
-
No omitted terms: All coefficients are explicitly represented, even if zero. A polynomial of degree
n
will have alln + 1
coefficients embedded in the type. However, there should be no unnecessary leading zeroes.
Note
The tests are forgiving in the sense that unimplemented parts of your solution will be registered as a failed test rather than a compilation error. Also, any two std::ratio
s representing the same quantity will be marked as correct. So, std::ratio<3>
and std::ratio<6, 2>
are equivalent when testing. If the tests time out, it's likely because your solution contains unintendeed infinite recursion.
#include <ratio>
// INTIAL SOLUTION TEMPLATE:
template <typename... Coeffs>
struct Polynomial {
// using differentiated = ???;
// template <???> using add = ???;
// template <???> using integrated = ???;
};
#include <ratio>
#include <string_view>
#include <random>
#include <tuple>
Describe(fixed_tests)
{
It(addition_tests)
{
do_add_test<Polynomial<std::ratio<7>, std::ratio<5>>,
Polynomial<std::ratio<3>, std::ratio<1>>,
Polynomial<std::ratio<10>, std::ratio<6>>>();
do_add_test<Polynomial<std::ratio<7>, std::ratio<5>>,
Polynomial<std::ratio<3>, std::ratio<1>>,
Polynomial<std::ratio<10>, std::ratio<6>>>();
do_add_test<Polynomial<std::ratio<10>, std::ratio<20>>,
Polynomial<std::ratio<30>>,
Polynomial<std::ratio<10>, std::ratio<50>>>();
do_add_test<Polynomial<std::ratio<25>, std::ratio<3>>,
Polynomial<std::ratio<-25>, std::ratio<10>>,
Polynomial<std::ratio<13>>>();
do_add_test<Polynomial<std::ratio<7>>,
Polynomial<std::ratio<-7>>,
Polynomial<std::ratio<0>>>();
do_add_test<Polynomial<std::ratio<7>, std::ratio<6>, std::ratio<5>>,
Polynomial<std::ratio<0>>,
Polynomial<std::ratio<7>, std::ratio<6>, std::ratio<5>>>();
do_add_test<Polynomial<std::ratio<7>, std::ratio<6>, std::ratio<5>>,
Polynomial<std::ratio<-7>, std::ratio<-6>, std::ratio<-5>>,
Polynomial<std::ratio<0>>>();
}
It(differentiation_tests)
{
do_diff_test<Polynomial<std::ratio<30>, std::ratio<20>, std::ratio<10>>,
Polynomial<std::ratio<60>, std::ratio<20>>>();
do_diff_test<Polynomial<std::ratio<60>, std::ratio<20>>,
Polynomial<std::ratio<60>>>();
do_diff_test<Polynomial<std::ratio<60>>,
Polynomial<std::ratio<0>>>();
do_diff_test<Polynomial<std::ratio<5, 3>, std::ratio<98, 5>, std::ratio<3>, std::ratio<98>>,
Polynomial<std::ratio<5>, std::ratio<196, 5>, std::ratio<3>>>();
do_diff_test<Polynomial<std::ratio<0>>,
Polynomial<std::ratio<0>>>();
}
It(integration_tests)
{
do_integ_test<Polynomial<std::ratio<0>>,
std::ratio<-1, 5>,
Polynomial<std::ratio<-1, 5>>>();
do_integ_test<Polynomial<std::ratio<10>>,
std::ratio<20>,
Polynomial<std::ratio<10>, std::ratio<20>>>();
do_integ_test<Polynomial<std::ratio<10>, std::ratio<20>>,
std::ratio<5, 2>,
Polynomial<std::ratio<5>, std::ratio<20>, std::ratio<5, 2>>>();
do_integ_test<Polynomial<std::ratio<-5>, std::ratio<2>, std::ratio<10>>,
std::ratio<0>,
Polynomial<std::ratio<-5, 3>, std::ratio<1>, std::ratio<10>, std::ratio<0>>>();
}
};
Constructor situation is a bit better now. Thunks are now copyable and are more flexibly constructible.
Background
C++ recreation of the Thunk API from this Kata.
Test cases are included to verify if it works as expected. The full extent of the class is used in those test cases.
#include <tuple> #include <string> #include <vector> #include <utility> Describe(fixed_test_cases) { It(basic_thunk_tests) { // Currently stores 3. Thunk num1 = MakeThunk::now(3); // Represents the future result of multiplying num1's value by 2 (i.e., 3 * 2 ==> 6). Thunk num2 = num1.chain([](auto n) { return n * 2; }); // Delayed computation of the number formed by concatenating num1 and num2 as strings. // Note: Since the function captures by reference, it's impure. However, this can allow us to check if computation is actually delayed. const Thunk num3 = MakeThunk::delay([&] { return std::stoi(std::to_string(num1.get()) + std::to_string(num2.get())); }); Assert::That(num2.get(), Equals(6)); Assert::That(num1.get(), Equals(3)); // Change num2 to 0. num2 = MakeThunk::delay([] { return 0; }); // Since Thunks delay computation, it actually computes 30 (up to date) and not 36 (outdated). Assert::That(num3.get(), Equals(30)); // Change num1 to 4. num1 = MakeThunk::now(4); // Thunk only evaluated once - unaffected by change. Remains 30 instead of 40. Assert::That(num3.get(), Equals(30)); // Works with regular old functions (non-functors) too. const Thunk num4 = MakeThunk::delay(return_24); Assert::That(num4.get(), Equals(24)); } It(can_chain_different_types) { // First chain returns int, second returns std::pair<int, int>, third returns string. const Thunk birthday_msg = MakeThunk::now(24) .chain([](auto n) { return std::pair{ n, n + 1 }; }) .chain([](auto ages) { return "Do you know what is funnier than " + std::to_string(ages.first) + "? " + std::to_string(ages.second) + "!"; }); Assert::That(birthday_msg.get(), Equals("Do you know what is funnier than 24? 25!")); } It(allows_cyclic_ref) { using LazyPair = std::pair<int, Thunk<int>>; // Second item of pair is 5 times the first (i.e., 10 * 5 == 50). LazyPair lazy_pair{ 10, MakeThunk::delay([&] { return lazy_pair.first * 5; })}; Assert::That(lazy_pair.second.get(), Equals(50)); } It(successfully_extends_lifetime) { Thunk<int> remaining_thunk{}; // Scope to restrict the lifetime of `expiring_thunk`. `remaining_thunk` depends on its data. { Thunk expiring_thunk = MakeThunk::now(3); remaining_thunk = expiring_thunk.chain([](auto n) { return n * 2; }); } // Thunk class should successfully extend the lifetime of the data of other Thunks it depends on. Assert::That(remaining_thunk.get(), Equals(6)); } It(thunk_is_copyable) { Thunk<const char*> c_str_thunk = MakeThunk::now("Yooooo"); Thunk<std::string> str_thunk_1 = c_str_thunk; Assert::That(str_thunk_1.get(), Equals("Yooooo")); Assert::That(std::is_same_v<std::string, std::decay_t<decltype(str_thunk_1.get())>>); Assert::That(str_thunk_1.get().c_str() != c_str_thunk.get()); Thunk<std::string> str_thunk_2 = MakeThunk::now("yo"); Assert::That(str_thunk_2.get(), Equals("yo")); Assert::That(std::is_same_v<std::string, std::decay_t<decltype(str_thunk_2.get())>>); Thunk<std::string> str_thunk_cpy = str_thunk_1; // If the types are the same, reuse the same stored data. Assert::That(&str_thunk_cpy.get() == &str_thunk_1.get()); Assert::That(str_thunk_1.get().c_str() == str_thunk_cpy.get().c_str()); } It(all_thunk_constructors_work_correctly) { const Thunk<int> num5{ return_24 }; // return_24 is a regular non-functor function. Assert::That(num5.get(), Equals(24)); const auto default_thunk_1 = MakeThunk::now_in_place<std::pair<int, int>>(); const Thunk<std::pair<int, int>> default_thunk_2{}; const Thunk default_thunk_3 = MakeThunk::now(std::pair<int, int>{}); const Thunk<std::pair<int, int>> default_thunk_4{ std::in_place }; Assert::That(default_thunk_1.get() == default_thunk_2.get() and default_thunk_2.get() == default_thunk_3.get() and default_thunk_3.get() == default_thunk_4.get()); const auto str_thunk = MakeThunk::now_in_place<std::string>("hey"); Assert::That(str_thunk.get(), Equals("hey")); const auto three_b_thunk = MakeThunk::now_in_place<std::string>(3, 'B'); Assert::That(three_b_thunk.get(), Equals("BBB")); const auto vec_thunk = MakeThunk::now_in_place<std::vector<int>>(std::initializer_list<int>{ 1, 2, 3 }); Assert::That(vec_thunk.get(), Equals(std::vector{ 1, 2, 3 })); const Thunk<std::string> four_a_thunk{ std::in_place, 4, 'A' }; Assert::That(four_a_thunk.get(), Equals("AAAA")); const Thunk<std::pair<int, char>> pair_thunk{ std::in_place, 2, 'z' }; Assert::That(pair_thunk.get(), Equals(std::pair{ 2, 'z' })); const auto tuple_thunk = MakeThunk::now_in_place<std::tuple<int, char, int, int>>(-2, 'f', 2000, 9); Assert::That(tuple_thunk.get(), Equals(std::tuple{ -2, 'f', 2000, 9 })); } private: // Regular old function. static int return_24() { return 24; } };
- #include <tuple>
- #include <string>
- #include <vector>
- #include <utility>
- Describe(fixed_test_cases)
- {
- It(basic_thunk_tests)
- {
- // Currently stores 3.
- Thunk num1 = MakeThunk::now(3);
- // Represents the future result of multiplying num1's value by 2 (i.e., 3 * 2 ==> 6).
- Thunk num2 = num1.chain([](auto n) { return n * 2; });
- // Delayed computation of the number formed by concatenating num1 and num2 as strings.
- // Note: Since the function captures by reference, it's impure. However, this can allow us to check if computation is actually delayed.
- const Thunk num3 = MakeThunk::delay([&] { return std::stoi(std::to_string(num1.get()) + std::to_string(num2.get())); });
- Assert::That(num2.get(), Equals(6));
- Assert::That(num1.get(), Equals(3));
- // Change num2 to 0.
- num2 = MakeThunk::delay([] { return 0; });
- // Since Thunks delay computation, it actually computes 30 (up to date) and not 36 (outdated).
- Assert::That(num3.get(), Equals(30));
- // Change num1 to 4.
- num1 = MakeThunk::now(4);
// Thunk only computed once - unaffected by change. Remains 30 instead of 40.- // Thunk only evaluated once - unaffected by change. Remains 30 instead of 40.
- Assert::That(num3.get(), Equals(30));
- // Works with regular old functions (non-functors) too.
- const Thunk num4 = MakeThunk::delay(return_24);
- Assert::That(num4.get(), Equals(24));
- }
- It(can_chain_different_types)
- {
- // First chain returns int, second returns std::pair<int, int>, third returns string.
- const Thunk birthday_msg = MakeThunk::now(24)
- .chain([](auto n) { return std::pair{ n, n + 1 }; })
- .chain([](auto ages) { return "Do you know what is funnier than " + std::to_string(ages.first) + "? " + std::to_string(ages.second) + "!"; });
- Assert::That(birthday_msg.get(), Equals("Do you know what is funnier than 24? 25!"));
- }
- It(allows_cyclic_ref)
- {
- using LazyPair = std::pair<int, Thunk<int>>;
- // Second item of pair is 5 times the first (i.e., 10 * 5 == 50).
- LazyPair lazy_pair{ 10, MakeThunk::delay([&] { return lazy_pair.first * 5; })};
- Assert::That(lazy_pair.second.get(), Equals(50));
- }
- It(successfully_extends_lifetime)
- {
- Thunk<int> remaining_thunk{};
- // Scope to restrict the lifetime of `expiring_thunk`. `remaining_thunk` depends on its data.
- {
- Thunk expiring_thunk = MakeThunk::now(3);
- remaining_thunk = expiring_thunk.chain([](auto n) { return n * 2; });
- }
- // Thunk class should successfully extend the lifetime of the data of other Thunks it depends on.
- Assert::That(remaining_thunk.get(), Equals(6));
- }
- It(thunk_is_copyable)
- {
- Thunk<const char*> c_str_thunk = MakeThunk::now("Yooooo");
- Thunk<std::string> str_thunk_1 = c_str_thunk;
- Assert::That(str_thunk_1.get(), Equals("Yooooo"));
- Assert::That(std::is_same_v<std::string, std::decay_t<decltype(str_thunk_1.get())>>);
- Assert::That(str_thunk_1.get().c_str() != c_str_thunk.get());
- Thunk<std::string> str_thunk_2 = MakeThunk::now("yo");
- Assert::That(str_thunk_2.get(), Equals("yo"));
- Assert::That(std::is_same_v<std::string, std::decay_t<decltype(str_thunk_2.get())>>);
- Thunk<std::string> str_thunk_cpy = str_thunk_1;
- // If the types are the same, reuse the same stored data.
- Assert::That(&str_thunk_cpy.get() == &str_thunk_1.get());
- Assert::That(str_thunk_1.get().c_str() == str_thunk_cpy.get().c_str());
- }
- It(all_thunk_constructors_work_correctly)
- {
- const Thunk<int> num5{ return_24 }; // return_24 is a regular non-functor function.
- Assert::That(num5.get(), Equals(24));
- const auto default_thunk_1 = MakeThunk::now_in_place<std::pair<int, int>>();
- const Thunk<std::pair<int, int>> default_thunk_2{};
- const Thunk default_thunk_3 = MakeThunk::now(std::pair<int, int>{});
- const Thunk<std::pair<int, int>> default_thunk_4{ std::in_place };
- Assert::That(default_thunk_1.get() == default_thunk_2.get() and default_thunk_2.get() == default_thunk_3.get() and default_thunk_3.get() == default_thunk_4.get());
- const auto str_thunk = MakeThunk::now_in_place<std::string>("hey");
- Assert::That(str_thunk.get(), Equals("hey"));
- const auto three_b_thunk = MakeThunk::now_in_place<std::string>(3, 'B');
- Assert::That(three_b_thunk.get(), Equals("BBB"));
- const auto vec_thunk = MakeThunk::now_in_place<std::vector<int>>(std::initializer_list<int>{ 1, 2, 3 });
- Assert::That(vec_thunk.get(), Equals(std::vector{ 1, 2, 3 }));
- const Thunk<std::string> four_a_thunk{ std::in_place, 4, 'A' };
- Assert::That(four_a_thunk.get(), Equals("AAAA"));
- const Thunk<std::pair<int, char>> pair_thunk{ std::in_place, 2, 'z' };
- Assert::That(pair_thunk.get(), Equals(std::pair{ 2, 'z' }));
- const auto tuple_thunk = MakeThunk::now_in_place<std::tuple<int, char, int, int>>(-2, 'f', 2000, 9);
- Assert::That(tuple_thunk.get(), Equals(std::tuple{ -2, 'f', 2000, 9 }));
- }
- private:
- // Regular old function.
- static int return_24() { return 24; }
- };
Refactors + bug fixes + using std::variant
now.
C++ recreation of the Thunk API from this Kata.
Test cases are included to verify if it works as expected.
The usage of the class happens in the test cases.
TODO:
Next I want to allow copying. The constructor situation is making this so difficult :/
//
#include <memory>#include <optional>#include <functional>#include <type_traits>// Forward declaration.template <typename T>struct Thunk;// Factory for Thunks. C++ disallows non-templated static methods for class templates,// so this is its own namespace.namespace MakeThunk {template <typename T>auto now(T&& t) -> Thunk<std::decay_t<T>>{return { std::forward<T>(t), {} };}template <typename Func>auto delay(Func&& func) -> Thunk<std::decay_t<std::invoke_result_t<Func>>>{return { {}, std::forward<Func>(func) };}}template <typename T>struct Thunk {public:Thunk(std::optional<T> value = {}, std::function<T()> supplier = {}) : data{ std::make_shared<ThunkData>(ThunkData{ value, supplier }) } {}T get() const{return data->get_data();}template <typename Func>auto chain(const Func& func) const -> Thunk<std::decay_t<std::invoke_result_t<Func, T>>>{// Data is a shared pointer that is copied in the closure ==> extends the lifetime of the data// as needed.return MakeThunk::delay([=, shared_data=data]() { return func(shared_data->get_data()); });}private:// Actual private API of Thunk.struct ThunkData{T get_data(){if (not value) value = std::exchange(supplier, {})();return *value;}std::optional<T> value{};std::function<T()> supplier{};};// Data is in a shared pointer ==> prevents lifetime issues.std::shared_ptr<ThunkData> data{};};- //
#include <string> #include <utility> Describe(fixed_test_cases) { It(basic_thunk_tests) { // Currently stores 3. Thunk num1 = MakeThunk::now(3); // Represents the future result of multiplying num1's value by 2 (i.e., 3 * 2 ==> 6). Thunk num2 = num1.chain([](auto n) { return n * 2; }); // Delayed computation of the number formed by concatenating num1 and num2 as strings. const Thunk num3 = MakeThunk::delay([&] { return std::stoi(std::to_string(num1.get()) + std::to_string(num2.get())); }); Assert::That(num2.get(), Equals(6)); Assert::That(num1.get(), Equals(3)); // Change num2 to 0. num2 = MakeThunk::delay([] { return 0; }); // Since Thunks delay computation, it actually computes 30 (up to date) and not 36 (outdated). Assert::That(num3.get(), Equals(30)); // Change num1 to 4. num1 = MakeThunk::now(4); // Thunk only computed once - unaffected by change. Remains 30 instead of 40. Assert::That(num3.get(), Equals(30)); } It(can_chain_different_types) { // First chain returns int, second returns std::pair<int, int>, third returns string. const Thunk birthday_msg = MakeThunk::now(24) .chain([](auto n) { return std::pair{ n, n + 1 }; }) .chain([](auto ages) { return "Do you know what is funnier than " + std::to_string(ages.first) + "? " + std::to_string(ages.second) + "!"; }); Assert::That(birthday_msg.get(), Equals("Do you know what is funnier than 24? 25!")); } It(allows_cyclic_ref) { using LazyPair = std::pair<int, Thunk<int>>; // Second item of pair is 5 times the first (i.e., 10 * 5 == 50). LazyPair lazy_pair{ 10, MakeThunk::delay([&] { return lazy_pair.first * 5; })}; Assert::That(lazy_pair.second.get(), Equals(50)); } It(successfully_extends_lifetime) { Thunk<int> remaining_thunk{}; // Scope to restrict the lifetime of `expiring_thunk`. `remaining_thunk` depends on its data. { Thunk expiring_thunk = MakeThunk::now(3); remaining_thunk = expiring_thunk.chain([](auto n) { return n * 2; }); } // Thunk class should successfully extend the lifetime of the data of other Thunks it depends on. Assert::That(remaining_thunk.get(), Equals(6)); } };
- #include <string>
- #include <utility>
- Describe(fixed_test_cases)
- {
- It(basic_thunk_tests)
- {
- // Currently stores 3.
- Thunk num1 = MakeThunk::now(3);
// Currently stores 3 * 2 ==> 6.- // Represents the future result of multiplying num1's value by 2 (i.e., 3 * 2 ==> 6).
- Thunk num2 = num1.chain([](auto n) { return n * 2; });
- // Delayed computation of the number formed by concatenating num1 and num2 as strings.
const Thunk num3 = MakeThunk::delay([&]() { return std::stoi(std::to_string(num1.get()) + std::to_string(num2.get())); });- const Thunk num3 = MakeThunk::delay([&] { return std::stoi(std::to_string(num1.get()) + std::to_string(num2.get())); });
- Assert::That(num2.get(), Equals(6));
- Assert::That(num1.get(), Equals(3));
- // Change num2 to 0.
num2 = MakeThunk::delay([]() { return 0; });- num2 = MakeThunk::delay([] { return 0; });
- // Since Thunks delay computation, it actually computes 30 (up to date) and not 36 (outdated).
- Assert::That(num3.get(), Equals(30));
- // Change num1 to 4.
- num1 = MakeThunk::now(4);
- // Thunk only computed once - unaffected by change. Remains 30 instead of 40.
- Assert::That(num3.get(), Equals(30));
- }
- It(can_chain_different_types)
- {
- // First chain returns int, second returns std::pair<int, int>, third returns string.
- const Thunk birthday_msg = MakeThunk::now(24)
- .chain([](auto n) { return std::pair{ n, n + 1 }; })
- .chain([](auto ages) { return "Do you know what is funnier than " + std::to_string(ages.first) + "? " + std::to_string(ages.second) + "!"; });
Assert::That(birthday_msg.get(),Equals("Do you know what is funnier than 24? 25!"));- Assert::That(birthday_msg.get(), Equals("Do you know what is funnier than 24? 25!"));
- }
- It(allows_cyclic_ref)
- {
- using LazyPair = std::pair<int, Thunk<int>>;
- // Second item of pair is 5 times the first (i.e., 10 * 5 == 50).
LazyPair lazy_pair{ 10, MakeThunk::delay([&]() { return lazy_pair.first * 5; })};- LazyPair lazy_pair{ 10, MakeThunk::delay([&] { return lazy_pair.first * 5; })};
- Assert::That(lazy_pair.second.get(), Equals(50));
- }
- It(successfully_extends_lifetime)
- {
- Thunk<int> remaining_thunk{};
- // Scope to restrict the lifetime of `expiring_thunk`. `remaining_thunk` depends on its data.
- {
- Thunk expiring_thunk = MakeThunk::now(3);
- remaining_thunk = expiring_thunk.chain([](auto n) { return n * 2; });
- }
- // Thunk class should successfully extend the lifetime of the data of other Thunks it depends on.
- Assert::That(remaining_thunk.get(), Equals(6));
- }
- };
C++ recreation of the Thunk API from this Kata.
Test cases are included to verify if it works as expected.
#include <memory>
#include <optional>
#include <functional>
#include <type_traits>
// Forward declaration.
template <typename T>
struct Thunk;
// Factory for Thunks. C++ disallows non-templated static methods for class templates,
// so this is its own namespace.
namespace MakeThunk {
template <typename T>
auto now(T&& t) -> Thunk<std::decay_t<T>>
{
return { std::forward<T>(t), {} };
}
template <typename Func>
auto delay(Func&& func) -> Thunk<std::decay_t<std::invoke_result_t<Func>>>
{
return { {}, std::forward<Func>(func) };
}
}
template <typename T>
struct Thunk {
public:
Thunk(std::optional<T> value = {}, std::function<T()> supplier = {}) : data{ std::make_shared<ThunkData>(ThunkData{ value, supplier }) } {}
T get() const
{
return data->get_data();
}
template <typename Func>
auto chain(const Func& func) const -> Thunk<std::decay_t<std::invoke_result_t<Func, T>>>
{
// Data is a shared pointer that is copied in the closure ==> extends the lifetime of the data
// as needed.
return MakeThunk::delay([=, shared_data=data]() { return func(shared_data->get_data()); });
}
private:
// Actual private API of Thunk.
struct ThunkData
{
T get_data()
{
if (not value) value = std::exchange(supplier, {})();
return *value;
}
std::optional<T> value{};
std::function<T()> supplier{};
};
// Data is in a shared pointer ==> prevents lifetime issues.
std::shared_ptr<ThunkData> data{};
};
#include <string>
#include <utility>
Describe(fixed_test_cases)
{
It(basic_thunk_tests)
{
// Currently stores 3.
Thunk num1 = MakeThunk::now(3);
// Currently stores 3 * 2 ==> 6.
Thunk num2 = num1.chain([](auto n) { return n * 2; });
// Delayed computation of the number formed by concatenating num1 and num2 as strings.
const Thunk num3 = MakeThunk::delay([&]() { return std::stoi(std::to_string(num1.get()) + std::to_string(num2.get())); });
Assert::That(num2.get(), Equals(6));
Assert::That(num1.get(), Equals(3));
// Change num2 to 0.
num2 = MakeThunk::delay([]() { return 0; });
// Since Thunks delay computation, it actually computes 30 (up to date) and not 36 (outdated).
Assert::That(num3.get(), Equals(30));
// Change num1 to 4.
num1 = MakeThunk::now(4);
// Thunk only computed once - unaffected by change. Remains 30 instead of 40.
Assert::That(num3.get(), Equals(30));
}
It(can_chain_different_types)
{
// First chain returns int, second returns std::pair<int, int>, third returns string.
const Thunk birthday_msg = MakeThunk::now(24)
.chain([](auto n) { return std::pair{ n, n + 1 }; })
.chain([](auto ages) { return "Do you know what is funnier than " + std::to_string(ages.first) + "? " + std::to_string(ages.second) + "!"; });
Assert::That(birthday_msg.get(),
Equals("Do you know what is funnier than 24? 25!"));
}
It(allows_cyclic_ref)
{
using LazyPair = std::pair<int, Thunk<int>>;
// Second item of pair is 5 times the first (i.e., 10 * 5 == 50).
LazyPair lazy_pair{ 10, MakeThunk::delay([&]() { return lazy_pair.first * 5; })};
Assert::That(lazy_pair.second.get(), Equals(50));
}
It(successfully_extends_lifetime)
{
Thunk<int> remaining_thunk{};
// Scope to restrict the lifetime of `expiring_thunk`. `remaining_thunk` depends on its data.
{
Thunk expiring_thunk = MakeThunk::now(3);
remaining_thunk = expiring_thunk.chain([](auto n) { return n * 2; });
}
// Thunk class should successfully extend the lifetime of the data of other Thunks it depends on.
Assert::That(remaining_thunk.get(), Equals(6));
}
};
The logs in the test output should hopefully make a case that recommending this syntax in the guidelines can be very problematic: std::bind(distrib, engine)
.
Depending on the testing code, this can actually turn into just glorified fixed-case testing.
// Look through the test output logs and expand to reveal commentary. No need to check the test code.
// Look through the test output logs and expand to reveal commentary. No need to check the test code.
#include <random>
#include <functional>
#include <fmt/ranges.h>
Describe(pitfalls_of_using_bind_without_ref)
{
It(context)
{
std::cout << R"(std::bind(distrib, engine) makes a copy of the engine at the time of its invocation.
Therefore, if you create different random-generation functions that
use std::bind, each time you call them, it’s as if you’re
generating the first number from the same initial
engine state. This can result in a very non-random output at times.)";
}
It(using_multiple_functions)
{
std::mt19937 engine{ std::random_device{}() };
std::function<int()> gen_a = std::bind(std::uniform_int_distribution{-1000, 1000}, engine);
std::function<int()> gen_b = std::bind(std::uniform_int_distribution{-1000, 1000}, engine);
std::cout << "std::function<int()> gen_a\n = std::bind(std::uniform_int_distribution{-1000, 1000}, engine);\n";
std::cout << "std::function<int()> gen_b\n = std::bind(std::uniform_int_distribution{-1000, 1000}, engine);\n\n";
std::cout << "gen_a and gen_b seem like they would return different results (or so we think!).\nLet's call them in a loop\n\n";
for (int i = 0; i < 10; ++i) {
std::cout << "Next Iteration:\n"
<< "gen_a(): " << gen_a() << '\n'
<< "gen_b(): " << gen_b() << "\n\n";
}
}
It(using_with_stl_algorithms)
{
std::mt19937 engine{ std::random_device{}() };
std::function<int()> gen_int = std::bind(std::uniform_int_distribution{-1000, 1000}, engine);
std::cout << "std::function<int()> gen_int\n = std::bind(std::uniform_int_distribution{-1000, 1000}, engine);\n\n"
<< "Let's make a loop where we create and fill up a\nvector with random ints each time.\n\n"
<< "std::vector<int> vec(10);\n"
<< "std::generate(vec.begin(), vec.end(), gen_int);\n\n";
for (int i = 0; i < 3; ++i) {
std::vector<int> vec(10);
std::generate(vec.begin(), vec.end(), gen_int);
std::cout << fmt::format("Iteration #{} using std::generate:\n{}\n\n", i, vec);
}
std::cout << "Same sequence every time :/.\n\nAfter all that, manually calling gen_int() a bunch of times\nalso returns the same sequence:\n";
for (int _ = 0; _ < 10; ++_) std::cout << gen_int() << " ";
}
};
Describe(solution1__bind_with_std_ref)
{
It(context)
{
std::cout << R"(An easy solution is still using std::bind
but providing a reference-wrapper to the engine
via std::ref (from the <functional> header).
std::bind(std::uniform_int_distribution{-1000, 1000}, engine);
becomes...
std::bind(std::uniform_int_distribution{-1000, 1000}, std::ref(engine));
)";
}
It(using_multiple_functions)
{
std::mt19937 engine{ std::random_device{}() };
std::function<int()> gen_a = std::bind(std::uniform_int_distribution{-1000, 1000}, std::ref(engine));
std::function<int()> gen_b = std::bind(std::uniform_int_distribution{-1000, 1000}, std::ref(engine));
std::cout << "std::function<int()> gen_a\n = std::bind(std::uniform_int_distribution{-1000, 1000}, std::ref(engine));\n";
std::cout << "std::function<int()> gen_b\n = std::bind(std::uniform_int_distribution{-1000, 1000}, std::ref(engine));\n\n";
std::cout << "gen_a and gen_b are no more identical.\nLet's call them in a loop\n\n";
for (int i = 0; i < 10; ++i) {
std::cout << "Next Iteration:\n"
<< "gen_a(): " << gen_a() << '\n'
<< "gen_b(): " << gen_b() << "\n\n";
}
}
It(using_with_stl_algorithms)
{
std::mt19937 engine{ std::random_device{}() };
std::function<int()> gen_int = std::bind(std::uniform_int_distribution{-1000, 1000}, std::ref(engine));
std::cout << "std::function<int()> gen_int\n = std::bind(std::uniform_int_distribution{-1000, 1000}, std::ref(engine));\n\n"
<< "Let's make a loop where we create and fill up a\nvector with random ints each time.\n\n"
<< "std::vector<int> vec(10);\n"
<< "std::generate(vec.begin(), vec.end(), gen_int);\n\n";
for (int i = 0; i < 3; ++i) {
std::vector<int> vec(10);
std::generate(vec.begin(), vec.end(), gen_int);
std::cout << fmt::format("Iteration #{} using std::generate:\n{}\n\n", i, vec);
}
std::cout << "After all that, manually calling gen_int() a bunch of times:\n";
for (int _ = 0; _ < 10; ++_) std::cout << gen_int() << " ";
std::cout << "\n\nAs evident, we don't have the same identical-number issue.";
}
};
Describe(solution2__using_lambdas_with_reference_capture)
{
It(context)
{
std::cout << R"(Using a lambda that captures the engine
by reference can also negate these issues.)
std::bind(std::uniform_int_distribution{-1000, 1000}, engine);
becomes...
[&, dis=std::uniform_int_distribution{-1000, 1000}]() mutable { return dis(engine); };
It's ugly but elides the issue.)";
}
It(using_multiple_functions)
{
std::mt19937 engine{ std::random_device{}() };
std::function<int()> gen_a = [&, dis=std::uniform_int_distribution{-1000, 1000}]() mutable { return dis(engine); };
std::function<int()> gen_b = [&, dis=std::uniform_int_distribution{-1000, 1000}]() mutable { return dis(engine); };
std::cout << "std::function<int()> gen_a\n = [&, dis=std::uniform_int_distribution{-1000, 1000}]() mutable { return dis(engine); };\n";
std::cout << "std::function<int()> gen_b\n = [&, dis=std::uniform_int_distribution{-1000, 1000}]() mutable { return dis(engine); };\n\n";
std::cout << "gen_a and gen_b are no more identical.\nLet's call them in a loop\n\n";
for (int i = 0; i < 10; ++i) {
std::cout << "Next Iteration:\n"
<< "gen_a(): " << gen_a() << '\n'
<< "gen_b(): " << gen_b() << "\n\n";
}
}
It(using_with_stl_algorithms)
{
std::mt19937 engine{ std::random_device{}() };
std::function<int()> gen_int = [&, dis=std::uniform_int_distribution{-1000, 1000}]() mutable { return dis(engine); };
std::cout << "std::function<int()> gen_int\n = [&, dis=std::uniform_int_distribution{-1000, 1000}]() mutable { return dis(engine); };\n\n"
<< "Let's make a loop where we create and fill up a\nvector with random ints each time!\n\n"
<< "std::vector<int> vec(10);\n"
<< "std::generate(vec.begin(), vec.end(), gen_int);\n\n";
for (int i = 0; i < 3; ++i) {
std::vector<int> vec(10);
std::generate(vec.begin(), vec.end(), gen_int);
std::cout << fmt::format("Iteration #{} using std::generate:\n{}\n\n", i, vec);
}
std::cout << "After all that, manually calling gen_int() a bunch of times:\n";
for (int _ = 0; _ < 10; ++_) std::cout << gen_int() << " ";
std::cout << "\n\nAs evident, we don't have the same identical-number issue.";
}
};