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

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.

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

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.

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.

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.

The type of fmap is "fmap: (a -> b) -> list[a] -> list[b]" I.e., in C++ speak,
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")); // 3list 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);

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 6If 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); // doubleLet'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.

## 15 comments:

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...)); };}

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.

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.

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.

ignore last comment, sorry, had ... on wrong side, shouldn't be programming new stuff so late x(

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.I very happy to read this informative post.Its a very useful for everyone.

ccna training institute

REVLON NAIL POLISH COLORS

lehnga choli dresses

bridal makeup

ball garments

babydoll night wear dresses

MEN WEAR WEDDING SHERWANI

Jewelry Women Wear

Saheli Couture By Preity Zinta Dresses

Parties Hairstyle

Zainab Chottani Pretty Suits

STYLISH SUNGLASSES DESIGNS

FROCKS DESIGNS FASHION

LONG GOWNS OUTFITS FASHION

HUMAN SALMAN KHAN STYLISH DRESSES

UTSAV FASHION NET INDIAN SAREES

Fancy Lawn Clothes

Nail Designs For UK Girls

Girls Footwear Selection

Pakistani Lehenga Clothes

MIDSUMMER SEASON WEDDING WEAR SHOES

Handbag & Clutches For Hot Girls

Front Open Double Shirt

Fashion Gallery Lehenga Choli

Stylo Best Mehndi Designs

HANDBAGS FOR WOMEN FASHION

Latest Sherwani Designs

Bridal Jewellery Set

Zara Shahjahan Eid Dresses

Mehndi Patterns for EID

SUMMER SEASON LADIES DRESSES FASHION

Sophia Tolli Collection

Earrings In Gold Collection

Actress Maya Ali – Fashion Collection

Bridal Gowns Collection

LADIES BLAZER STYLES OUTFITS

MEHNDI DRESS DESIGNS

BRIDAL SHOES

SHIRTS GRAY MAXI SKIRT SKIRTS

BRIDAL DRESSES WESTERN STYLE

LAWN AND CHIFFON OUTFITS

classic lawn suits

mix eid dresses

midsummer kurta

anarkali suits

Shouldn't the cases of List in line 1 and list in line 10 match? (In the first example)

*And also list on line 17

Post a Comment