*fmap*)

*,*and Monads (

*mbind, mreturn*), and today, IO. Whether or not monadic IO is desirable in C++, I cannot say. But it represents a significantly more difficult monad to conceptualize and implement, and many of Haskell's monads are similar (StateT, Reader, etc.), so if nothing else, this is good practice. It's also good practice for implementing contiuations.

I neglected (by mistake) to discuss Monads in full, mainly

*do*and

*fail*. In Haskell,

*fail*takes a string, some error message, and returns a failure which, for a pointer, might be null, for a sequence, an empty one. More useful today will be

*do*. Since this should have been in the Monads article, I will explain that first, and then how it's relevant to IO.

*do*simply takes two monads and returns the second. It's symbolically noted

*>>*like

*bind's >>=*. If integers were monads, 1 >> 2 would equal 2. For pointers

*p*and

*q*,

*p >> q*would equal

*q*, but only if

*p*. By that, I mean if

*p = null*, then

*p >> q = null.*If

*q*is null, then

*p >> q*is null regardless. For sequences, Haskell defines

*s >> t*as

*t*appended to itself for every element of

*s*.

*[*

*a,b] >> [x,y] = [x,y,x,y]*

*[a] >> [x,y] = [x,y]*

*[] >> [x,y] = []*

*It should be fairly intuitive how to write this, so I will continue to IO.*

#### IO<X>

So far, we have always made a few implicit assumption about monads. They hold a value and exactly the type in the angle-brackets. In a functional sense, input is a mechanism that somehow produces a value, but it comes out of thin air from some unseen external force. Output is a device that makes seen values disappear. An

*IO*is either a value-producing machine, or a value-taking one. So an*IO*monad is a function! A function with*IO*decoration, that is.
What does an

So Monads aren't just containers. One might have heard they are also computations. That's just an obfuscated way of saying they're functions.

And now, a few examples:

And that's input. We'll have to specialize

Now, let's try and imagine some operation on IO.

I wanted to go over

*IO<int>*contain? It must contain a function that produces an int!*IO<void>*? A function that outputs some value. But since it's actually a function, wouldn't it be more like*IO<int(*)()>*? Or*IO<MyFuncType>*? Well, the IO monad can be implemented with*std::function*, and that allows us to keep our assertions about monadic types, as you will soon see.So Monads aren't just containers. One might have heard they are also computations. That's just an obfuscated way of saying they're functions.

#### Hello World

Let's first define

*IO<X>*as an object holding an*std::function*.template< class X > struct IO { using function = std::function<X()>; function f; template< class F > IO( F&& f ) : f(std::forward<F>(f)) { } X operator () () const { return f(); } }; template< class F, class R = typename std::result_of<F()>::type > IO<R> io( F f ) { return IO<R>( std::move(f) ); }

And now, a few examples:

IO<int> readInt = io( []{ int x; std::cin >> x; return x; } ); IO<std::string> readStr = io( []{ std::string s; std::cin >> s; return s; } ); IO<int> constant = io( []{ return 5; } );

And that's input. We'll have to specialize

*IO*for output.

template< > struct IO<void> { using function = std::function<void()>; function f; IO( function f ) : f(std::move(f)) { } void operator () () const { f(); } }; IO<void> hello = io( []{ std::cout << "Hello world." << std::endl; } ); IO<void> doNothing = io( []{} );

Now, let's try and imagine some operation on IO.

IO<void> hello2 = hello >> hello

*do*is a lot like

*bind*, except that it does not pass the result of the previous expression to the next. When we

*do*two

*IO*monads, we get a third back. No

*IO*has yet been executed.

*hello2*is the function that actually executes the

*IO*.

I wanted to go over

*IO<X>*because it is easier to reason about than

*IO<F>*, and much more Haskell-like. However, C++ is about zero-overhead abstractions and this ends up being less efficient because of the tricks

*std::function*uses in order to work. To see the

*std::function*implementation, check out the gist.

#### IO<F>

This version is initially much simpler to implement.

template< class F > struct IO { using function = F; F f; constexpr IO( function f ) : f(std::move(f)) { } constexpr decltype(f()) operator () () { return f(); } }; template< class F, class _F = typename std::decay<F>::type > constexpr IO<_F> io( F&& f ) { return std::forward<F>(f); }

But now what should the type of

What will

It may make more sense to have

Now we can write things like:

This part might be a little mind boggling. Let's say we call

We may now implement

*hello2*be? Well, it'll basically be executing*hello*, twice, so it's a sort of composition, but with two void functions. Let's define a type to represent this composition:*Incidence*.template< class F, class G > struct Incidence { F a; G b; constexpr Incidence( F a, G b ) : a(std::move(a)), b(std::move(b)) { }&; // Execute a and b coincidentally. auto operator () () const -> typename std::result_of<G()>::type { a(); return b(); } }; template< class F, class G, class I = Incidence<F,G> > constexpr I incidence( F f, G g ) { return I( std::move(f), std::move(g) ); }

What will

*mreturn*do? An*IO*is just a function, so it'll take some*x*and make a function that just returns*x*. To do this, we'll define another type,*Identity*.template< class X > struct Identity { using value_type = X; value_type x; template< class Y > Identity( Y&& y ) : x( std::forward<Y>(y) ) { } constexpr value_type operator () () { return x; } }; template< class X, class D = typename std::decay<X>::type > Identity<D> identity( X&& x ) { return Identity<D>( std::forward<X>(x) ); }

It may make more sense to have

*Identity*return a reference or const reference to

*x*, but since we are dealing strictly with values, this would complicate things. Any

*decltype*or

*result_of*involving an

*Identity*would have to remove the reference.

Now we can write things like:

*auto getFive = mreturn<IO>( 5 );*

*int five = getFive();*

*and all is good. Next is*

*mbind*.

*auto someIO = readInt >>= []( int x ) { return mreturn<IO>(x + 5); }*

*Here, we have our*

*IO*called

*readInt*which gets an

*int*from

*std::cin.*It passes the

*int*to our lambda, which adds

*5*and returns a new

*IO*. No integer has been read from

*std::cin*yet, nor the five added; we have merely composed

*readInt*with our continuation to create a new function, a new

*IO*.

This part might be a little mind boggling. Let's say we call

*someIO*; what happens? We know it'll return an

*int*with

*5*added to it. It starts by calling

*readInt*. Then the number gets passed to our lambda. It adds five and returns a new

*IO*<

*Identity<int>>.*If we stopped here, we wouldn't have our value, so we then execute the

*Identity*

*IO*. We'll implement

*DoubleCall*to express the pattern of constructing the

*IO*with the first call and running it with the second. We'll also expand

*Incidence*to handle the case where it needs to pass the value (from

*readInt*) to the continuation.

template< class T, class R > using EVoid = typename std::enable_if< std::is_void<T>::value, R >::type; template< class T, class R > using XVoid = typename std::enable_if< !std::is_void<T>::value, R >::type; // Incidental. template< class F, class G, class R = typename std::result_of<F()>::type > constexpr auto incidentallyDo( F&& f, G&& g ) -> XVoid < R, decltype( std::declval<G>()( std::declval<F>()() ) ) > { return std::forward<G>(g)( std::forward<F>(f)() ); } // Co-incidental. template< class F, class G, class R = typename std::result_of<F()>::type > constexpr auto incidentallyDo( F&& f, G&& g ) -> EVoid < R, decltype( std::declval<G>()() ) > { std::forward<F>(f)(); return std::forward<G>(g)(); } // Either an incidence or coincidence. template< class F, class G > struct Incidence { F a; G b; constexpr Incidence( F a, G b ) : a(std::move(a)), b(std::move(b)) { } using R = decltype( incidentallyDo(a,b) ); constexpr R operator () () { return incidentallyDo( a, b ); } }; template< class F, class G, class I = Incidence<F,G> > constexpr I incidence( F f, G g ) { return I( std::move(f), std::move(g) ); } template< class F > struct DoubleCall { F f; using F2 = typename std::result_of<F()>::type; using result_type = typename std::result_of<F2()>::type; constexpr result_type operator () () { return f()(); } }; template< class F > constexpr DoubleCall<F> doubleCall( F f ) { return { std::move(f) }; }

We may now implement

*Functor<IO>*and

*Monad<IO>*totally in terms of

*Identity*,

*Incidence,*and

*DoubleCall*.

template< class _ > struct Functor< IO<_> > { template< class F, class G, class I = Incidence<F,G> > constexpr static IO<I> fmap( F f, IO<G> r ) { return I( std::move(f), std::move(r.f) ); } }; template< class _ > struct Monad< IO<_> > { template< class F, class G, class R = typename std::result_of<G()>::type > static constexpr auto mbind( F f, IO<G> m ) -> IO< DoubleCall< Incidence<G,F> > > { // f returns a new IO, so doubleCall the incidence to execute it! return doubleCall ( incidence( std::move(m.f), std::move(f) ) ); } template< class F, class G > static constexpr IO<Incidence<F,G>> mdo( IO<F> f, IO<G> g ) { return incidence( std::move(f.f), std::move(g.f) ); } template< class __, class X, class D = typename std::decay<X>::type > static constexpr IO<Identity<D>> mreturn( X&& x ) { return Identity<D>( std::forward<X>(x) ); } template< class _IO > static _IO mfail() { return _IO( []{ } ); } };

Now, we can string along arbitrary operations in whatever way we'd like, but a sane person might realize that if one lambda reads in an int and another prints it, then we've really just obfuscated this process because we could otherwise we could just do that ourselves. Like any other useful thing,

*IO*requires other useful things to make it useful.

#### The tools

First, input. We could write a function that read an int and returned it and it would look something like this:

*int readInt() { int x; std::cin >> x; return x; }*

Or, we can template

We can read; can we write? Since an

Now, we want to turn a*Print*combo into an

We can now write rudimentary

*read*to work on any type. Even better, we can make*read*a type!template< class T > struct ReadT { T operator () () const { T x; std::cin >> x; return x; } }; template< class T > constexpr IO< ReadT<T> > readT() { return ReadT<T>(); }

We can read; can we write? Since an

*IO*takes no arguments, anything we want to write has to be held within the*IO*object. First, we just need some generic functions.constexpr struct Print { template< class X > void operator () ( const X& x ) const { std::cout << x; } } print{}; template< class X > static std::string show( const X& x ) { static std::ostringstream oss; oss.str( "" ); oss << x; return oss.str(); } static std::string show( std::string str ) { return str; } static constexpr const char* show( const char* str ) { return str; } template< class X, class Y, class ...Z > static std::string show( const X& x, const Y& y, const Z& ...z ) { return show(x) + show(y,z...); }

Now, we want to turn a

*show*/*IO*. I'll be borrowing my code from*"Partial Application in C++"*for this.constexpr struct Echo { using F = PartialApplication< Print, std::string >; using result_type = IO<F>; template< class ...X > result_type operator () ( const X& ...x ) const { // We don't know if x will still be around when the IO executes, so // convert to a string right away! return closet( print, show(x...) ); } } echo{}; auto newline = io( []{ std::cout << std::endl; } );

We can now write rudimentary

*IO*programs like*echo("Give me an int!\n") >> (readT<int>() >>= echo) >> newline**Which will, if you've been following along, echo*

*"Give me an int!"*to the screen, read one from*std::cin*, and echo the int back out.#### Complications

Remember

*addM*?template< class M > M addM( const M& a, const M& b ) { return mbind ( [&]( int x ) { return mbind ( [=]( int y ) { return mreturn<M>(x+y); }, b ); }, a ); }

For

*IO*, this should read in two ints and add them, but it won't work since

*IO<F> >>= []{...} =/= IO<F>*! We could wrap the function in a

*decltype,*but not while using lambdas. The challenge is to rewrite this function without lambdas.Looking at the lambda, it takes only one argument, but also captures

*b*. We can replace it with a function that takes

*f, b,*and

*x*

*. x*has to be the last argument because we're going to partially apply

*f*and

*b,*making it a function of

*x*.

template< class M > struct _AddM { constexpr auto operator () ( int x, int y ) -> decltype( mreturn<M>(1) ) { return mreturn<M>( x + y ); } }; constexpr struct BindCloset { template< class F, class X, class M > constexpr auto operator () ( F&& f, M&& m, X&& x ) -> decltype( std::declval<M>() >>= closet(std::declval<F>(),std::declval<X>()) ) { return std::forward<M>(m) >>= closet( std::forward<F>(f), std::forward<X>(x) ); } } bindCloset{}; template< class M > constexpr auto addM( const M& a, const M& b ) -> decltype ( a >>= closure( bindCloset, _AddM<M>(), b ) ) { return a >>= closure( bindCloset, _AddM<M>(), b ); }

When we bind

*a*to the closure,

*x*gets extracted as the last argument. The closure then partially applies

*x*to

*f*and extracts

*y*from

*b*.

The same technique can be used to implement

*liftM*, the two-argument version, or any other function with embedded lambdas.

#### Conclusions

How powerful is this? We can write almost a whole program in it! Here's the

*main*I used to test*IO*(using some code from the*Monads*article).int main() { std::unique_ptr<int> p( new int(5) ); auto f = []( int x ) { return Just(-x); }; std::unique_ptr<int> q = mbind( f, p ); std::vector<int> v={1,2,3}, w={3,4}; auto readInt = readT<int>(); auto program = echo( "Unique pairs of [1,2,3]:\n\t" ) >> echo( uniquePairs(v) ) >> newline >> echo("Unique pairs of Just 5:\n\t") >> echo( uniquePairs(p) ) >> newline >> echo( "Please enter two numbers, x and y: " ) >> ( addM( readInt, readInt ) >>= []( int x ) { return echo( "x+y = ", x ) >> newline; } ) >> echo("The quadratic root of (1,3,-4) = ") >> echo( qroot(1,3,-4) ) >> newline >> echo("The quadratic root of (1,0,4) = ") >> echo( qroot(1,0,4) ) >> newline; program(); }

The variable *Print*and*Print*s and*Print*object and inlines much of the code, which it could not do if it were a regular function (since it would have to maintain a pointer), but it wouldn't ordinarily construct this many

Would one ever want to actually use this over vanilla IO in C++? I certainly wouldn't argue it should be prefered. Still, if one was in the situation of needing to pass along a function, this offers a simple way of composing it from simpler objects. Composition itself is a powerful tool.

At first, we may have thought of a monad or functor as a container, but

*program*is a complex data structure that contains many*Incidence*s made of*PartialApplication*s of*std::string*. GCC does a very good job of optimizing it, however, if we had written this out normally (no monads), GCC would just insert each item into*std::cout.*Instead we're creating a structure with*std::string*s. GCC optimizes away the*std::string*s. There is room for optimization--this is not hopelessly inefficient, but be aware of how your objects are constructed and passed along.Would one ever want to actually use this over vanilla IO in C++? I certainly wouldn't argue it should be prefered. Still, if one was in the situation of needing to pass along a function, this offers a simple way of composing it from simpler objects. Composition itself is a powerful tool.

At first, we may have thought of a monad or functor as a container, but

*IO*disproves this. So monads can be containers**or**functions?*IO*is more than just a function, it's a program encoded as data, constructed at run-time. It's hard to point to one sentence that well-describes all monads, but we know they aren't one exact thing over another. It's almost anything!**As always, the source code:**https://gist.github.com/3994038**IO implemented with**https://gist.github.com/3994038#file_io_monad.cpp*std::function*:
## No comments:

## Post a Comment

Please feel free to post any comments, concerns, questions, thoughts and ideas. I am perhaps more interested in what you have to say than you are in what I do.