123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321 |
- // Copyright Louis Dionne 2013-2017
- // Distributed under the Boost Software License, Version 1.0.
- // (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
- #include <boost/hana/and.hpp>
- #include <boost/hana/any_of.hpp>
- #include <boost/hana/flatten.hpp>
- #include <boost/hana/functional/compose.hpp>
- #include <boost/hana/functional/partial.hpp>
- #include <boost/hana/fwd/ap.hpp>
- #include <boost/hana/fwd/equal.hpp>
- #include <boost/hana/fwd/find_if.hpp>
- #include <boost/hana/fwd/lift.hpp>
- #include <boost/hana/fwd/union.hpp>
- #include <boost/hana/if.hpp>
- #include <boost/hana/is_subset.hpp>
- #include <boost/hana/optional.hpp>
- #include <boost/hana/transform.hpp>
- namespace hana = boost::hana;
- // A `Monad` for searching infinite sets in finite time.
- //
- // Taken from http://goo.gl/XJeDy8.
- struct infinite_set_tag { };
- template <typename Find>
- struct infinite_set {
- Find find;
- using hana_tag = infinite_set_tag;
- };
- template <typename Pred>
- constexpr infinite_set<Pred> make_infinite_set(Pred pred) {
- return {pred};
- }
- template <typename X>
- constexpr auto singleton(X x) {
- return make_infinite_set([=](auto /*p*/) { return x; });
- }
- template <typename X, typename Y>
- constexpr auto doubleton(X x, Y y) {
- return make_infinite_set([=](auto p) {
- return hana::if_(p(x), x, y);
- });
- }
- namespace boost { namespace hana {
- template <>
- struct union_impl<infinite_set_tag> {
- template <typename Xs, typename Ys>
- static constexpr auto apply(Xs xs, Ys ys) {
- return flatten(doubleton(xs, ys));
- }
- };
- //////////////////////////////////////////////////////////////////////////
- // Comparable
- //////////////////////////////////////////////////////////////////////////
- template <>
- struct equal_impl<infinite_set_tag, infinite_set_tag> {
- template <typename Xs, typename Ys>
- static constexpr auto apply(Xs xs, Ys ys)
- { return and_(is_subset(xs, ys), is_subset(ys, xs)); }
- };
- //////////////////////////////////////////////////////////////////////////
- // Functor
- //////////////////////////////////////////////////////////////////////////
- template <>
- struct transform_impl<infinite_set_tag> {
- template <typename Set, typename F>
- static constexpr auto apply(Set set, F f) {
- return make_infinite_set([=](auto q) {
- return f(set.find(compose(q, f)));
- });
- }
- };
- //////////////////////////////////////////////////////////////////////////
- // Applicative
- //////////////////////////////////////////////////////////////////////////
- template <>
- struct lift_impl<infinite_set_tag> {
- template <typename X>
- static constexpr auto apply(X x)
- { return singleton(x); }
- };
- template <>
- struct ap_impl<infinite_set_tag> {
- template <typename F, typename Set>
- static constexpr auto apply(F fset, Set set) {
- return flatten(transform(fset, partial(transform, set)));
- }
- };
- //////////////////////////////////////////////////////////////////////////
- // Monad
- //////////////////////////////////////////////////////////////////////////
- template <>
- struct flatten_impl<infinite_set_tag> {
- template <typename Set>
- static constexpr auto apply(Set set) {
- return make_infinite_set([=](auto p) {
- return set.find([=](auto set) {
- return any_of(set, p);
- }).find(p);
- });
- }
- };
- //////////////////////////////////////////////////////////////////////////
- // Searchable
- //////////////////////////////////////////////////////////////////////////
- template <>
- struct find_if_impl<infinite_set_tag> {
- template <typename Set, typename Pred>
- static constexpr auto apply(Set set, Pred p) {
- auto x = set.find(p);
- return if_(p(x), hana::just(x), hana::nothing);
- }
- };
- template <>
- struct any_of_impl<infinite_set_tag> {
- template <typename Set, typename Pred>
- static constexpr auto apply(Set set, Pred p) {
- return p(set.find(p));
- }
- };
- }} // end namespace boost::hana
- //////////////////////////////////////////////////////////////////////////////
- // Tests
- //////////////////////////////////////////////////////////////////////////////
- #include <boost/hana/any_of.hpp>
- #include <boost/hana/ap.hpp>
- #include <boost/hana/assert.hpp>
- #include <boost/hana/equal.hpp>
- #include <boost/hana/find_if.hpp>
- #include <boost/hana/flatten.hpp>
- #include <boost/hana/integral_constant.hpp>
- #include <boost/hana/is_subset.hpp>
- #include <boost/hana/lift.hpp>
- #include <boost/hana/not.hpp>
- #include <boost/hana/optional.hpp>
- #include <boost/hana/plus.hpp>
- #include <boost/hana/transform.hpp>
- #include <boost/hana/union.hpp>
- namespace hana = boost::hana;
- template <int i>
- constexpr int n = i;
- template <int i>
- constexpr auto c = hana::int_c<i>;
- int main() {
- auto f = [](auto n) { return n + hana::int_c<10>; };
- auto g = [](auto n) { return n + hana::int_c<100>; };
- // union_
- {
- BOOST_HANA_CONSTANT_CHECK(hana::equal(
- hana::union_(singleton(c<0>), singleton(c<0>)),
- singleton(c<0>)
- ));
- BOOST_HANA_CONSTANT_CHECK(hana::equal(
- hana::union_(singleton(c<0>), singleton(c<1>)),
- doubleton(c<0>, c<1>)
- ));
- BOOST_HANA_CONSTANT_CHECK(hana::equal(
- hana::union_(singleton(c<0>), doubleton(c<0>, c<1>)),
- doubleton(c<0>, c<1>)
- ));
- }
- // Comparable
- {
- // equal
- {
- BOOST_HANA_CONSTEXPR_CHECK(hana::equal(singleton(n<0>), singleton(n<0>)));
- BOOST_HANA_CONSTEXPR_CHECK(hana::not_(hana::equal(singleton(n<0>), singleton(n<1>))));
- BOOST_HANA_CONSTEXPR_CHECK(hana::equal(singleton(n<0>), doubleton(n<0>, n<0>)));
- BOOST_HANA_CONSTEXPR_CHECK(hana::not_(hana::equal(singleton(n<0>), doubleton(n<0>, n<1>))));
- BOOST_HANA_CONSTEXPR_CHECK(hana::not_(hana::equal(singleton(n<0>), doubleton(n<1>, n<1>))));
- BOOST_HANA_CONSTEXPR_CHECK(hana::equal(doubleton(n<0>, n<1>), doubleton(n<0>, n<1>)));
- BOOST_HANA_CONSTEXPR_CHECK(hana::equal(doubleton(n<0>, n<1>), doubleton(n<1>, n<0>)));
- BOOST_HANA_CONSTEXPR_CHECK(hana::not_(hana::equal(doubleton(n<0>, n<1>), doubleton(n<0>, n<0>))));
- BOOST_HANA_CONSTEXPR_CHECK(hana::not_(hana::equal(doubleton(n<0>, n<1>), doubleton(n<3>, n<4>))));
- }
- }
- // Functor
- {
- // transform
- {
- BOOST_HANA_CONSTEXPR_CHECK(hana::equal(
- hana::transform(singleton(n<0>), f),
- singleton(f(n<0>))
- ));
- BOOST_HANA_CONSTEXPR_CHECK(hana::equal(
- hana::transform(doubleton(n<0>, n<1>), f),
- doubleton(f(n<0>), f(n<1>))
- ));
- BOOST_HANA_CONSTEXPR_CHECK(hana::equal(
- hana::transform(doubleton(n<0>, n<0>), f),
- singleton(f(n<0>))
- ));
- }
- }
- // Applicative
- {
- // ap
- {
- BOOST_HANA_CONSTANT_CHECK(hana::equal(
- hana::ap(singleton(f), singleton(c<0>)),
- singleton(f(c<0>))
- ));
- BOOST_HANA_CONSTANT_CHECK(hana::equal(
- hana::ap(singleton(f), doubleton(c<0>, c<1>)),
- doubleton(f(c<0>), f(c<1>))
- ));
- BOOST_HANA_CONSTANT_CHECK(hana::equal(
- hana::ap(doubleton(f, g), singleton(c<0>)),
- doubleton(f(c<0>), g(c<0>))
- ));
- BOOST_HANA_CONSTANT_CHECK(hana::equal(
- hana::ap(doubleton(f, g), doubleton(c<0>, c<1>)),
- hana::union_(doubleton(f(c<0>), f(c<1>)),
- doubleton(g(c<0>), g(c<1>)))
- ));
- }
- // lift
- {
- BOOST_HANA_CONSTANT_CHECK(hana::equal(
- hana::lift<infinite_set_tag>(c<0>),
- singleton(c<0>)
- ));
- }
- }
- // Monad
- {
- // flatten
- {
- BOOST_HANA_CONSTANT_CHECK(hana::equal(
- hana::flatten(singleton(singleton(c<0>))),
- singleton(c<0>)
- ));
- BOOST_HANA_CONSTANT_CHECK(hana::equal(
- hana::flatten(singleton(doubleton(c<0>, c<1>))),
- doubleton(c<0>, c<1>)
- ));
- BOOST_HANA_CONSTANT_CHECK(hana::equal(
- hana::flatten(doubleton(singleton(c<0>), singleton(c<1>))),
- doubleton(c<0>, c<1>)
- ));
- BOOST_HANA_CONSTANT_CHECK(hana::equal(
- hana::flatten(doubleton(doubleton(c<0>, c<1>), singleton(c<2>))),
- hana::union_(doubleton(c<0>, c<1>), singleton(c<2>))
- ));
- BOOST_HANA_CONSTANT_CHECK(hana::equal(
- hana::flatten(doubleton(singleton(c<0>), doubleton(c<1>, c<2>))),
- hana::union_(doubleton(c<0>, c<1>), singleton(c<2>))
- ));
- BOOST_HANA_CONSTANT_CHECK(hana::equal(
- hana::flatten(doubleton(doubleton(c<0>, c<1>), doubleton(c<2>, c<3>))),
- hana::union_(doubleton(c<0>, c<1>), doubleton(c<2>, c<3>))
- ));
- }
- }
- // Searchable
- {
- // any_of
- {
- BOOST_HANA_CONSTEXPR_CHECK(hana::any_of(singleton(n<0>), hana::equal.to(n<0>)));
- BOOST_HANA_CONSTEXPR_CHECK(hana::not_(hana::any_of(singleton(n<0>), hana::equal.to(n<1>))));
- BOOST_HANA_CONSTEXPR_CHECK(hana::any_of(doubleton(n<0>, n<1>), hana::equal.to(n<0>)));
- BOOST_HANA_CONSTEXPR_CHECK(hana::any_of(doubleton(n<0>, n<1>), hana::equal.to(n<1>)));
- BOOST_HANA_CONSTEXPR_CHECK(hana::not_(hana::any_of(doubleton(n<0>, n<1>), hana::equal.to(n<2>))));
- }
- // find_if
- {
- BOOST_HANA_CONSTANT_CHECK(hana::find_if(singleton(c<0>), hana::equal.to(c<0>)) == hana::just(c<0>));
- BOOST_HANA_CONSTANT_CHECK(hana::find_if(singleton(c<1>), hana::equal.to(c<0>)) == hana::nothing);
- BOOST_HANA_CONSTANT_CHECK(hana::find_if(doubleton(c<0>, c<1>), hana::equal.to(c<0>)) == hana::just(c<0>));
- BOOST_HANA_CONSTANT_CHECK(hana::find_if(doubleton(c<0>, c<1>), hana::equal.to(c<1>)) == hana::just(c<1>));
- BOOST_HANA_CONSTANT_CHECK(hana::find_if(doubleton(c<0>, c<1>), hana::equal.to(c<2>)) == hana::nothing);
- }
- // is_subset
- {
- BOOST_HANA_CONSTEXPR_CHECK(hana::is_subset(singleton(n<0>), singleton(n<0>)));
- BOOST_HANA_CONSTEXPR_CHECK(hana::not_(hana::is_subset(singleton(n<1>), singleton(n<0>))));
- BOOST_HANA_CONSTEXPR_CHECK(hana::is_subset(singleton(n<0>), doubleton(n<0>, n<1>)));
- BOOST_HANA_CONSTEXPR_CHECK(hana::is_subset(singleton(n<1>), doubleton(n<0>, n<1>)));
- BOOST_HANA_CONSTEXPR_CHECK(hana::not_(hana::is_subset(singleton(n<2>), doubleton(n<0>, n<1>))));
- BOOST_HANA_CONSTEXPR_CHECK(hana::is_subset(doubleton(n<0>, n<1>), doubleton(n<0>, n<1>)));
- BOOST_HANA_CONSTEXPR_CHECK(hana::not_(hana::is_subset(doubleton(n<0>, n<2>), doubleton(n<0>, n<1>))));
- BOOST_HANA_CONSTEXPR_CHECK(hana::not_(hana::is_subset(doubleton(n<2>, n<3>), doubleton(n<0>, n<1>))));
- }
- }
- }
|