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 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.
And now, a few examples:
And that's input. We'll have to specialize IO for output.
Now, let's try and imagine some operation on IO.
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.
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 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.
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.
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.
We may now implement Functor<IO> and Monad<IO> totally in terms of Identity, Incidence, and DoubleCall.
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 read to work on any type. Even better, we can make read a type!
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.
Now, we want to turn a show/Print combo into an IO. I'll be borrowing my code from "Partial Application in C++" for this.
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.
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/Print combo into an 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 program is a complex data structure that contains many Incidences made of PartialApplications of Print and 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 Prints and std::strings. GCC optimizes away the 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 std::strings. 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 std::function: https://gist.github.com/3994038#file_io_monad.cpp
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 std::function: https://gist.github.com/3994038#file_io_monad.cpp
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.