# Harder to C++: Monads for Mortals [3], Lazy implementation

This blog post is part 3 in a series. This part presents a simple implementation of a lazy evaluating monad. It is a minimal variation of the implementation in part 2.

Below we will see how the implementation is constructed, then an example is given that provides initial verification that the construction is indeed a monad.

## Implementation of a Lazy Monad

Implementation starts again with some includes and a using statement. The first important construct is the monad *type constructor*, a C++ template which in this particular case takes the form of a std::function template:

// Monad type constructor: a std::function template template<typename T> using monad = function < T() >;

The using statement defines ‘monad’ as a type alias.

Of course, a suitably formed pointer to function object would suffice as well. The std::function template has the advantage that it looks neat, and we can instantiate it in an elegant way using a lambda expression. Thus upholding some of the functional character of the monad’s roots.

The unit function, which creates instances of the ‘monadic’ function object is as follows:

// Monad unit function, wraps a value in a lambda template<typename V> monad<V> unit(V val) { return[=](){ return val; }; }

The unit function returns a lambda expression the returns a value, when executed (later some time, if any).

The bind function follows the description of bind operators to the letter. It evaluates the monad argument, and returns a function that applies the function argument to the result of that evaluation:

// Monad bind operator template<typename A, typename R> monad<R> operator|(monad<A>& mnd, monad<R>(*func)(A)) { // return a callable to evaluate later return[=]() { A unwrapped = mnd(); monad<R> result = func(unwrapped); return result(); //parentheses, because we define a function that returns a value }; }

The returned function is *not* evaluated before function call is applied to it. Hence using this bind operator we can construct long and complex function compositions, which get evaluated only after we explicitly do so.

The above triple is the complete implementation of the monad. Yes I know, there should be two additional operations defined as well: the *sequencing* operator and the *fail* operator (see e.g. Mike Vanier, part 3. However, many texts discussing monads indicate that these operations are uninteresting. So, we will skip them in this series.

Let’s add the same functions as in part 2, and run a simple composition:

// divides arg by 2 and returns result as monadic template monad<int> divideby2(int i) { return unit<int>(i / 2); } // checks if arg is even and returns result as monadic template monad<bool> even(int i) { return unit<bool>(i % 2 == 0); } int _tmain(int argc, _TCHAR* argv[]) { SetConsoleTitle(L"Harder to C++: Monads [3]"); // Wrap 22 in monadic template auto m1 = unit<int>(22); // Apply bind 4 times in function composition auto m2 = m1 | divideby2 | divideby2 | divideby2 | even; cout << boolalpha << m2() << endl; cin.get(); return 0; }

Note that the functions ‘divideby2’ and ‘even’ have not changed. The only change in the _*tmain* function is that in the output statement *m2.value* has been replaced by *m2()*. Note the parentheses, which denote lazy evaluation of the constructed composition.

## Minimal Verification that Monadic Laws Hold

The minimal verification is the lazy analog to verification in the eager case. It looks like this:

int _tmain(int argc, _TCHAR* argv[]) { SetConsoleTitle(L"Harder to C++: Monads [3]"); // Wrap 22 in monadic template auto m1 = unit<int>(22); // Left identity // First explicitly convert to function pointer (because of template) auto pf1 = &unit < int >; // then apply bind operator auto m2 = m1 | pf1; cout << "Left Identity result: " << m2() << endl; // Right identity auto m3 = m1 | divideby2; auto m4 = divideby2(22); cout << boolalpha << "Right Identity result : " << (m3() == m4()) << endl; // Associativity // Case 1: equivalent to bind(m1, divideby2);bind(m5, even) auto m5 = m1 | divideby2; auto m6 = m5 | even; // Case 2: equivalent to Bind(m1, divideby2;bind(..., even)); // Create function composition auto f = [](int i){ return divideby2(i) | even; }; // Explicitly convert f to function pointer auto pf2 = static_cast<monad<bool>(*)(int)>(f); auto m7 = m1 | pf2; cout << boolalpha << "Associativity result : " << (m6() == m7()) << endl; cin.get(); return 0; }

which generates output:

## Pros, Cons

Some texts declare that lazy implementation provides advantages over eager or strict evaluation. Advantages presented are:

- Calculations are only made when required and in as far as required.
- ‘Lazy’ allows he evaluation of lists that are unbounded (endless, infinite)
- Delayed evaluation of function compositions allows for an optimization before evaluation of the composition takes place.

What to think of this?

The first advantage strikes me as odd; I usually do not write programs that make calculations which’ results are not required.

The second advantage is odd as well. My computer is as powerful as a Turing machine, hence it can process input lists of unboundedly length. Without lazy evaluation.

The third advantage could be a real advantage, but I wouldn’t know how to do this in C++; the advantage presupposes that it is possible to create code at runtime and then compile and execute it, which isn’t true for C++.

I do see a disadvantage, though, and we will get to it in detail when doing some shootouts between the various alternative monad implementations. The disadvantage is that the software does extra work. It first creates an expression, then evaluates it. So in C++, for each lazy evaluating program, there is an equivalent eager evaluating program that is faster and smaller, hence more competitive.

In the next part of this series we will work on an (eager) implementation that has the same time performance characteristics for any size value. There will be many references and move semantics. Hmm … mjummy 😉

[…] Harder to C++: Monads for Mortals [3], Lazy implementation […]

[…] Harder to C++: Monads for Mortals [3], Lazy implementation […]

[…] Harder to C++: Monads for Mortals [3], Lazy implementation […]