{"id":6213,"date":"2021-09-08T19:45:25","date_gmt":"2021-09-08T19:45:25","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/from-variadic-templates-to-fold-expressions\/"},"modified":"2024-07-22T10:44:25","modified_gmt":"2024-07-22T10:44:25","slug":"from-variadic-templates-to-fold-expressions","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/from-variadic-templates-to-fold-expressions\/","title":{"rendered":"From Variadic Templates to Fold Expressions"},"content":{"rendered":"

In my last two posts, “Variadic Templates or the Power of Three Dots<\/a>” and “More about Variadic Templates<\/a>“, I introduced variadic templates. This post goes one step further in the future, and presents fold expressions that can directly reduce a parameter pack with a binary operator.<\/p>\n

<\/p>\n

\"templates\"<\/p>\n

I intentionally skipped one import use case for variadic templates: the perfect factory function. When you combine perfect forwarding with variadic templates, you get the perfect factory function. The perfect factory function is a function that can accept an arbitrary number of arguments of any value category (lvalue or rvalue). Curious? Read my previous post, “C++ Core Guidelines: Rules for Variadic Templates<\/a>“.<\/p>\n

But now, I want to present something new with fold expressions.<\/p>\n

Fold Expressions<\/h2>\n

C++11 supports variadic templates. These are templates that can accept an arbitrary number of template parameters. A so-called parameter pack holds an arbitrary number. Additionally, with C++17, we got fold expressions. You can directly reduce a parameter pack with a binary operator thanks to fold expressions. Let’s look at reducing an arbitrary number of numbers to a value.<\/p>\n

<\/p>\n

\n
\/\/ variadicTemplatesFoldExpression.cpp<\/span>\n\n#include <iostream><\/span>\n\nbool<\/span> allVar<\/span>() {                                              \/\/ (1)<\/span>\n    return<\/span> true<\/span>;\n}\n\ntemplate<\/span><<\/span>typename<\/span> T, typename<\/span> ...Ts>                         \/\/ (2)<\/span><\/span>\nbool<\/span> allVar(T t, Ts ... ts) {                                \/\/ (3)<\/span><\/em>\n    return<\/span> t &&<\/span> allVar(ts...);                               \/\/ (4)<\/span><\/em>\n}\n\ntemplate<\/span><<\/span>typename<\/span>... Args>                                   \/\/ (5)<\/span><\/span><\/span>\nbool<\/span> all(Args... args) { return<\/span> (... &&<\/span> args); }            \n\nint<\/span> main() {\n\n    std::<\/span>cout <<<\/span> std::<\/span>boolalpha;\n\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\n\n    std::<\/span>cout <<<\/span> \"allVar(): \"<\/span> <<<\/span> allVar() <<<\/span> '\\n'<\/span>;\n    std::<\/span>cout <<<\/span> \"all(): \"<\/span> <<<\/span> all() <<<\/span> '\\n'<\/span>;\n\n    std::<\/span>cout <<<\/span> \"allVar(true): \"<\/span> <<<\/span> allVar(true<\/span>) <<<\/span> '\\n'<\/span>;\n    std::<\/span>cout <<<\/span> \"all(true): \"<\/span> <<<\/span> all(true<\/span>) <<<\/span> '\\n'<\/span>;\n\n    std::<\/span>cout <<<\/span> \"allVar(true, true, true, false): \"<\/span> \n              <<<\/span> allVar(true<\/span>, true<\/span>, true<\/span>, false<\/span>) <<<\/span> '\\n'<\/span>;\n    std::<\/span>cout <<<\/span> \"all(true, true, true, false): \"<\/span> \n              <<<\/span> all(true<\/span>, true<\/span>, true<\/span>, false<\/span>) <<<\/span> '\\n'<\/span>;\n\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\n\n}\n<\/pre>\n<\/div>\n
Both function templates allVar<\/span> and all<\/span> return at compile time if all arguments are true. allVar<\/span> uses variadic templates; all<\/span> fold expressions.<\/p>\n
The variadic templates allVar<\/code> applies recursion to evaluate its arguments. The function allVar<\/span> (1) is the boundary condition if the parameter pack is empty. The recursion takes place in the function template allVar<\/span> (2). The three dots stand for the so-called parameter pack. Parameter packs support two operations. You can pack or unpack them. It is packed in line (2); unpacked in (3) and (4).<\/p>\n
Line (4) requires our full attention. Here, the head of the parameter pack t<\/span> is combined with the rest ts<\/span> of the parameter pack ts using the binary operator &&. The call allVar(ts …)<\/span> triggers the recursion. The call includes a parameter pack that is the original one reduced by the head. Fold expressions (5) make our job easier. With fold expressions, you can directly reduce the parameter pack with the help of the binary operator: (... && args)<\/code>.<\/p>\n
Here is the output of the program.<\/p>\n
\"variadicTemplatesFoldExpressios\"<\/p>\n
A fold expression applies a binary operator to a parameter pack.<\/p>\n
Application of the binary Operator<\/h3>\n
A fold expression can apply the binary operator in two different ways.<\/p>\n
    \n
  1. With and without an initial value.
    \n<\/strong><\/li>\n
  2. Fold the variadic pack from left or from right
    \n<\/strong><\/li>\n<\/ol>\n
    There is a subtle difference between the algorithm allVar<\/span> and all.<\/span> All<\/span> have the default value true<\/code> for the empty parameter pack.<\/p>\n
    C++17 supports 32 binary operators in fold expressions: “+ – * \/ % ^ & | = < > << >> += -= *= \/= %= ^= &= |= <<= >>= == != <= >= && || , .* ->*<\/strong><\/span>” . A few of them have default-values:<\/p>\n
    \"BinaryOperatorDefault\"<\/p>\n
    You must provide an initial value for binary operators with no default value. You can specify an initial value for binary operators with a default value.<\/p>\n
    If the ellipsis stands left of the parameter pack, the parameter pack will be processed from the left. If right of the parameter pack, it will be processed from the right. This is also true if you provide an initial value.<\/p>\n
    Fold expression allows it to implement Haskell functions foldl, foldr, foldl1,<\/span> and foldr1 <\/span>directly in C++.<\/p>\n
    \u00a0A Flavor of Haskell<\/h3>\n
    The following table shows the four variations of fold expression and their Haskell pendants. The C++17 standard requires that fold expressions with initial value use the same binary operator op.<\/span><\/p>\n
    \"foldExpressions\"<\/p>\n
    The C++\u00a0 and Haskell variations differ in two points. The C++ version uses the default value as the initial value; the Haskell version uses the first element as the initial value. The C++ version processes the parameter pack at compile time, and the Haskell version processes its list at run time.<\/p>\n
    The following program shows all four variations of fold expression. Each one subtracts a few numbers.<\/p>\n
    <\/p>\n
    \n
    \/\/ foldVariations.cpp<\/span>\n\n#include <iostream><\/span>\n\ntemplate<\/span><<\/span>typename<\/span>... Args><\/span>                   \/\/ (1)<\/span>\nauto<\/span> diffL1(Args const<\/span>&<\/span>... args) {\n    return<\/span> (... -<\/span> args);\n}\n\ntemplate<\/span><<\/span>typename<\/span>... Args><\/span>                   \/\/ (2)<\/span>\nauto<\/span> diffR1(Args const<\/span>&<\/span>... args) {\n    return<\/span> (args -<\/span> ...);\n}\n\ntemplate<\/span><<\/span>typename<\/span> Init, typename<\/span>... Args><\/span>    \/\/ (3)<\/span>\nauto<\/span> diffL(Init init, Args const<\/span>&<\/span>... args) {\n    return<\/span> (init -<\/span> ... -<\/span> args);\n}\n\ntemplate<\/span><<\/span>typename<\/span> Init, typename<\/span>... Args><\/span>    \/\/ (4)<\/span>\nauto<\/span> diffR(Init init, Args const<\/span>&<\/span>... args) {\n    return<\/span> (args -<\/span> ... -<\/span> init);\n}\n\nint<\/span> main() {\n\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\n\n    std::<\/span>cout <<<\/span> \"diffL1(1, 2, 3): \"<\/span> <<<\/span> diffL1(1<\/span>, 2<\/span>, 3<\/span>) <<<\/span> '\\n'<\/span>;       \/\/ (1 - 2) - 3<\/span>\n    std::<\/span>cout <<<\/span> \"diffR1(1, 2, 3): \"<\/span> <<<\/span> diffR1(1<\/span>, 2<\/span>, 3<\/span>) <<<\/span> '\\n'<\/span>;       \/\/ 1 - (2 - 3)<\/span>\n    std::<\/span>cout <<<\/span> \"diffL(10, 1, 2, 3): \"<\/span> <<<\/span> diffL(10<\/span>, 1<\/span>, 2<\/span>, 3<\/span>) <<<\/span> '\\n'<\/span>; \/\/ ((10 - 1) - 2) - 3<\/span>\n    std::<\/span>cout <<<\/span> \"diffR(10, 1, 2, 3): \"<\/span> <<<\/span> diffR(10<\/span>, 1<\/span>, 2<\/span>, 3<\/span>) <<<\/span> '\\n'<\/span>; \/\/ 1 - (2 - (3 - 10))<\/span>\n\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\n\n}\n<\/pre>\n<\/div>\n
    The functions diffL1<\/code> (1) and diffL<\/code> (3) process the numbers from the left and the functions diffR1<\/code> (2) and diffR<\/code> (3) process them from the right. Additionally, the functions diffL<\/code> and diffR<\/code> use an initial start value. The comments in the main<\/code> function shows the processing steps.<\/p>\n
    \"foldVariations\"<\/p>\n
    I execute the Haskell pendant directly in the Haskell shell.<\/p>\n
    \"foldHaskell\"<\/h2>\n
    What’s next?<\/h2>\n
    Variadic templates, mainly fold expressions, enable concise expressions to be written for repeated operations. Learn more about it in my next post.<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
    In my last two posts, “Variadic Templates or the Power of Three Dots” and “More about Variadic Templates“, I introduced variadic templates. This post goes one step further in the future, and presents fold expressions that can directly reduce a parameter pack with a binary operator.<\/p>\n","protected":false},"author":21,"featured_media":6208,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[376],"tags":[442,441],"class_list":["post-6213","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-templates","tag-fold-expressions","tag-variadic-templates"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/6213","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=6213"}],"version-history":[{"count":2,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/6213\/revisions"}],"predecessor-version":[{"id":9757,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/6213\/revisions\/9757"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/6208"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=6213"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=6213"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=6213"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}