boost_hana_learning.txt

Boost Hana:

Functional programming concepts:
0. useful links
	0.1 Monads : https://monadmadness.wordpress.com/2015/01/02/monoids-functors-applicatives-and-monads-10-main-ideas/
	https://bartoszmilewski.com/2011/07/11/monads-in-c/
	https://bartoszmilewski.com/2015/05/18/using-monads-in-c-to-solve-constraints-3-the-tale-of-two-monads/
	https://bartoszmilewski.com/2015/05/11/using-monads-in-c-to-solve-constraints-1-the-list-monad/
	https://bartoszmilewski.com/2014/04/21/getting-lazy-with-c/
	0.2 Tag dispatching: A tag is simply an empty class whose only purpose is to convey some information at compile time
		0.2.1 If a tag AA is derived from another tag BB, the compiler will select the BB version for both types are marked with tag AA and BB. This is not possible for specialization on tags. 
		
1. Monads example
	1.1 here’s a problem that you may get as an interview question. It’s a small problem, so the advantages of various approaches might not be immediately obvious, especially if you’ve been trained all your life in imperative programming, and you are seeing monads for the first time.

	You’re supposed write a program to solve this puzzle:

				  s e n d
				+ m o r e
				---------
				m o n e y
	Each letter correspond to a different digit between 0 and 9. Before you continue reading this post, try to think about how you would approach this problem.
	1.2 The Analysis: It never hurts to impress your interviewer with your general knowledge by correctly classifying the problem. This one belongs to the class of “constraint satisfaction problems.” The obvious constraint is that the numbers obtained by substituting letters with digits have to add up correctly. There are also some less obvious constraints, namely the numbers should not start with zero.
		1.2.1 You would deduce that m must stand for 1 because that’s the largest possible carry from the addition of two digits (even if there is a carry from the previous column). Then you’d figure out that s must be either 8 or 9 to produce this carry, and so on. Given enough time, you could probably write an expert system with a large set of rules that could solve this and similar problems. (Mentioning an {{expert system}} could earn you extra points with the interviewer.)
		1.2.2 However, the small size of the problem suggests that a simple brute force approach is probably best. The interviewer might ask you to estimate the number of possible substitutions, which is 10!/(10 – 8)! or roughly 2 million. That’s not a lot. So, really, the solution boils down to generating all those substitutions and testing the constraints for each.
	1.3 The Straightforward Solution: 
		The mind of an imperative programmer immediately sees the solution as a set of 8 nested loops (there are 8 unique letters in the problem: s, e, n, d, m, o, r, y). Something like this:

			for (int s = 0; s < 10; ++s)
				for (int e = 0; e < 10; ++e)
					for (int n = 0; n < 10; ++n)
						for (int d = 0; d < 10; ++d)
							...
		and so on, until y. But then there is the condition that the digits have to be different, so you have to insert a bunch of tests like:

			e != s
			n != s && n != e
			d != s && d != e && d != n
			and so on, the last one involving 7 inequalities… Effectively you have replaced the uniqueness condition with 28 new constraints.

		This would probably get you through the interview at Microsoft, Google, or Facebook, but really, can’t you do better than that?
	1.4 The Smart Solution: The problem with our naive solution is the 28 additional constraints. Well, I guess one could live with that — except that this is just a tiny example of a whole range of constraint satisfaction problems, and it makes sense to figure out a more general approach.
		1.4.1 The problem can actually be formulated as a superposition of two separate concerns. One deals with the depth and the other with the breadth of the search for solutions.
		1.4.2 Let me touch on the depth issue first. Let’s consider the problem of creating just one substitution of letters with numbers. This could be described as picking 8 digits from a list of 0, 1, …9, one at a time. Once a digit is picked, it’s no longer in the list. We don’t want to hard code the list, so we’ll make it a parameter to our algorithm. Notice that this approach works even if the list contains duplicates, or if the list elements are not easily comparable for equality (for instance, if they are futures). We’ll discuss the list-picking part of the problem in more detail later.
		1.4.3 Now let’s talk about breadth: we have to repeat the above process for all possible picks. This is what the 8 nested loops were doing. Except that now we are in trouble because each individual pick is destructive. It removes items from the list — it mutates the list. This is a well known problem when searching through solution spaces, and the standard remedy is called backtracking. Once you have processed a particular candidate, you put the elements back in the list, and try the next one. Which means that you have to keep track of your state, either implicitly on your function’s stack, or in a separate explicit data structure.
		1.4.3 Wait a moment! Weren’t we supposed to talk about functional programming? So what’s all this talk about mutation and state? Well, who said you can’t have state in functional programming? Functional programmers have been using the state monad since time immemorial. And mutation is not an issue if you’re using persistent data structures. So fasten your seat belts and make sure your folding trays are in the upright position.
	1.5 The List Monad: We’ll start with a small refresher in quantum mechanics. As you may remember from school, quantum processes are non-deterministic. You may repeat the same experiment many times and every time get a different result. There is a very interesting view of quantum mechanics called the many-worlds interpretation, in which every experiment gives rise to multiple alternate histories. So if the spin of an electron may be measured as either up or down, there will be one universe in which it’s up, and one in which it’s down.
		1.5.1 We’ll use the same approach to solving our puzzle. We’ll create an alternate universe for each digit substitution for a given letter. So we’ll start with 10 universes for the letter s; then we’ll split each of them into ten universes for the letter e, and so on. Of course, most of these universes won’t yield the desired result, so we’ll have to destroy them. I know, it seems kind of wasteful, but in functional programming it’s easy come, easy go. The creation of a new universe is relatively cheap. That’s because new universes are not that different from their parent universes, and they can share almost all of their data. That’s the idea behind persistent data structures. These are the immutable data structures that are “mutated” by cloning. A cloned data structure shares most of its implementation with the parent, except for a small delta. We’ll be using persistent lists described in this post (https://bartoszmilewski.com/2013/11/13/functional-data-structures-in-c-lists/).
		Once you internalize the many-worlds approach to programming, the implementation is pretty straightforward. First, we need functions that generate new worlds. Since we are cheap, we’ll only generate the parts that are different. So what’s the difference between all the worlds that we get when selecting the substitution for the letter s? Just the number that we assign to s. There are ten worlds corresponding to the ten possible digits (we’ll deal with the constraints like s being different from zero later). So all we need is a function that generates a list of ten digits. These are our ten universes in a nutshell. They share everything else.
		Once you are in an alternate universe, you have to continue with your life. In functional programming, the rest of your life is just a function called a continuation. I know it sounds like a horrible simplification. All your actions, emotions, and hopes reduced to just one function. Well, maybe the continuation just describes one aspect of your life, the computational part, and you can still hold on to our emotions.
		So what do our lives look like, and what do they produce? The input is the universe we’re in, in particular the one number that was picked for us. But since we live in a quantum universe, the outcome is a multitude of universes. So a continuation takes a number, and produces a list. It doesn’t have to be a list of numbers, just a list of whatever characterizes the differences between alternate universes. In particular, it could be a list of different solutions to our puzzle — triples of numbers corresponding to “send”, “more”, and “money”. (There is actually only one solution, but that’s beside the point.)
		And what’s the very essence of this new approach? It’s the binding of the selection of the universes to the continuation. That’s where the action is. This binding, again, can be expressed as a function. It’s a function that takes a list of universes and a continuation that produces a list of universes. It returns an even bigger list of universes. We’ll call this function for_each, and we’ll make it as generic as possible. We won’t assume anything about the type of the universes that are passed in, or the type of the universes that the continuation k produces. We’ll also make the type of the continuation a template parameter and extract the return type from it using auto and decltype:
		
			template<class A, class F>
			auto for_each(List<A> lst, F k) -> decltype(k(lst.front()))
			{
				using B = decltype(k(lst.front()).front());
				// This should really be expressed using concepts
				static_assert(std::is_convertible<
					F, std::function<List<B>(A)>>::value,
					"for_each requires a function type List<B>(A)");

				List<List<B>> lstLst = fmap(k, lst);
				return concatAll(lstLst);
			}
		1.5.2 The function fmap is similar to std::transform. It applies the continuation k to every element of the list lst. Because k itself produces a list, the result is a list of lists, lstLst. The function concatAll concatenates all those lists into one big list. Congratulations! You have just seen a monad. This one is called the list monad and it’s used to model non-deterministic processes. The monad is actually defined by two functions. One of them is for_each, and here’s the other one:

			template<class A>
			List<A> yield(A a)
			{
				return List<A> (a);
			}
			
		It’s a function that returns a singleton list. We use yield when we are done multiplying universes and we just want to return a single value. We use it to create a single-valued continuation. I will later rename these functions to mbind and mreturn, because they are part of any monad, not just the list monad. The names like for_each or yield have a very imperative ring to them. That’s because, in functional programming, monadic code plays a role similar to imperative code. But neither for_each nor yield are control structures — they are functions. In particular for_each, which sounds and works like a loop, is just a higher order function; and so is fmap, which is used in its implementation. Of course, at some level the code becomes imperative — fmap can either be implemented recursively or using an actual loop — but the top levels are just declarations of functions. Hence, declarative programming.
		There is a slight difference between a loop and a function on lists like for_each: for_each takes a whole list as an argument, while a loop might generate individual items — in this case integers — on the fly. This is not a problem in a lazy functional language like Haskell, where a list is evaluated on demand. The same behavior may be implemented in C++ using streams or lazy ranges. I won’t use it here, since the lists we are dealing with are short, but you can read more about it in my earlier post Getting Lazy with C++ (https://bartoszmilewski.com/2014/04/21/getting-lazy-with-c/)
		We are not ready yet to implement the solution to our puzzle, but I’d like to give you a glimpse of what it looks like. For now, think of StateL as just a list. See if it starts making sense (I grayed out the usual C++ noise):

=================================================
Variadic expansion:
1. A universe way of writing a function overload for some traits

// enabled via the return type
template<typename T>
auto function(const T &) -> typename std::enable_if<interesting_traits<T>::value>::type;

or 

//enabled via a template parameter
template<typename T, typename std::enable_if<interesting_traits<T>::value, int>::type = 0>
auto function( const T& );

2. Variadic SFINAE
template<typename T, typename std::enable_if<interesting_traits<T>::value, int>::type...>
auto function( const T& );

or 

template<typename T, typename std::enable_if<interesting_traits<T>::value>::*...>
auto function( const T& );

3. How to call a function per each argument, like
template<typename ...Args>
void foo( Args... args )
{
	bar( args )... // invalid
}
Solution: define a function that accept varadic arguments and then calling the function we want to call, like
template<typename ...Args>
void swallow( Args &&... )
{
	//empty
}

template<typename ...Args>
void foo( Args... args )
{
	swallow(bar( args )...) 
}

however, if bar() returns void for one of arguments, the above cannot work. An alternative way is

template<typename ...Args>
void foo( Args... args )
{
	swallow((bar( args ),0)...) 
}

In this way, the void type will be accepted.

However, since the unpacking of the arguments for the function is not defined, the sequence of the expanded arguments is different for different compilers.

The solution to this issue is using brace initialized list 
* define a empty struct
struct unit{};

*rewrite swallow as a struct
struct swallow
{
	template<typename ...Args>
	swallow( Args&&.... )
	{
	}
}

then calling bar is like
template<typename ...Args>
void foo( Args... args )
{
	swallow{(bar<std::forward<Args>(args),unit{})...}
}

4. Lambdas
* Lambdas are expressions

template<typename ...Ts>
void print(variant<Ts...> v)
{
	using visitor_type = void(*)(variant<Ts...>);
	
	static visitor_type handlers[] = {
		[]( variant<Ts...> v )
		{
			using T = Ts;
			bar( std::forward<decltype<get<index_of<T,Ts...>::value>>( v ) );
		}
	}...;
	
	handlers[v.index()](std::move(v));
}

notice: handlers are packs and "using T = Ts" will be expanded outside of the lambda body.

=================================================

Core:

1	when: it is a template with bool as template typename. only define as a simple struct
template<bool condition>
struct when.

2	tag_of: when using with when<>, the SFINAE will only enable the specialization if and only if on when<true>. (similar to std::enable_if)
	2.1 tag_of<T> is same type as tag_of<U>, where U is the type T after being stripped of all reference and cv-qualifers. This make it unnecessary to specialize tag_of for all reference and cv combinations.
	2.2 tag_of<tag_of<T>::type>::type is same type as tag_of<T>::type;
	2.3 The general template definition:
		
		template<typename T, typename = void> struct tag_of
		
	then define a specialization for when<true>
	
		template<typename T, typename>
		struct tag_of : tag_of<T, when<true>> {} 
	
	we must provide how tag_of<T, when<{boolean value}>> looks like
	
		template<typename T, bool condition>
		struct tag_of<T, when<condition>>
		{
			using type = T;
		}
	
	so, if expression in when<expression> is a well formed, tag_of will have a type = T. Otherwise, only tag_of<T,when<false>> has a type = T, not type tag_of<T>
	
	then provide a series of specialization for different cv and reference combinations;
	struct tag_of<T const> : tag_of<T>
	struct tag_of<T volatile> : tag_of<T>
	struct tag_of<T const volatile> : tag_of<T>
	struct tag_of<T&> : tag_of<T>
	struct tag_of<T&&> : tag_of<T>
3. is_a: is_a<Tag,T> is a compile_time logical representing whether the tag of T is exactly tag. i.e. std::is_same<Tag, tag_of<T>::type> ??

4. Monoid (From : https://functionalcpp.wordpress.com/ )
	4.1 Type classes are a feature of Haskell which is very similar to the upcoming Concepts. Both define interfaces to a data type, which can be defined separately from the data, in contrast to member functions. To introduce the notion of type classes, let’s start with a simple one: the monoid. A monoid is an object which has a binary operation and an identity for that operation. For our purposes, we will call the identity empty() and the operation append.
	4.2 The basic template for the type class follows:
		template<class T>
		struct monoid
		{
			// T empty()
			// T append(T,T)
			static constexpr bool is_instance = false;
		};
		
	Most things are not monoids and so we also add a boolean which marks this. This allows us to do type checking using std::enable_if or static_assert.
	4.3 When an object has the type class interface, we say that it is an instance of the type class. For example, the monoid instance for integers can be written as:
		template<>
		struct monoid<int>
		{
			static int empty(){return 0;}
			static int append(int lhs, int rhs){return lhs+rhs;}
			static constexpr bool is_instance = true;
		};
	Now if we wanted to write a function using monoids, we could do so easily and with guarantees of type safety. For example, here is a function which “accumulates” monoid values from a vector:
	
	template< class T,  class = typename std::enable_if<monoid<T>::is_instance>::type>
	T accumulator(const std::vector<T>& in)
	{
		T out{monoid<T>::empty()};
 
		for (const T& t : in)
			out = monoid<T>::append(out,t);
		return out;
	}
 
	int main()
	{
		std::cout << accumulator(std::vector<int>{1,2,3}) << "\n";
	 
		return 0;
	}
	
	output: 6
	
	4.4 Obviously, there are quite a few data types which display monoid behaviour, including all the fundamental data types. There’s quite a bit of repetition which can be removed, also reducing the chance for error. Many of the monoids, including all the fundamental types implement operator+ and are value-initialized to a reasonable value. A default monoid can be written to represent this.
		template<class T>
		struct default_monoid
		{
			static T empty(){return T{};}
			static T append(const T& lhs, const T& rhs){return lhs+rhs;}
			static constexpr bool is_instance = true;
		};
		 
		// example use
		template<>
		struct monoid<int> : public default_monoid<int>
		{};
		 
		template<>
		struct monoid<char> : public default_monoid<char>
		{}
	4.5 We can further reduce the repetition through the use of x macros (search x macros in wikipedia):
	
		#define FUNDAMENTAL_TYPES\
			X(bool)\
			X(signed char)\
			X(unsigned char)\
			X(char)\
			X(wchar_t)\
			X(char16_t)\
			X(char32_t)\
			X(short)\
			X(unsigned short)\
			X(int)\
			X(unsigned)\
			X(long)\
			X(unsigned long)\
			X(long long)\
			X(unsigned long long)
		 
		#define X(a)\
			template<>\
			struct monoid<a> : public default_monoid<a>\
			{};
		 
		FUNDAMENTAL_TYPES;
		#undef X
		This code will generate monoid instances based on default_monoid for all the fundamental data types.We can also use default_monoid for strings:
			template<>
			struct monoid<std::string> : public default_monoid<std::string>
			{};
	4.6 But for some types we need to customize a bit more:
			template<class T>
			struct monoid<std::vector<T>>
			{
				static std::vector<T> empty(){return std::vector<T>{};}
			 
				static std::vector<T> append(std::vector<T> lhs, const std::vector<T>& rhs)
				{
					for (const T& t : rhs)
						lhs.push_back(t);
			 
					return lhs;
				}
			 
				static constexpr bool is_instance = true;
			};
		it is suffice to say that containers, string streams, numerical types and many more can all instantiate the monoid type class. The combination of generic programming and functional programming is very powerful. The accumulator function from earlier can now work with every type that is an instance of monoid! Pretty neat. For example:
		
		int main()
		{
			int a = accumulator(std::vector<int>{1,2,3});
			std::cout << a << "\n";
		 
			int b = accumulator(accumulator(std::vector<std::vector<int>>{{1,2,3},{4,5,6},{7,8,9}}));
			std::cout << b << "\n";
		 
			std::string c = accumulator(std::vector<std::string>{"hello ","world","!"});
			std::cout << c << "\n";
		 
			return 0;
		}