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...);
}
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...)); };}
Nawaz said…
I commented on your answer here:

http://stackoverflow.com/questions/25338795/is-there-a-name-for-this-tuple-creation-idiom

Please fix the serious typos.
Moshe Magnes said…
This comment has been removed by the author.
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.
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(
awais kamran 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
manho valentine 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

Popular posts from this blog

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 two r…

Understanding Fold Expressions

C++17 has an interesting new feature called fold expressions. Fold expressions offer a compact syntax to apply a binary operation to the elements of a parameter pack. Here’s an example. template <typename... Args> auto addall(Args... args) { return (... + args); } addall(1,2,3,4,5); // returns 15. This particular example is a unary left fold. It's equivalent to ((((1+2)+3)+4)+5). It reduces/folds the parameter pack of integers into a single integer by applying the binary operator successively. It's unary because it does not explicitly specify an init (a.k.a. identity) argument. So, let add it. template <typename... Args> auto addall(Args... args) { return (0 + ... + args); } addall(1,2,3,4,5); // returns 15. This version of addall is a binary left fold. The init argument is 0 and it's redundant (in this case). That's because this fold expression is equivalent to (((((0+1)+2)+3)+4)+5). Explicit identity elements will come in handy a little la…

Folding Monadic Functions

In the previous two blog posts (Understanding Fold Expressions and Folding Functions) we looked at the basic usage of C++17 fold expressions and how simple functions can be folded to create a composite one. We’ll continue our stride and see how "embellished" functions may be composed in fold expressions.

First, let me define what I mean by embellished functions. Instead of just returning a simple value, these functions are going to return a generic container of the desired value. The choice of container is very broad but not arbitrary. There are some constraints on the container and once you select a generic container, all functions must return values of the same container. Let's begin with std::vector.
// Hide the allocator template argument of std::vector. // It causes problems and is irrelevant here. template <class T> struct Vector : std::vector<T> {}; struct Continent { }; struct Country { }; struct State { }; struct City { }; auto get_countries…