Fold expressions w C++17¶
Wyrażenia fold w językach funkcjonalnych¶
Koncept redukcji jest jednym z podstawowych pojęć w językach funkcjonalnych.
Fold w językach funkcjonalnych to rodzina funkcji wyższego rzędu zwana również reduce, accumulate, compress lub inject. Funkcje fold przetwarzają rekursywnie uporządkowane kolekcje danych (listy) w celu zbudowania końcowego wyniku przy pomocy funkcji (operatora) łączącej elementy.
Dwie najbardziej popularne funkcje z tej rodziny to fold (fold left) i foldr (fold right).
Przykład:
Redukcja listy [1, 2, 3, 4, 5] z użyciem operatora (+):
- użycie funkcji
fold
- redukcja od lewej do prawej
fold (+) 0 [1..5]
(((((0 + 1) + 2) + 3) + 4) + 5)
- użycie funkcji
foldr
- redukcja od prawej do lewej
foldr (+) 0 [1..5]
(1 + (2 + (3 + (4 + (5 + 0)))))
Redukcja w C++98 - std::accumulate¶
W C++ redukcja jest obecna poprzez implementację algorytmu
std::accumulate
.
#include <vector>
#include <numeric>
#include <string>
using namespace std::string_literals;
std::vector<int> vec = {1, 2, 3, 4, 5};
std::accumulate(std::begin(vec), std::end(vec), "0"s,
[](const std::string& reduction, int item) {
return "("s + reduction + " + "s + std::to_string(item) + ")"s; });
(((((0 + 1) + 2) + 3) + 4) + 5)
Variadic templates¶
C++11 wprowadziło variadic templates jako jeden z podstawowych mechanizmów zaawansowanego programowania z wykorzystaniem szablonów.
Variadic templates umożliwiają między innymi implementację funkcji akceptujących dowolną liczbę parametrów z zachowaniem bezpieczeństwa typów.
Implementacja redukcji z wykorzystaniem variadic templates często wykorzystuje idiom Head-Tail, który polega na rekursywnym wywołaniu funkcji z częścią parametrów. Rekurencja jest przerywana przez implementację funkcji albo przez specjalizację szablonu klasy dla końcowego przypadku.
namespace Cpp11
{
auto sum()
{
return 0;
}
template <typename Head, typename... Tail>
auto sum(Head head, Tail... tail)
{
return head + sum(tail...);
}
}
Cpp11::sum(1, 2, 3, 4, 5);
(int) 15
Fold expressions w C++17¶
Wyrażenia typu fold umożliwiają uproszczenie rekurencyjnych implementacji dla zmiennej liczby argumentów szablonu.
Przykład z wariadyczną funkcją sum(1, 2, 3, 4, 5)
z wykorzystaniem
fold expressions może być w C++17 zaimplementowany następująco:
template <typename... Args>
auto sum(Args&&... args)
{
return (... + args);
}
sum(1, 2, 3, 4, 5);
(int) 15
Składnia wyrażeń fold¶
Niech \(e = e_1, e_2, \dotso, e_n\) będzie wyrażeniem, które zawiera nierozpakowany parameter pack i \(\otimes\) jest operatorem fold, wówczas wyrażenie fold ma postać:
Unary left fold
\((\dotso\; \otimes\; e)\)
który jest rozwijany do postaci \((((e_1 \otimes e_2) \dotso ) \otimes e_n)\)
Unary right fold
\((e\; \otimes\; \dotso)\)
który jest rozwijany do postaci \((e_1 \otimes ( \dotso (e_{n-1} \otimes e_n)))\)
Jeśli dodamy argument nie będący paczką parametrów do operatora ...
,
dostaniemy dwuargumentową wersję wyrażenia fold. W zależności od
tego po której stronie operatora ...
dodamy dodatkowy argument
otrzymamy:
Binary left fold
\((a \otimes\; \dotso\; \otimes\; e)\)
który jest rozwijany do postaci \((((a \otimes e_1) \dotso ) \otimes e_n)\)
Binary right fold
\((e\; \otimes\; \dotso\; \otimes\; a)\)
który jest rozwijany do postaci \((e_1 \otimes ( \dotso (e_n \otimes a)))\)
Operatorem \(\otimes\) może być jeden z poniższych operatorów C++:
+ - * / % ^ & | ~ = < > << >>
+= -= *= /= %= ^= &= |= <<= >>=
== != <= >= && || , .* ->*
Elementy identycznościowe¶
Operacja fold dla pustej paczki parametrów (parameter pack) jest ewaluowana do określonej wartości zależnej od rodzaju zastosowanego operatora. Zbiór operatorów i ich rozwinięć dla pustej listy parametrów prezentuje tabela:
Operator | Wartość zwracana jako element identycznościowy |
---|---|
\(\&\&\) | true |
\(\mid\mid\) | false |
\(,\) | void() |
Jeśli operacja fold jest ewaluowana dla pustej paczki parametrów dla innego operatora, program jest nieprawidłowo skonstruowany (ill-formed).
Przykłady zastosowań wyrażeń fold w C++17¶
Wariadyczna funkcja przyjmująca dowolną liczbę argumentów
konwertowalnych do wartości logicznych i zwracająca ich iloczyn logiczny
(operator &&
):
template <typename... Args>
bool all_true(Args... args)
{
return (... && args);
}
bool result = all_true(true, true, false, true);
(bool) false
Funkcja print()
wypisująca przekazane argumenty. Implementacja
wykorzystuje wyrażenie binary left fold dla operatora <<
:
#include <iostream>
template <typename... Args>
void print(Args&&... args)
{
(std::cout << ... << args) << "\n";
}
print(1, 2, 3, 4);
1234
Sumowanie zawartości tablicy w czasie kompilacji.
#include <array>
#include <utility>
#include <iostream>
#define fw(...) ::std::forward<decltype(__VA_ARGS__)>(__VA_ARGS__)
namespace Folds
{
namespace Detail
{
template <typename... Args>
constexpr auto sum(Args&&... args)
{
return (... + fw(args));
}
template <typename T, size_t N, size_t... Is>
constexpr auto sum_impl(std::array<T, N> const& arr, std::index_sequence<Is...>)
{
return sum(std::get<Is>(arr)...);
}
}
template <typename T, size_t N>
constexpr T sum(std::array<T, N> const& arr)
{
return Detail::sum_impl(arr, std::make_index_sequence<N>{});
}
}
constexpr std::array<int, 5> arr1 { { 1, 2, 3, 4, 5 } };
static_assert(std::integral_constant<int, Folds::sum(arr1)>::value == 15);
constexpr auto sum_of_array = Folds::sum(arr1);
std::cout << sum_of_array << std::endl;
15
Iteracja po elementach różnych typów:
#include <iostream>
struct Window {
void show() { std::cout << "showing Window\n"; }
};
struct Widget {
void show() { std::cout << "showing Widget\n"; }
};
struct Toolbar {
void show(){ std::cout << "showing Toolbar\n"; }
};
Window wnd;
Widget widget;
Toolbar toolbar;
#define fw(...) ::std::forward<decltype(__VA_ARGS__)>(__VA_ARGS__)
auto printer = [](auto&&... args) { (fw(args).show(), ...); };
printer(wnd, widget, toolbar);
showing Window
showing Widget
showing Toolbar
Implementacja wariadycznej wersji algorytmu foreach()
z
wykorzystaniem funkcji std::invoke()
:
#include <iostream>
template <typename F, typename... Args>
auto invoke(F&& f, Args&&... args)
{
return std::forward<F>(f)(std::forward<Args>(args)...);
}
struct Printer
{
template <typename T>
void operator()(T&& arg) const { std::cout << arg; }
};
#include <string>
using namespace std::literals;
auto foreach = [](auto&& fun, auto&&... args) {
(..., invoke(fun, std::forward<decltype(args)>(args));
};
foreach(Printer{}, 1, " - one; ", 3.14, " - pi;"s);
1 - one; 3.14 - pi
Implementacja wariadycznych wersji algorytmów count()
oraz
count_if()
działających na listach typów:
#include <type_traits>
#include <iostream>
// count the times a predicate Predicate is satisfied in a typelist Lst
template <template<class> class Predicate, class... Lst>
constexpr size_t count_if = (Predicate<Lst>::value + ...);
// count the occurences of a type V in a typelist L
template <class V, class... Lst>
constexpr size_t count = (std::is_same<V, Lst>::value + ...);
static_assert(count_if<std::is_integral, float, unsigned, int, double, long> == 3);
static_assert(count<float, unsigned, int, double, long, float> == 1);