#### From A to B.

A category theorist might view functions as a transformation from one type to another. For example,*std::to_string : X -> std::string*

would mean that

*to_string*is a function that maps an

*X*to a

*string*.

In "Generic Function Objects", I talked about type constructors.

/* MakeT T : X -> T<X> */ template< template<class...> class T > struct MakeT { template< class ...X, class R = T< typename std::decay<X>::type... > > constexpr R operator () ( X&& ...x ) { return R( std::forward<X>(x)... ); } }; /* pair : X x Y -> std::pair<X,Y> */ constexpr auto pair = MakeT<std::pair>();

I use the notation

*X x Y*to mean that

*MakeT<pair>*takes two arguments. Though, in Haskell, it would actually look like this:

*make_pair :: X -> Y -> (X,Y)*

Haskell uses curried notation.

*g : pair<X,A> -> pair<X,B>*

Here,

*g*is a function that transforms the second element of the

*pair*to a

*B*, but leaves the first as an

*X*. Although this cannot be inferred from the definition, let's assume that the first value (

*X*) is not transformed in any way. There is a function that represents this non-transformation.

/* id : X -> X */ constexpr struct Id { template< class X > constexpr X operator () ( X&& x ) { return std::forward<X>(x); } } id{};

Arrows provide the tools to take a normal function,

*f : A -> B*, and convert it to a function like

*g*. This is sort of like composition

/* compose : (B -> C) x (A -> B) -> (A -> C) */ template< class F, class G > struct Composition { F f; G g; template< class _F, class _G > constexpr Composition( _F&& f, _G&& g ) : f(std::forward<_F>(f)), g(std::forward<_G>(g)) { } template< class X > constexpr auto operator() ( X&& x) -> decltype( f(g(std::declval<X>())) ) { return f( g( std::forward<X>(x) ) ); } }; constexpr auto compose = MakeT<Composition>();

If we look at

*A -> B*as a type itself, say

*AB*, and

*B -> C*as a type,

*BC*, then it is clear that composition is

*BC x AB -> AC*. Functions themselves are values with types and composition creates a new value and type. We can think of them as being on a geometric plain with the points

*A*,

*B*, and

*C*. Functions are connections from point-to-point. Similarly, we can think of

*AB*,

*BC*, and

*AC*as points on a different plain with arrows connecting

*AB*and

*BC*to

*AC*(though

*AB*and

*BC*cannot be connected).

#### Functions as Arrows.

Arrows have several operations. The first is*arr*, which transforms a function to an arrow; but since functions

**are**arrows, it isn't useful, right off the bat.

*first*and

*second*take functions,

*A -> B*, and lift them to pair-oriented functions.

*fan*takes two functions, one

*A -> B*, another

*A -> C*, and returns a function to

*pair<B,C>*.

*split*takes two functions as well,

*A -> B*and

*X -> Y*, and returns a function

*pair<A,X> -> pair<B,Y>*.

*arr : (A -> B) -> (A -> B)*

*first : (A -> B) -> (pair<A,X> -> pair<B,X>)*

*second : (A -> B) -> (pair<X,A> -> pair<X,B>)*

*split : (A -> B) x (X -> Y) -> (pair<A,X> -> pair<B,Y>)*

*fan : (A -> B) x (A -> C) -> (A -> pair<B,C>)*

First, we fill in the declarations.

template< class A, class F, class Arr = Arrow< Cat<A> > > constexpr auto arr( F&& f ) -> decltype( Arr::arr( std::declval<F>() ) ) { return Arr::arr( std::forward<F>(f) ); } template< class A > struct Arr { template< class F > constexpr auto operator () ( F&& f ) -> decltype( arr(std::declval<F>()) ) { return arr( std::forward<F>(f) ); } }; constexpr struct Split { template< class F, class G, class A = Arrow<Cat<F>> > constexpr auto operator () ( F&& f, G&& g ) -> decltype( A::split(std::declval<F>(), std::declval<G>()) ) { return A::split( std::forward<F>(f), std::forward<G>(g) ); } } split{}; constexpr struct Fan { template< class F, class G, class A = Arrow<Cat<F>> > constexpr auto operator () ( F&& f, G&& g ) -> decltype( A::fan(std::declval<F>(),std::declval<G>()) ) { return A::fan( std::forward<F>(f), std::forward<G>(g) ); } } fan{}; constexpr struct First { template< class F, class A = Arrow<Cat<F>> > constexpr auto operator () ( F&& f ) -> decltype( A::first(std::declval<F>()) ) { return A::first( std::forward<F>(f) ); } } first{}; constexpr struct Second { template< class F, class A = Arrow<Cat<F>> > constexpr auto operator () ( F&& f ) -> decltype( A::second(std::declval<F>()) ) { return A::second( std::forward<F>(f) ); } } second{};

*arr*will be trivial to implement, but the others are tricky. Luckily, we can define it mostly in terms of

*split*--it looks like this:

/* pairCompose : (A -> B) x (X -> Y) -> (pair<A,X> -> pair<B,Y>) */ template< class F, class G > struct PairComposition { F f; G g; template< class _F, class _G > constexpr PairComposition( _F&& f, _G&& g ) : f(std::forward<_F>(f)), g(std::forward<_G>(g)) { } template< class P/*air*/ > constexpr auto operator() ( const P& p ) -> decltype( std::make_pair( f(std::get<0>(p)), g(std::get<1>(p)) ) ) { return std::make_pair( f(std::get<0>(p)), g(std::get<1>(p)) ); } }; constexpr auto pairCompose = MakeT<PairComposition>();

*pairCompose*returns a function expecting a

*pair*and returns a

*pair*, threading the first value through

*f*and the second through

*g*. We can compose

*PairCompositions*.

namespace std { std::string to_string( const std::string& s ); template< class X, class Y > std::string to_string( const std::pair<X,Y>& p ); std::string to_string( const std::string& s ) { return "\"" + s + "\""; } template< class X, class Y > std::string to_string( const std::pair<X,Y>& p ) { return "(" + to_string(p.first) + "," + to_string(p.second) + ")"; } } constexpr struct ToString { template< class X > std::string operator () ( const X& x ) const { return std::to_string(x); } } string{}; int main() { using std::cin; using std::cout; using std::endl; auto plus2 = []( int x ){ return x+2; }; std::pair<int,int> p( 1, 1 ); cout << "((+2) . string, (+4))( 1, 1 ) = " << compose( pairCompose(string,plus2), pairCompose(plus2, plus2) )(p) << endl; }

This will output

*("3",5)*. It's easiest to look at this as

*p.first*and

*p.second*being on two separate paths. I have written it such that the individual paths are verticle. The first path starts at

*1*, and goes to

*plus2(1)*, to

*show(plus2(1))*. The second path starts at

*2*and ends at

*plus2(plus2(2))*. The odd part is that we're defining both paths at once.

Observe that

*first(f) = split(f,id)*. Proof?

*first : (A -> B) -> (pair<A,X> -> pair<B,X>)*

*split : (A -> B) x (X -> Y) -> (pair<A,X> -> pair<B,Y>)*

*id : X -> X*

*f : A -> B*

*split(f,id) : pair<A,X> -> pair<B,X>*

Since we know

*first(f) = split(f,id)*, we can intuit that

*second(f) = split(id,f)*and also,

*split(f,g) = compose( first(f), second(g) )*.

*fan*represents a fork in the road. One variable gets fed into two functions, the results of which get zipped into a pair.

*duplicate*will do the splitting, but we'll rely on

*split*to implement

*fan*.

constexpr struct Duplicate { template< class X, class P = std::pair<X,X> > constexpr P operator() ( const X& x ) { return P( x, x ); } } duplicate{};

With this, we can say that

*fan(f,g)(x) = split(f,g)( duplicate(x) )*. Since we know what everything looks like, we can define

*Arrow<F>*.

template< class Func > struct Arrow<Func> { template< class F > static constexpr F arr( F&& f ) { return std::forward<F>(f); } /* split(f,g)(x,y) = { f(x), g(y) } */ template< class F, class G > static constexpr auto split( F f, G g ) -> PairComposition<F,G> { return pairCompose( std::move(f), std::move(g) ); } /* * first(f)(x,y) = { f(x), y } * second(f)(x,y) = { x, f(y) } */ template< class F > static constexpr auto first( F f ) -> decltype( split(std::move(f),id) ) { return split( std::move(f), id ); } template< class F > static constexpr auto second( F f ) -> decltype( split(id,std::move(f)) ) { return split( id, std::move(f) ); } /* fan(f,g)(x) = { f(x), g(x) } */ template< class F, class G > static constexpr auto fan( F f, G g ) -> decltype( compose( split(std::move(f),std::move(g)), duplicate ) ) { return compose( split(std::move(f),std::move(g)), duplicate ); } };

Now, we can rewrite the above example:

int main() { auto plus2 = []( int x ){ return x+2; }; cout << "(+2) *** (+2) >>> string *** (+2) $ 1 = " << compose( split(string, plus2), fan( plus2, plus2) )(1) << endl; }

One way to think of Arrows is as paths.

*fan*represents a fork in the road,

*split*defines two separate, but parallel, paths at once, and

*first*and

*second*allow progress on one of the paths. For an arbitrary example, consider a branching path that hides some treasure. What sequence of moves are required to recover it?

/* * Get 0 : (X,Y) -> X * Get 1 : (X,Y) -> Y */ template< size_t N > struct Get { template< class P > constexpr auto operator () ( P&& p ) -> decltype( std::get<N>(std::declval<P>()) ) { return std::get<N>( std::forward<P>(p) ); } }; int main() { constexpr auto fst = Get<0>(); constexpr auto snd = Get<1>(); constexpr auto oneHundred = []( int x ){ return 100; }; // Hide the hundred. // hidden = pair( pair( 0, pair(100,0) ), 0 ) auto hidden = fan( fan(id,fan(oneHundred,id)), id )( 0 ); // Function to find it again. auto find = compose( fst, compose(snd,fst) ); cout << "I found " << find(hidden) << "!" << endl; }

#### Enter Kleisli.

This all works great for free functions, but some functions look like this:*f : X -> M<Y> -- Where M is some Monad*

*This*

*f*is a member of the Kleisli category. It accepts a normal value and returns a Monadic one. Examples of Kelisli functions (psuedocode):

*Just : X -> unique_ptr<X>*

*Just = MakeT<unique_ptr>();*

*Seq : X -> std::vector<X>*

*Seq(x) = std::vector<X>{x}*

*mreturn<M> : X -> M<X>*

*unique_ptr*s and

*vector*s are monads, so any function that produces one from some

*x*can be considered in the Kleisli category. Though, to the compiler, there's no logic to that, so we define a wrapper type around the function. This is a fairly common pattern, so I define a base class for it.

template< class F > struct Forwarder { using function = typename std::decay<F>::type; function f = F(); template< class ...G > constexpr Forwarder( G&& ...g ) : f( std::forward<G>(g)... ) { } template< class ...X > constexpr auto operator() ( X&& ...x ) -> decltype( f(std::declval<X>()...) ) { return f( std::forward<X>(x)... ); } constexpr operator function () { return f; } };

The Kleisli itself can be implemented two ways. The Haskell way would be something like this:

/* Kleisli M A B : A -> M<B> */ template< template<class...> class M, class A, class B, class F = std::function<M<A>(B)> > struct Kleisli : Forwarder<F> { template< class ...G > constexpr Kleisli( G&& ...g ) : Forwarder<F>(std::forward<G>(g)...) { } };

This is faithful to how Haskell defines it.

*newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b }*

But just think about this for a moment. A Kleisli is an Arrow, right? What would

*Arrow<Kleisli>::first*return?

*first : (A -> B) -> (pair<A,X> -> pair<B,X>)*

*Kleisli f = A -> M<B>*

*first(Kleisli f) : (A -> M B) -> (pair<A,X> -> M pair<B,X>)*

What's the type of

*X*? It's truly impossible to know because it depends on what gets passed in, which is what the notation above means.

Is it impossible to define Kleisli in this way? I don't know. I attempted to specialize its composition function for when

*A*or

*B*were pair types

*,*but there are four combinations of whether

*A*or

*B*or both is a pair. I tried assigning

*X*the type of

*std::placeholders::_1*, but none of my attempts to make it really work compiled. (It was horrible.)

But we don't have

**any**of that trouble if we define Kleisli differently.

#### Kleisli<F>.

/* Kleisli M F : F -- where F : A -> M<B> */ template< template<class...> class M, class F = Id > struct Kleisli : Forwarder<F> { template< class ...G > constexpr Kleisli( G&& ...g ) : Forwarder<F>(std::forward<G>(g)...) { } };

An implicit requirement of arrows is that they can be composed, but Kleislies?

*compseKleisli : Kleisli(B -> M<C>) x*

*Kleisli*(A -> M<B>) -> (...?)We can reasonably assume that it should be

*Kleisli(A -> M<C>*), but our naive definition of composition must be specialized. Literally.

/* Composition : Kleisli(B -> M<C>) x Kleisli(A -> M<B>) -> (A -> M<C>) */ template< template<class...> class M, class F, class G > struct Composition<Kleisli<M,F>,Kleisli<M,G>> { Kleisli<M,F> f; Kleisli<M,G> g; template< class _F, class _G > constexpr Composition( _F&& f, _G&& g ) : f(std::forward<_F>(f)), g(std::forward<_G>(g)) { } template< class X > constexpr auto operator() ( X&& x ) -> decltype( g(std::forward<X>(x)) >>= f ) { return g(std::forward<X>(x)) >>= f; } }; /* kcompose : Kleisli(B -> M<C>) x Kleisli(A -> M<B>) -> Kleisli(A -> M<C>) */ constexpr struct KCompose { template< template<class...> class M, class F, class G > constexpr auto operator () ( Kleisli<M,F> f, Kleisli<M,G> g ) -> Kleisli< M, Composition<Kleisli<M,F>,Kleisli<M,G> > { return kleisli<M> ( compose( std::move(f), std::move(g) ) ); } } kcompose{}; int main() { auto stars = kleisli<std::basic_string> ( [] (char c) -> std::string { return c == '*' ? "++" : c == '+' ? "* *" : std::string{c}; } ); auto starsSqr = kcompose( stars, stars ); auto starsCube = kcompose( starsSqr, stars ); cout << "stars of '*' : " << stars('*') << endl; cout << "stars^2 of '*' : " << starsSqr('*') << endl; cout << "stars^3 of '*' : " << starsCube('*') << endl; }

This outputs

*stars of '*' : "++"*

stars^2 of '*' : "* ** *"

stars^3 of '*' : "++ ++++ ++"

stars^2 of '*' : "* ** *"

stars^3 of '*' : "++ ++++ ++"

Like before, it would be most convenient to define

*Arrow<Kleisli>*in terms of

*split*.

*split(f,g)*, given the pair

*{x,y}*, will have to pass

*x*into

*f*and

*y*into

*g*, both of which will return Monadic values. Finally, a

*pair*will have to be constructed from the values extracted from

*f(x)*and

*g(y)*.

*split: Kleisli (A -> M B) x Kleisli (X -> M Y) -> Kleisli (pair<A,X> -> M pair<B,Y>)*

To extract the values from

*f(x)*and

*g(y)*, we need to call

*mbind*on each, which in Haskell might look like this:

*f(x) >>= (\x' -> g(y) >>= (\y' -> return (x,y)))*

Or,

*Control.Monad*defines

*liftM*.

*liftM2 (,) f(x) g(y) -- where (,) is equivalent to make_pair*

template< class M > struct Return { template< class X > constexpr auto operator () ( X&& x ) -> decltype( mreturn<M>(std::declval<X>()) ) { return mreturn<M>( std::forward<X>(x) ); } }; /* * liftM : (A -> B) x M<A> -> M<B> * liftM : (A x B -> C) x M<A> x M<B> -> M<C> */ constexpr struct LiftM { template< class F, class M, class R = Return<typename std::decay<M>::type> > constexpr auto operator () ( F&& f, M&& m ) -> decltype( std::declval<M>() >>= compose(R(),std::declval<F>()) ) { return std::forward<M>(m) >>= compose( R(), std::forward<F>(f) ); } template< class F, class A, class B > constexpr auto operator () ( F&& f, A&& a, B&& b ) -> decltype( std::declval<A>() >>= compose ( rcloset( LiftM(), std::declval<B>() ), closet(closet,std::declval<F>()) ) ) { return std::forward<A>(a) >>= compose ( rcloset( LiftM(), std::forward<B>(b) ), closet(closet,std::forward<F>(f)) ); } } liftM{};

It acts basically as a n-ary

*mbind*, though one could also define an n-ary

*mbind*!

*liftM*works even if you don't.

Finally, we have all the pieces in place to implement

*KleisliSplit*.

/* kleisliSplit : Kleisli(A -> M<B>) x Kleisli(X -> M<Y>) -> (piar<A,X> -> M<pair<B,Y>>) */ template< template<class...> class M, class F, class G > struct KleisliSplit { F f; G g; constexpr KleisliSplit( F f, G g ) : f(std::move(f)), g(std::move(g)) { } template< class X, class Y > constexpr auto operator () ( const std::pair<X,Y>& p ) -> decltype( liftM(pair,f(std::get<0>(p)),g(std::get<1>(p))) ) { return liftM ( pair, f( std::get<0>(p) ), g( std::get<1>(p) ) ); } };

The final note before moving on:

*arr*. Kleisli's

*arr*is like a Monad's

*mreturn*.

*arr : (A -> B) -> Kleisli(A -> M<B>)*

*arr(f)(x) = mreturn<M>( f(x) )*

or:

*arr = liftM*

template< template<class...> class M, class F > struct Arrow< Kleisli<M,F> > { template< class G > using K = Kleisli<M,G>; template< class G > static constexpr auto arr( G g ) -> Kleisli< M, Part<LiftM,G> > { return kleisli<M>( closet(liftM,std::move(g)) ); } template< class G > static constexpr auto first( G g ) -> K<decltype( ::split(std::move(g),arr(id)) )> { // id is not a Kleisli. // The call to arr refers to the arr above, not ::arr. // arr(id) : Kleisli(X -> M<X>) return ::split( std::move(g), arr(id) ); } template< class G > static constexpr auto second( G g) -> K<decltype( ::split(arr(id),std::move(g)) )> { return ::split( arr(id), std::move(g) ); } template< class G > static constexpr auto split( Kleisli<M,F> f, Kleisli<M,G> g ) -> K< KleisliSplit<M,F,G> > { return KleisliSplit<M,F,G>( std::move(f.f), std::move(g.f) ); } template< class _F, class _G > static constexpr auto fan( _F&& f, _G&& g ) -> decltype( kcompose(split(std::declval<_F>(),std::declval<_G>()),arr(duplicate)) ) { return kcompose( split(std::forward<_F>(f),std::forward<_G>(g)), arr(duplicate) ); } }; int main() { auto stars = kleisli<std::vector> ( [] (char c) { return c == '*' ? std::vector<char>{'+','+'} : c == '+' ? std::vector<char>{'*',' ','*'} : std::vector<char>{c}; } ); auto hairs = kleisli<std::vector> ( [] (char c) -> std::vector<char> { return c == '*' ? std::vector<char>{'\'','"','\''} : c == '+' ? std::vector<char>{'"',' ','"'} : c == '"' ? std::vector<char>{'\''} : c == '\'' ? std::vector<char>{} : std::vector<char>{c}; } ); cout << "hairs of '*' : " << hairs('*') << endl; cout << "hairs^2 of '*' : " << compose(hairs,hairs)('*') << endl; cout << "split(stars,hairs) (*,*) = " << split(stars,hairs)(pair('*','*')) << endl; cout << "fan(stars,hairs) (*) = " << fan(stars,hairs)('*') << endl; cout << "fan(hairs,stars) (*) = " << fan(hairs,stars)('*') << endl; cout << "split(hairs,stars) . fan(stars,hairs) = " << compose( split(hairs,stars), fan(stars,hairs) )('*') << endl; }Finally, this outputs

*hairs of '*' : [',",']*

hairs^2 of '*' : [']

split(stars,hairs) (*,*) = [(+,'),(+,"),(+,'),(+,'),(+,"),(+,')]

fan(stars,hairs) (*) = [(+,'),(+,"),(+,'),(+,'),(+,"),(+,')]

fan(hairs,stars) (*) = [(',+),(',+),(",+),(",+),(',+),(',+)]

split(hairs,stars) . fan(stars,hairs) = [(",'),( ,'),(",'),(","),( ,"),(","),(",'),( ,'),(",'),(",'),( ,'),(",'),(","),( ,"),(","),(",'),( ,'),(",')]

hairs^2 of '*' : [']

split(stars,hairs) (*,*) = [(+,'),(+,"),(+,'),(+,'),(+,"),(+,')]

fan(stars,hairs) (*) = [(+,'),(+,"),(+,'),(+,'),(+,"),(+,')]

fan(hairs,stars) (*) = [(',+),(',+),(",+),(",+),(',+),(',+)]

split(hairs,stars) . fan(stars,hairs) = [(",'),( ,'),(",'),(","),( ,"),(","),(",'),( ,'),(",'),(",'),( ,'),(",'),(","),( ,"),(","),(",'),( ,'),(",')]

#### Extras -- Convenience and Pitfalls.

Perhaps the most important parts of*Control.Arrow*are here, but there are still a few things that can be added. For example,

*compose*is backwards!

*compose(f,g)*means

*"do g, then do f."*Because of this we have to read it backwards.

*fomp*is useful, if only because we read left-to-right, not the other way around.

/* fcomp : (A -> B) x (B -> C) -> (A -> C) */ constexpr struct FComp { template< class G, class F, class C = Composition<F,G> > constexpr C operator () ( G g, F f ) { return C(std::move(f),std::move(g)); } } fcomp{};

Another tool is

*precompose*and

*postcompose*. Perhaps one wants to compose something that is not a Kleisli with something that is.

/* prefcomp : (A -> B) x (Arrow X Y) -> Arrow A Y */ constexpr struct PreFComp { template< class F, class A > constexpr auto operator () ( F&& f, A&& a ) -> decltype( arr<A>(declval<F>()) > declval<A>() ) { return arr<A>(forward<F>(f)) > forward<A>(a); } } prefcomp{}; /* postfcomp : Arrow A B x (X -> Y) -> Arrow A Y */ constexpr struct PostFComp { template< class A, class F > constexpr auto operator () ( A&& a, F&& f ) -> decltype( declval<A>() > arr<A>(declval<F>()) ) { return forward<A>(a) > arr<A>(forward<F>(f)); } } postfcomp{};

Beyond that, there's

*ArrowZero*and

*ArrowPlus*to work with Monoids,

*ArrowChoice*based on

*Either*,

*ArrowApply*and

*ArrowLoop*.

*ArrowZero*, defining

*zeroArrow*, shows the downside to implementing Kleisli as

*K<M,F>*instead of

*K<M,A,B>*. It is defined like so:

*zeroArrow = Kleisli (\_ -> mzero)*

The type

*mzero*needs to return is

*M<B>*. Its argument, the

*_*, will be of type

*A*. So we have this problem where

*zeroArrow(k)*(for some Kleisli,

*k*) doesn't know what type to return and can't deduce it!

If we had implemented Kleisli with

*A*and

*B*, this would be no problem, but then it would have been impossible(?) to implement

*Arrow<Kleisli>::first*. In Haskell, all functions carry around information about their domain and codomain, so there is no difference between passing around

*A*and

*B*or just

*F*.

The easiest solution is to diverge from Haskell's definition and require

*zeroArrow*to take an explicit result-type parameter.

#### Conclusions.

Arrows let us do interesting types of composition that one would not normally likely think of. They fall somewhere between Functors and Monads (this article has a graph). My Monadic parser could have also been written with Arrows.I realize this has been a

*very*long post. Hopefully all the code examples work, there are no inaccuracies, and it is understandable, but with an article this large,

*some*thing has probably been fudged. Due to the large amount of material, it may be a good idea to split this article up and go more in depth. Please speak up if something seems off.

**Source code:**https://gist.github.com/4176121

**Haskell reference:**Control.Arrow