Fold Expressions

Contents[Show]

With fold expressions you can implement the from Haskell known functions foldl, foldr, foldl1 and foldr1 directly in C++. These four functions successively reduce a list to a single value.

 

Fold expressions

C++11 support variadic templates. These are templates that can accept an arbitrary number of template arguments. The arbitrary number is held by a parameter pack. Additionally, we get with C++17 that you can directly reduce a parameter pack with a binary operator. Therefore, you can implement the from Haskell known functions foldl, foldr, foldl1 und foldr1 in C++. Let's have a look, how you can reduce a list to a value.

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// foldExpression.cpp

#include <iostream>

bool allVar(){
  return true;
}

template<typename T, typename ...Ts>
bool allVar(T t, Ts ... ts){
  return t && allVar(ts...);
}

template<typename... Args>
bool all(Args... args) { return (... && args); }

int main(){

  std::cout << std::boolalpha;

  std::cout << "allVar(): " << allVar() << std::endl;
  std::cout << "all(): " << all() << std::endl;

  std::cout << "allVar(true): " << allVar(true) << std::endl;
  std::cout << "all(true): " << all(true) << std::endl;

  std::cout << "allVar(true, true, true, false): " << allVar(true, true, true, false) << std::endl;
  std::cout << "all(true, true, true, false): " << all(true, true, true, false) << std::endl;

}

 

The both function template allVar and all will return at compile time if all arguments are true. allVar uses variadic templates; all variadic templates in combination with fold expressions. At first to allVar. Variadic templates use recursion to evaluate its arguments. Therefore, the function allVar in line 5 is the boundary condition if the parameter pack is empty. The recursion takes place in the function template allVar in line 9. Thanks to the three dots - a so-called ellipsis -, the parameter pack is defined. Parameter packs support two operations. You can pack and unpack them. It is packed in line 9; unpacked in line 10 and 11. Line 11 needs our full attention. Here, the head of the parameter pack t is combined with the rest ts of the parameter pack ts by using the binary operator &&. The call allVar(ts ...) 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.

Here is the output of the program.

foldingExpressions

Two variations

Now to the two variations of fold expression that result in four different forms of fold expressions. At first, fold expression can

  1. have a default value. That value depends on the binary operator.
  2. be reduced from the left of the right.

 

There is a subtle difference between the algorithm allVar and all. All has the default value true for the empty parameter pack.

C++17 support 32 binary operators in fold expressions: "+ - * / % ^ & | = < > << >> += -= *= /= %= ^= &= |= <<= >>= == != <= >= && || , .* ->*" . A few of them have default-values:

 BinaryOperatorDefault

For binary operators that have no default value, you have to provide an initial value. For binary operators that have a default value, you can specify an initial value.

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.

The following table shows the four variations and their Haskell pendants. The C++17 standard requires that fold expressions with initial value use the same binary operator op.

foldExpressions

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 process the parameter pack at compile time and the Haskell version its list a run time. 

The small code snippet shows once more the algorithm all. This time I use true as the initial value.

 

template<typename... Args>
bool all(Args... args) { return (true && ... && args); }

What's next?

While fold expressions C++ supports the probably most genuine functional algorithm in C++17, the ranges library in contrary extends C++20 with three powerful functional concepts. Therefore, the next post will be about the ranges library from Eric Niebler that gives lazy evaluation, function composition and range comprehension a home in functional C++.

 

 

 

 

 

 

 

 

 

 

 

 

title page smalltitle page small Go to Leanpub/cpplibrary "What every professional C++ programmer should know about the C++ standard library".   Get your e-book. Support my blog.

 

 

Tags: C++17

Comments   

0 #1 mehndi 2017-02-13 08:59
Great post.
Quote
0 #2 Jacki 2017-04-12 05:22
I blog quite often and I seriously thank you for your information.
This article has truly peaked my interest.
I will take a note of your website and keep
chscking for new details about once per week.
I subscribed to your Feed too.
Quote
0 #3 Kenny 2017-05-14 00:40
Loving the info on this website, you have done outstanding job on the
blog posts.
Quote
0 #4 đèn gầm 2017-05-21 02:56
Keep on working, great job!
Quote
0 #5 Christoper 2017-06-19 03:02
I blog often and I genuinely thank you for your content.

Your article has really peaked my interest. I will take a note oof your blog and keep checking for new
information about once a week. I subscribed to your Feed
as well.
Quote

Add comment


My Newest E-Book

Latest comments

Subscribe to the newsletter (+ pdf bundle)

Blog archive

Source Code

Visitors

Today 728

All 332852

Currently are 174 guests and no members online