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);