Skip to main content

Fun with Lambdas: C++14 Style (part 3)

Now that we have C++14, it has opened up doors for truly mind-bending uses of lambdas--more specifically--generic lambdas. This blog post is the third installment in the series of "Fun with Lambdas: C++14 Style". Check out part 1 and part 2 if you have not already.

This post is about "monadic tuples".

Monad--a simple but powerful abstraction, however, considered quite difficult to understand in the imperative circles. We will look into what's know as the "continuation monad". As it turns out, in C++14, you need just a couple of lines of code to create an instance of a continuation monad.

I'm fairly new to the world of monads. So, things did not begin with great clarity for me. It all started with an intriguing question on Stackoverflow. As it turns out the same "trick" is also used in Boost.Hana and discussed on boost mailing list here.

What you see below is more or less how I came to understand the idiom as an instance of a monad. Some background in functional programming may be helpful in reading this post. A good understanding of nested generic lambdas is a must. If you are wondering if you should read the part 1 first, then you probably should.

Ok, lets cut to the chase.
auto List = [](auto ...xs) { 
    return [=](auto access) { return access(xs...); }; 
}; 

auto head = [](auto xs) { 
    return xs([](auto first, auto ...rest) { return first; }); 
}; 

auto tail = [](auto xs) { 
    return xs([](auto first, auto ...rest) { return list(rest...); }); 
}; 

auto length = [](auto xs) { 
    return xs([](auto ...z) { return sizeof...(z); }); 
}; 

int len = length(list(1, '2', "3"));  // 3

list is a generic lambda that accepts a variable number of arguments and returns a closure (an instance of the inner lambda) that captures the arguments by value. The inner lambda accepts a parameter (called access) that must be callable with an arbitrary number of arguments. The inner lambda simply expands the parameter pack while calling the callable. That way it provides "access" to the captured parameter pack.

If you squint a little, you will probably realize that list is like a constructor of a tuple. As a matter of fact, if you were to implement the inner lambda using a good old class template, you will most likely resort to using a std::tuple member.

head, tail, and length are examples of operations that you may perform on a list. head returns the first element, tail returns the list excluding the first element and length returns the size of the parameter pack. For example, a three element list is passed to the length lambda. As every list itself is a closure, it is called with an "accessor" function. The accessor simply does a sizeof... and returns the result, which propagates all the way out.

It is probably immediately apparent that this idiom adds life to otherwise drab variadic parameter packs. Don't get me wrong, variadic parameter packs are cool and we won't have other cool things like std::tuple without them. However, the point is that the language allows very few operations on a parameter pack. In general, you can't "store" them. Pretty much, you can expand a parameter pack, ask for its size, and unwind it using the car/cdr recursive style. And that's about it. Until now, To store a parameter pack you have to put it in a std::tuple.

But now there is an alternative. You can capture it using a lambda and provide access to it as done in the list lambda. As it turns out, this seemingly innocuous and perhaps needlessly convoluted approach to "accessing" parameter packs is phenomenally powerful.

WHY? ... the list lambda and the closure inside are special. Together, they form an implementation of a Continuation Monad.

A great introduction for continuation monad for C++ programmers is here. In essence, the list lambda above takes a value (a variadic parameter-pack) and returns a simple "continuator" (the inner closure). This continuator, when given a callable (called access), passes the parameter pack into it and returns whatever that callable returns.

Borrowing from the FPComplete blogpost, a continuator is more or less like the following.
template<class R, class A>
struct Continuator {
   virtual ~Continuator() {}
   virtual R andThen(std::function<R(A)> access) = 0;
};
The Continuator above is abstract--does not provide an implementation. So, here is a simple one.
template<class R, class A>
struct SimpleContinuator : Continuator<R, A> 
{
   SimpleContinuator(A x) : _x(x) {}
   R andThen(std::function<R(A)> access) {
       return access(_x);
   }
   A _x;
};
The SimpleContinuator accepts one value of type A and passes it on to access when andThen is called. The closure returned by the list lambda is conceptually the same. It is more general. Instead of a single value, the inner closure captures a parameter-pack and passes it to the access function. Neat!

Hopefully that explains what it means to be a continuator. but what does it mean to be a monad? Here is a good introduction using pictures.

The inner closure returned by the list lambda is also a list monad, which is implemented as a continuation monad. Note that continuation monad is the mother of all monads. I.e., you can implement any monad with a continuation monad. Of course, list monad is not out of reach.

As a parameter-pack is quite naturally a "list" (often of heterogeneous types), it makes sense for it to work like a list/sequence monad, where operations can be chained one after another. The list lambda above is a very interesting way of converting C++ parameter-packs to a monadic structure.

The head and length lambdas above, however, are a bit disappointing because they break the monad and the nested lambda inside simply returns a non-monadic value (something you can't chain more operations to). There is arguably a better way to write a chain of "processing" operations as shown below.

Functor

Before we can say that the list lambda is a monad constructor, we have to show that it is a functor. I.e., fmap must be written for the inner closure. Note that "functor" is a category theoretic term. It has no direct correlation with a C++ functor (i.e., a function object)

The list lambda above serves as the creator of the functor from a parameter pack---essentially it serves as the "return" in Haskell. That created functor keeps the parameter-pack with itself (capture) and it allows access to it provided you give a callable that accepts a variable number of arguments. Note that the callable is called EXACTLY-ONCE.

Lets write fmap for such a functor.
    
auto fmap = [](auto func) {
    return [func] (auto alist) {
        return alist([func](auto... xs) { return List(func(xs)...); });
    };
};
The type of the func must be (a -> b). I.e., in C++ speak,
    template <class a, class b>
    b func(a);
The type of fmap is "fmap: (a -> b) -> list[a] -> list[b]" I.e., in C++ speak,
    

    template <class Func, class a, class b>
    list<b> fmap(Func, list<a>);
I.e., when fmap is given a function from a to b, it simply returns another function that maps list-of-a to a list-of-b.
Now you can do
    
    auto twice = [](auto i) { return 2*i; };
    auto print = [](auto i) { std::cout << i << " "; return i; };
    auto l1 = List(1, 2, 3, 4);
    auto l2 = fmap(twice)(l1);
    auto l3 = fmap(print)(l2); // prints 2 4 6 8 on clang (g++ in reverse)
Therefore, it is a functor.

Monad

Now, lets try to write a flatmap (a.k.a. bind, selectmany)

Type of flatmap is "flatmap: (a -> list[b]) -> list[a] -> list[b]"

I.e., given a function that maps a to a list-of-b and a list-of-a, flatmap return a list-of-b. Essentially, it takes each element from list-of-a, calls func on it, receives (potentially empty) list-of-b one-by-one, then concatenates all the list-of-b, and finally returns the concatenated list-of-b.

Here's an implementation of flatmap for List.
 
    auto concat = [](auto l1, auto l2) {
        auto access1 = [=](auto... p) {
          auto access2 = [=](auto... q) {
            return List(p..., q...);
          };
          return l2(access2);
        };
        return l1(access1);
    };

    template <class Func>
    auto flatten(Func)
    {
      return List(); 
    }
    
    template <class Func, class A, class... B>
    auto flatten(Func f, A a, B... b)
    {
      return concat(f(a), flatten(f, b...));
    }
    
    auto flatmap = [](auto func) {
       return [func](auto alist) {
           return alist([func](auto... xs) { return flatten(func, xs...);  });
    };
Now you can do a lot of powerful things with a list. For example,
 
    auto pair     = [](auto i) { return list(-i, i); };
    auto count    = [](auto... a) { return list(sizeof...(a)); };
    
    auto l1 = List(1, 2, 3);
    auto l2 = flatmap(pair)(l1);
    auto l3 = fmap(print)(l2); // prints -1, 1, -2, 2, -3, 3 on clang (g++ in reverse)
    auto l4 = l3(count);    
    auto l5 = fmap(print)(l4); // prints 6.
The count function is a monad-perserving operation because it returns a List of single element. If you really want to get the length (not wrapped in a List) you have to terminate the monadic chain and get the value as follows.
 
    auto len = [](auto ...z) { return sizeof...(z); }; 

    auto l1 = List(10, 20, 30);
    auto l2 = flatmap(pair)(l1);
    std::cout << l2(len); // prints 6
If done right, the collection pipeline pattern (e.g., filter, reduce) can now be applied to C++ parameter-packs. So lets try to do that.

You might have noticed that we're doing only one operation per line and giving names to each intermediate result (i.e., l1, l2, l3 etc). Naming the intermediate results is unnecessary but if we don't, readability of code goes out the window.

Lets try to rewrite the previous program where we print 1, 1, -2, 2, -3, 3.
    
    auto l3 = 
      fmap(print)(flatmap(pair)(List(1, 2, 3))); 
    // prints -1, 1, -2, 2, -3, 3 on clang (g++ in reverse)
The above code is pretty much incomprehensible and at this point you probably want to click away. But bear with me for just one moment. There's a pattern here and we can factor that out. I'm going to use C++ operator overloading so that the code looks significantly more readable.
 
template <class LIST, class Func>
auto operator > (LIST l, Func f)
{
  return fmap(f)(l);   
}

template <class LIST, class Func>
auto operator >= (LIST l, Func f)
{
  return flatmap(f)(l);   
}
Operator > accepts our special list as the left hand side argument and a function from a->b as the right hand side argument. It uses fmap internally. The Operator >= is similar but it takes a function that goes from a->List[b] and uses flatmap internally. Remember, both functions return the special list (monadic tuple).

And now's the show time!
 
  auto l3 = 
     List(1, 2, 3) >= pair > print;  
  // prints -1, 1, -2, 2, -3, 3 on clang (g++ in reverse)
Suddenly, you can read the program from left to right and all the fmap/flatmap boilerplate is hidden inside the overloaded operators. You are looking at a tiny Domain-Specific Language (DSL) for piping operations on collections. The chain can be arbitrarily extended to the right.

Before we celebrate though, lets verify the monad laws.

Monad Laws

Let's make sure the list monad satisfies all three monad laws.
    
  template <class M1, class M2>
  void assert_equal(M1 m1, M2 m2)
  {
    auto to_vector = [](auto... a) { return std::vector<int> { a... }; };
    assert(m1(to_vector) == m2(to_vector));   
  }
  
  auto triplet(int i)  { return List(-i, 0, i); }

  {
    auto M = List(11);
    std::cout << "Monad law (left identity)\n";
    assert_equal(flatmap(pair)(M), pair(11));
    assert_equal(M >= pair, pair(11));
    
    std::cout << "Monad law (right identity)\n";
    assert_equal(flatmap(List)(M), M);
    assert_equal(M >= List, M);
     
    std::cout << "Monad law (associativity)\n";
    assert_equal(flatmap(triplet)(flatmap(pair)(M)),
                 flatmap([=](auto x) { return flatmap(triplet)(pair(x)); })(M));
    assert_equal(M >= pair >= triplet, 
                 M >= [=](auto x) { return pair(x) >= triplet; });
  }
All assertions are satisfied.

Collection Pipeline

Although the above list lambda is provably a monad and shares characteristics of the proverbial list-monad, it is quite unpleasant to work with as a collection pipeline. Especially because the behavior of a common collection pipeline combinator filter (a.k.a where) does not meet common expectations.

The reason is just how C++ lambdas work. Each lambda expression produces a function object of a unique type. Therefore, list(1,2,3) produces a type that has nothing to do with list(1) and an empty list, which in this case would be list().

The straight-forward implementation of `where` fails compilation because in C++ a function can not return two different types.
    
   auto where_broken = [](auto func) {
      return flatmap([func](auto i) { 
          return func(i)? list(i) : list(); // broken :-(
      }); 
    };
In the above implementation, func returns a boolean. It's a predicate that says true or false for each element. The ?: operator does not compile because the types of list(i) and list() (empty list) are different.

So, a different trick can be used to allow continuation of the collection pipeline. Instead of actually filtering the elements, they are simply flagged as such---and that's what makes it unpleasant.
    
  auto where_unpleasant = [](auto func) {
    return [=](auto i) { 
        return std::make_pair(func(i), i);
    }; 
  };
The where_unpleasant gets the job done but unpleasantly... For example, this is how you can filter negative elements.
    
    auto positive = [](auto i) { return i >= 0; };
    auto pair_print = [](auto pair) { 
      if(pair.first) 
         std::cout << pair.second << " "; 
      return pair; 
    };
    List(10, 20) >= pair > where_unpleasant(positive) > pair_print; 
    // prints 10 and 20 in some order


Heterogeneous Tuples

So far the discussion was about homogeneous tuples. Now lets generalize it to true tuples. Note that fmap, flatmap, where take only one callback lambda. To provide multiple lambdas each working on one type, we can overload them. For example,
    template <class A, class... B>
    struct overload : overload<A>, overload<B...> {
      overload(A a, B... b) 
          : overload<A>(a), overload<B...>(b...) 
      {}  
      using overload<A>::operator ();
      using overload<B...>::operator ();
    };
     
    template <class A>
    struct overload<A> : A {
      overload(A a) 
          : A(a) {} 
      using A::operator();
    };
    
    template <class... F>
    auto make_overload(F... f) {
      return overload<F...>(f...);   
    }
    
    auto test = 
       make_overload([](int i) { std::cout << "int = " << i << std::endl; },
                     [](double d) { std::cout << "double = " << d << std::endl; });
    test(10); // int 
    test(9.99); // double    
Let's use the overloaded lambda technique to process a heterogeneous tuple continuator.
    
        auto int_or_string = 
            make_overload([](int i) { return 5*i; },
                          [](std::string s) { return s+s; });
        List(10, "ab") > int_or_string >  print; // prints 50 and abab (gcc in reverse)

Finally, Here is the complete live example. For more relevant reading, also see the lambda-over-lambda.

P.S. Why is the order of output not the same across compilers? The order of variadic pack expansion is defined in the standard which corresponds to the original order of the pack. The order of evaluating function argument expressions is, however, not standardized. For example, checkout the implementation of fmap. func(z) is called as many time as there are arguments. However, the order in which multiple calls to func are evaluated is not guaranteed. As the calls to func print the values out to the console, the output is unpredictable across compilers. See more discussion on reddit/r/cpp.

Comments

Kirilodius said…
This comment has been removed by the author.
Kirilodius said…
template <class... F&qt;
auto make_overload(F... f) {
return overload<F...<(f...);
}
Typo? Should be replaced with
template <class... F&qt;
auto make_overload(F... f) {
return overload<F...&qt;(f...);
}
Unknown said…
After one week of research, I'm sure I will use this trick instead of std::tuple whenever I can. It has no runtime indexing too (Despite my gaffe on twitter, that worked for homogeneous tuples only). Anyway, it allows you to use tuple argumments directly (Which std::tuple does not, std::get is a monstrosity). Also if you require backwards compatibility (i.e. use the monad tuple when a tsd::tuple is expected), just write another functor from tuple() to std::tuple: auto std_tuple = [](auto... args) { return [=](auro f){ return f(std::make_tuple(args...)); };}
Unknown said…
This comment has been removed by the author.
Joe said…
Hi, some reason, your tail function is not compiling on g++ 4.9 nor clang 3.4.

"error: expected expression
return xs([](auto first, auto ...rest) { return List( ...rest); });
"

point to the "...rest" on the return.

Am I doing something wrong? Your head and list functions worked fine.
Joe said…
ignore last comment, sorry, had ... on wrong side, shouldn't be programming new stuff so late x(
Unknown said…
Your work is really appreciative thanks man. C++ in Urdu
C and C++ classes in Delhi NCR- RKM IT Institute provides high quality C and C++ classes in Delhi, C and C++ training in Delhi NCR, C and C++ live project training in Delhi NCR at affordable price. To get details information about free and timing visit our website Edutech.rkmsolution.com.
Anonymous said…
I very happy to read this informative post.Its a very useful for everyone.
ccna training institute
Anonymous said…
Shouldn't the cases of List in line 1 and list in line 10 match? (In the first example)
Anonymous said…
*And also list on line 17
Anonymous said…
Thanks for your ideas. You can also find the details on Affity Solutions, at the C++ Developers. The main object of the Affity Solutions is to provide quality web services and is among the few software development company in Nagpur.
golden slot mobile
gclub
Serverental said…
Great information Thanks for sharing.
entry level advanced server on rentals
global said…
Thanks a lot for your well written and interesting post.
Branded workstations for rent

Popular Content

Unit Testing C++ Templates and Mock Injection Using Traits

Unit testing your template code comes up from time to time. (You test your templates, right?) Some templates are easy to test. No others. Sometimes it's not clear how to about injecting mock code into the template code that's under test. I've seen several reasons why code injection becomes challenging. Here I've outlined some examples below with roughly increasing code injection difficulty. Template accepts a type argument and an object of the same type by reference in constructor Template accepts a type argument. Makes a copy of the constructor argument or simply does not take one Template accepts a type argument and instantiates multiple interrelated templates without virtual functions Lets start with the easy ones. Template accepts a type argument and an object of the same type by reference in constructor This one appears straight-forward because the unit test simply instantiates the template under test with a mock type. Some assertion might be tested in

Covariance and Contravariance in C++ Standard Library

Covariance and Contravariance are concepts that come up often as you go deeper into generic programming. While designing a language that supports parametric polymorphism (e.g., templates in C++, generics in Java, C#), the language designer has a choice between Invariance, Covariance, and Contravariance when dealing with generic types. C++'s choice is "invariance". Let's look at an example. struct Vehicle {}; struct Car : Vehicle {}; std::vector<Vehicle *> vehicles; std::vector<Car *> cars; vehicles = cars; // Does not compile The above program does not compile because C++ templates are invariant. Of course, each time a C++ template is instantiated, the compiler creates a brand new type that uniquely represents that instantiation. Any other type to the same template creates another unique type that has nothing to do with the earlier one. Any two unrelated user-defined types in C++ can't be assigned to each-other by default. You have to provide a

Multi-dimensional arrays in C++11

What new can be said about multi-dimensional arrays in C++? As it turns out, quite a bit! With the advent of C++11, we get new standard library class std::array. We also get new language features, such as template aliases and variadic templates. So I'll talk about interesting ways in which they come together. It all started with a simple question of how to define a multi-dimensional std::array. It is a great example of deceptively simple things. Are the following the two arrays identical except that one is native and the other one is std::array? int native[3][4]; std::array<std::array<int, 3>, 4> arr; No! They are not. In fact, arr is more like an int[4][3]. Note the difference in the array subscripts. The native array is an array of 3 elements where every element is itself an array of 4 integers. 3 rows and 4 columns. If you want a std::array with the same layout, what you really need is: std::array<std::array<int, 4>, 3> arr; That's quite annoying for