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.