{"id":5163,"date":"2017-02-04T10:44:25","date_gmt":"2017-02-04T10:44:25","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/fold-expressions\/"},"modified":"2023-06-26T12:24:46","modified_gmt":"2023-06-26T12:24:46","slug":"fold-expressions","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/fold-expressions\/","title":{"rendered":"Fold Expressions"},"content":{"rendered":"

With fold expressions, you can implement Haskell functions foldl, foldr, foldl1<\/span>, and foldr1 <\/span>directly in C++. These four functions successively reduce a list to a single value.<\/p>\n

<\/p>\n

 <\/p>\n

Fold expressions<\/h2>\n

C++11 supports variadic templates. These are templates that can accept an arbitrary number of template arguments. A parameter pack holds an arbitrary number. Additionally, with C++17, you can directly reduce a parameter pack with a binary operator. Therefore, you can implement Haskell functions foldl, foldr, foldl1<\/span>, and foldr1 <\/span>in C++. Let’s look at how you can reduce a list to a value.<\/p>\n

 <\/p>\n

<\/p>\n

\n\n\n\n
\n
 1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11\r\n12\r\n13\r\n14\r\n15\r\n16\r\n17\r\n18\r\n19\r\n20\r\n21\r\n22\r\n23\r\n24\r\n25\r\n26\r\n27\r\n28\r\n29\r\n30<\/pre>\n<\/td>\n
\n
\/\/ foldExpression.cpp<\/span>\r\n\r\n#include <iostream><\/span>\r\n\r\nbool<\/span> allVar(){\r\n  return<\/span> true;\r\n}\r\n\r\ntemplate<\/span><typename<\/span> T, typename<\/span> ...Ts>\r\nbool<\/span> allVar(T t, Ts ... ts){\r\n  return<\/span> t && allVar(ts...);\r\n}\r\n\r\ntemplate<\/span><typename<\/span>... Args>\r\nbool<\/span> all(Args... args) { return<\/span> (... && args); }\r\n\r\nint<\/span> main(){\r\n\r\n  std::cout << std::boolalpha;\r\n\r\n  std::cout << \"allVar(): \"<\/span> << allVar() << std::endl;\r\n  std::cout << \"all(): \"<\/span> << all() << std::endl;\r\n\r\n  std::cout << \"allVar(true): \"<\/span> << allVar(true) << std::endl;\r\n  std::cout << \"all(true): \"<\/span> << all(true) << std::endl;\r\n\r\n  std::cout << \"allVar(true, true, true, false): \"<\/span> << allVar(true, true, true, false) << std::endl;\r\n  std::cout << \"all(true, true, true, false): \"<\/span> << all(true, true, true, false) << std::endl;\r\n\r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
 <\/p>\n
Both function templates allVar<\/span> and all<\/span> will return at compile time if all arguments are true. allVar<\/span> uses variadic templates, all<\/span> variadic templates in combination with fold expressions, at first to allVar.<\/span> Variadic templates use recursion to evaluate their arguments. Therefore, the function allVar<\/span> in line 5 is the boundary condition of the empty parameter pack. The recursion takes place in the function template allVar<\/span> in line 9. The parameter pack is defined thanks to the three dots – a so-called ellipsis. Parameter packs support two operations. You can pack and unpack them. It is packed in line 9; unpacked in lines 10 and 11. Line 11 needs 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 make our job easier. With fold expressions, you can directly reduce the parameter pack with the help of the binary operator.<\/p>\n
Here is the output of the program.<\/p>\n
\"foldingExpressions\"<\/p>\n<\/p>\n
Two variations<\/h3>\n
Now to the two variations of fold expression that result in four different forms of fold expressions. At first, fold expression can<\/p>\n
    \n
  1. have a default value<\/strong>.<\/strong> That value depends on the binary operator.
    <\/strong><\/li>\n
  2. be reduced from the left of the right.
    <\/strong><\/li>\n<\/ol>\n
     <\/p>\n
    There is a subtle difference between the algorithm allVar<\/span> and all.<\/span> All<\/span> have the default value true 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 have to 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. The same holds for right. This is also true if you provide an initial value.<\/p>\n
    The following table shows the four variations and their Haskell pendants. The C++17 standard requires fold expressions with initial value using the same binary operator op.<\/span><\/p>\n
    \"foldExpressions\"<\/p>\n
    The C++  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 its list at run time. <\/p>\n
    The small code snippet shows the once more algorithm all\u2014this<\/span> time, I use true<\/span> as the initial value.<\/p>\n
     <\/p>\n
    <\/p>\n
    \n
    template<\/span><typename<\/span>... Args>\r\nbool<\/span> all(Args... args) { return<\/span> (true && ... && args); }\r\n<\/pre>\n<\/div>\n
    What’s next?<\/h2>\n
    While fold expressions C++ supports the probably most genuine functional algorithm in C++17, the ranges library extends C++20 with three powerful functional concepts. Therefore, the next post<\/a> will be about the ranges library from Eric Niebler that gives lazy evaluation, function composition, and range comprehension a home in functional C++.<\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n<\/p>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    With fold expressions, you can implement Haskell functions foldl, foldr, foldl1, and foldr1 directly in C++. These four functions successively reduce a list to a single value.<\/p>\n","protected":false},"author":21,"featured_media":5161,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[365],"tags":[442,508],"class_list":["post-5163","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-functional","tag-fold-expressions","tag-haskell"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5163","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=5163"}],"version-history":[{"count":1,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5163\/revisions"}],"predecessor-version":[{"id":6892,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5163\/revisions\/6892"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/5161"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=5163"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=5163"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=5163"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}