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_ptrs and vectors 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 '*' : "++ ++++ ++"
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 outputshairs of '*' : [',",']
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, something 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
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.