Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Several of Haskell's Data.List functions implemented in C++ Data.List: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>
template< class F, class X, class S >
constexpr X foldl( F&& f, X x, const S& s ) {
return std::accumulate (
std::begin(s), std::end(s),
std::move(x), std::forward<F>(f)
);
}
// A function wrapper that flips the argument order.
template< class F > struct Flip {
F f = F();
constexpr Flip( F f ) : f(std::move(f)) { }
template< class X, class Y >
constexpr auto operator () ( X&& x, Y&& y )
-> typename std::result_of< F(Y,X) >::type
{
return f( std::forward<Y>(y), std::forward<X>(x) );
}
};
template< class F, class Flip = Flip<F> >
Flip flip( F f ) {
return Flip( std::move(f) );
}
template< class F, class X, class S >
constexpr X foldr( F&& f, X x, const S& s ) {
using It = decltype(std::begin(s));
using RIt = std::reverse_iterator<It>;
return std::accumulate (
// Just foldl in reverse.
RIt(std::end(s)), RIt(std::begin(s)),
std::move(x),
// std::acc expects f(acc,si), but f is f(si,acc).
Flip<F>(std::forward<F>(f))
);
}
#include <forward_list>
template< class F, template<class...>class S, class X, class Y,
class Res = typename std::result_of< F(X,Y) >::type >
S<Res> zipWith( F&& f, const S<X>& v, const S<Y>& w ) {
S<Res> r;
std::transform( std::begin(v), std::end(v),
std::begin(w),
std::back_inserter(r),
std::forward<F>(f) );
return r;
}
template< class F, template<class...>class S, class X,
class Res = typename std::result_of< F(X) >::type >
S<Res> map( const F& f, const S<X>& s ) {
S<Res> r;
std::transform( std::begin(s), std::end(s),
std::back_inserter(r),
std::forward<F>(f) );
return r;
}
template< class F, template<class...>class S, class X, class Y,
class Res = typename std::result_of< F(X,Y) >::type >
S<Res> map( const F& f, const S<X>& xs, const S<Y>& ys ) {
S<Res> r;
for( const X& x : xs )
for( const Y& y : ys )
r.emplace_back( f(x,y) );
return r;
}
template< class P, class S >
S filter( const P& p, S s ) {
using F = std::function< bool(typename S::value_type) >;
s.erase (
std::remove_if( std::begin(s), std::end(s), std::not1(F(p)) ),
std::end(s)
);
return s;
}
// For each x in s, returns pair( p(x), not p(x) ).
template< class P, class S >
std::pair<S,S> partition( const P& p, const S& s ) {
using F = std::function< bool(typename S::value_type) >;
// There does exist std::partition_copy,
// however this function demonstrates a use of filter.
return std::make_pair (
filter( p, s ),
filter( std::not1(F(p)), s )
);
}
// Fake Quick-Sort: A non-in-place qsort-inspired function.
template< class S >
S fake_qsort( S s ) {
using X = typename S::value_type;
if( s.size() < 2 )
return s;
X pivot = s.back();
s.pop_back();
S low, high;
std::tie(low,high) = partition (
[&]( const X& x ) { return x <= pivot; },
s
);
low = fake_qsort( std::move(low) );
low.push_back( pivot );
// Append the sorted high to the sorted low.
high = fake_qsort( std::move(high) );
std::move( std::begin(high), std::end(high),
std::back_inserter(low) );
return low;
}
template< class S, class _X = decltype( *std::begin(std::declval<S>()) ),
class X = typename std::decay<_X>::type >
std::vector<X> take( size_t n, const S& s ) {
std::vector<X> r;
std::copy_n( std::begin(s), n, std::back_inserter(r) );
return r;
}
// Predicate version
template< class P, class S,
class _X = decltype( *std::begin(std::declval<S>()) ),
class X = typename std::decay<_X>::type >
std::vector<X> takeWhile( const P& p, const S& s ) {
std::vector<X> r;
std::copy( std::begin(s),
std::find_if_not( std::begin(s), std::end(s), p ),
std::back_inserter(r) );
return r;
}
#include <boost/range/irange.hpp>
void euler1() {
// multiples of...
auto two = boost::irange( 3, 1001, 3 );
auto five = boost::irange( 5, 1001, 5 );
// Ensure that the final sum has no duplicates.
std::vector<int> all;
std::set_union( std::begin(two), std::end(two),
std::begin(five), std::end(five),
std::back_inserter(all) );
std::cout << "Every multiple of 3 or 5 bellow 1000 :"
<< std::accumulate( std::begin(all), std::end(all), 0 )
<< std::endl;
}
template< class S >
S drop( size_t n, const S& s ) {
return S (
std::next( std::begin(s), n ),
std::end(s)
);
}
// Predicate version
template< class P, class S >
S dropWhile( const P& p, const S& s ) {
return S (
std::find_if_not( std::begin(s), std::end(s), p ),
std::end(s)
);
}
template< class X > struct Reader {
using iterator = std::istream_iterator<X>;
iterator b;
iterator e;
Reader( iterator b = iterator( std::cin ),
iterator e = iterator() )
: b(b), e(e)
{
}
iterator begin() const { return b; }
iterator end() const { return e; }
};
auto r = drop( 2, Reader<int>() );
// Probably ill-advised,
// but this is /one/ way of doing IO before main().
std::vector<int> three = take( 3, r );
template< class F, template<class...> class S, class X,
class Res = typename std::result_of< F(X) >::type >
S<Res> scanl( F&& f, const S& s ) {
S<Res> r;
std::partial_sum( std::begin(s), std::end(s),
std::back_inserter(r),
std::forward<F>(f) );
return r;
}
int main() {
euler1();
std::cout << "size of three : " << three.size() << std::endl;
std::vector<int> v = { 5, 3, 2 };
std::vector<int> w = { 9, 8, 7 };
auto doubleV = zipWith( std::plus<int>(), v, v );
std::cout << "((10 - 5) - 3) - 2) = " << foldl( std::minus<int>(), 10, v ) << std::endl;
std::cout << "(2 - (3 - (5-5))) = " << foldr( std::minus<int>(), 5, v ) << std::endl;
std::vector<int> outOfOrder = { 10, 8, 3, 11, 1, 9 };
outOfOrder = fake_qsort( outOfOrder );
std::cout << "outOfOrder post sort: ";
std::copy( std::begin(outOfOrder), std::end(outOfOrder),
std::ostream_iterator<int>( std::cout, ", " ) );
std::cout << std::endl;
auto sums = map( std::plus<int>(), v, w );
std::vector<std::string> strs = { "st", "ri", "ng" };
// std::string associated with (+) is a monoid.
std::cout << "'st' + 'ri' + 'ng' = " <<
foldl( std::plus<std::string>(), std::string(), strs ) << std::endl;
using Func = std::function< int(int) >;
auto comp = []( Func f, Func g ) {
return [f,g]( int x ){ return f(g(x)); };
};
auto inc = []( int x ) { return x+1; };
auto id = []( int x ) { return x; };
std::vector<Func> incs = { inc, inc, inc };
// Functions can be monoids under composition.
std::cout << "(inc . inc . inc)(1) = " <<
foldl( comp, Func(id), incs )(1) << std::endl;
using List = std::forward_list<int>;
auto cons = []( List l, int x ) {
l.push_front( x );
return std::move(l);
};
List l = foldl( cons, List(), v );
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.