Created
December 15, 2012 01:03
-
-
Save splinterofchaos/4290166 to your computer and use it in GitHub Desktop.
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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