1 // Copyright Louis Dionne 2013-2017
2 // Distributed under the Boost Software License, Version 1.0.
3 // (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
4
5 #include <boost/hana/and.hpp>
6 #include <boost/hana/any_of.hpp>
7 #include <boost/hana/flatten.hpp>
8 #include <boost/hana/functional/compose.hpp>
9 #include <boost/hana/functional/partial.hpp>
10 #include <boost/hana/fwd/ap.hpp>
11 #include <boost/hana/fwd/equal.hpp>
12 #include <boost/hana/fwd/find_if.hpp>
13 #include <boost/hana/fwd/lift.hpp>
14 #include <boost/hana/fwd/union.hpp>
15 #include <boost/hana/if.hpp>
16 #include <boost/hana/is_subset.hpp>
17 #include <boost/hana/optional.hpp>
18 #include <boost/hana/transform.hpp>
19 namespace hana = boost::hana;
20
21
22 // A `Monad` for searching infinite sets in finite time.
23 //
24 // Taken from http://goo.gl/XJeDy8.
25 struct infinite_set_tag { };
26
27 template <typename Find>
28 struct infinite_set {
29 Find find;
30 using hana_tag = infinite_set_tag;
31 };
32
33 template <typename Pred>
make_infinite_set(Pred pred)34 constexpr infinite_set<Pred> make_infinite_set(Pred pred) {
35 return {pred};
36 }
37
38 template <typename X>
singleton(X x)39 constexpr auto singleton(X x) {
40 return make_infinite_set([=](auto /*p*/) { return x; });
41 }
42
43 template <typename X, typename Y>
doubleton(X x,Y y)44 constexpr auto doubleton(X x, Y y) {
45 return make_infinite_set([=](auto p) {
46 return hana::if_(p(x), x, y);
47 });
48 }
49
50 namespace boost { namespace hana {
51 template <>
52 struct union_impl<infinite_set_tag> {
53 template <typename Xs, typename Ys>
applyboost::hana::union_impl54 static constexpr auto apply(Xs xs, Ys ys) {
55 return flatten(doubleton(xs, ys));
56 }
57 };
58
59 //////////////////////////////////////////////////////////////////////////
60 // Comparable
61 //////////////////////////////////////////////////////////////////////////
62 template <>
63 struct equal_impl<infinite_set_tag, infinite_set_tag> {
64 template <typename Xs, typename Ys>
applyboost::hana::equal_impl65 static constexpr auto apply(Xs xs, Ys ys)
66 { return and_(is_subset(xs, ys), is_subset(ys, xs)); }
67 };
68
69
70 //////////////////////////////////////////////////////////////////////////
71 // Functor
72 //////////////////////////////////////////////////////////////////////////
73 template <>
74 struct transform_impl<infinite_set_tag> {
75 template <typename Set, typename F>
applyboost::hana::transform_impl76 static constexpr auto apply(Set set, F f) {
77 return make_infinite_set([=](auto q) {
78 return f(set.find(compose(q, f)));
79 });
80 }
81 };
82
83 //////////////////////////////////////////////////////////////////////////
84 // Applicative
85 //////////////////////////////////////////////////////////////////////////
86 template <>
87 struct lift_impl<infinite_set_tag> {
88 template <typename X>
applyboost::hana::lift_impl89 static constexpr auto apply(X x)
90 { return singleton(x); }
91 };
92
93 template <>
94 struct ap_impl<infinite_set_tag> {
95 template <typename F, typename Set>
applyboost::hana::ap_impl96 static constexpr auto apply(F fset, Set set) {
97 return flatten(transform(fset, partial(transform, set)));
98 }
99 };
100
101 //////////////////////////////////////////////////////////////////////////
102 // Monad
103 //////////////////////////////////////////////////////////////////////////
104 template <>
105 struct flatten_impl<infinite_set_tag> {
106 template <typename Set>
applyboost::hana::flatten_impl107 static constexpr auto apply(Set set) {
108 return make_infinite_set([=](auto p) {
109 return set.find([=](auto set) {
110 return any_of(set, p);
111 }).find(p);
112 });
113 }
114 };
115
116 //////////////////////////////////////////////////////////////////////////
117 // Searchable
118 //////////////////////////////////////////////////////////////////////////
119 template <>
120 struct find_if_impl<infinite_set_tag> {
121 template <typename Set, typename Pred>
applyboost::hana::find_if_impl122 static constexpr auto apply(Set set, Pred p) {
123 auto x = set.find(p);
124 return if_(p(x), hana::just(x), hana::nothing);
125 }
126 };
127
128 template <>
129 struct any_of_impl<infinite_set_tag> {
130 template <typename Set, typename Pred>
applyboost::hana::any_of_impl131 static constexpr auto apply(Set set, Pred p) {
132 return p(set.find(p));
133 }
134 };
135 }} // end namespace boost::hana
136
137 //////////////////////////////////////////////////////////////////////////////
138 // Tests
139 //////////////////////////////////////////////////////////////////////////////
140
141 #include <boost/hana/any_of.hpp>
142 #include <boost/hana/ap.hpp>
143 #include <boost/hana/assert.hpp>
144 #include <boost/hana/equal.hpp>
145 #include <boost/hana/find_if.hpp>
146 #include <boost/hana/flatten.hpp>
147 #include <boost/hana/integral_constant.hpp>
148 #include <boost/hana/is_subset.hpp>
149 #include <boost/hana/lift.hpp>
150 #include <boost/hana/not.hpp>
151 #include <boost/hana/optional.hpp>
152 #include <boost/hana/plus.hpp>
153 #include <boost/hana/transform.hpp>
154 #include <boost/hana/union.hpp>
155 namespace hana = boost::hana;
156
157
158 template <int i>
159 constexpr int n = i;
160
161 template <int i>
162 constexpr auto c = hana::int_c<i>;
163
main()164 int main() {
165 auto f = [](auto n) { return n + hana::int_c<10>; };
166 auto g = [](auto n) { return n + hana::int_c<100>; };
167
168 // union_
169 {
170 BOOST_HANA_CONSTANT_CHECK(hana::equal(
171 hana::union_(singleton(c<0>), singleton(c<0>)),
172 singleton(c<0>)
173 ));
174 BOOST_HANA_CONSTANT_CHECK(hana::equal(
175 hana::union_(singleton(c<0>), singleton(c<1>)),
176 doubleton(c<0>, c<1>)
177 ));
178 BOOST_HANA_CONSTANT_CHECK(hana::equal(
179 hana::union_(singleton(c<0>), doubleton(c<0>, c<1>)),
180 doubleton(c<0>, c<1>)
181 ));
182 }
183
184 // Comparable
185 {
186 // equal
187 {
188 BOOST_HANA_CONSTEXPR_CHECK(hana::equal(singleton(n<0>), singleton(n<0>)));
189 BOOST_HANA_CONSTEXPR_CHECK(hana::not_(hana::equal(singleton(n<0>), singleton(n<1>))));
190
191 BOOST_HANA_CONSTEXPR_CHECK(hana::equal(singleton(n<0>), doubleton(n<0>, n<0>)));
192 BOOST_HANA_CONSTEXPR_CHECK(hana::not_(hana::equal(singleton(n<0>), doubleton(n<0>, n<1>))));
193 BOOST_HANA_CONSTEXPR_CHECK(hana::not_(hana::equal(singleton(n<0>), doubleton(n<1>, n<1>))));
194
195 BOOST_HANA_CONSTEXPR_CHECK(hana::equal(doubleton(n<0>, n<1>), doubleton(n<0>, n<1>)));
196 BOOST_HANA_CONSTEXPR_CHECK(hana::equal(doubleton(n<0>, n<1>), doubleton(n<1>, n<0>)));
197 BOOST_HANA_CONSTEXPR_CHECK(hana::not_(hana::equal(doubleton(n<0>, n<1>), doubleton(n<0>, n<0>))));
198 BOOST_HANA_CONSTEXPR_CHECK(hana::not_(hana::equal(doubleton(n<0>, n<1>), doubleton(n<3>, n<4>))));
199 }
200 }
201
202 // Functor
203 {
204 // transform
205 {
206 BOOST_HANA_CONSTEXPR_CHECK(hana::equal(
207 hana::transform(singleton(n<0>), f),
208 singleton(f(n<0>))
209 ));
210 BOOST_HANA_CONSTEXPR_CHECK(hana::equal(
211 hana::transform(doubleton(n<0>, n<1>), f),
212 doubleton(f(n<0>), f(n<1>))
213 ));
214 BOOST_HANA_CONSTEXPR_CHECK(hana::equal(
215 hana::transform(doubleton(n<0>, n<0>), f),
216 singleton(f(n<0>))
217 ));
218 }
219 }
220
221 // Applicative
222 {
223 // ap
224 {
225 BOOST_HANA_CONSTANT_CHECK(hana::equal(
226 hana::ap(singleton(f), singleton(c<0>)),
227 singleton(f(c<0>))
228 ));
229 BOOST_HANA_CONSTANT_CHECK(hana::equal(
230 hana::ap(singleton(f), doubleton(c<0>, c<1>)),
231 doubleton(f(c<0>), f(c<1>))
232 ));
233
234 BOOST_HANA_CONSTANT_CHECK(hana::equal(
235 hana::ap(doubleton(f, g), singleton(c<0>)),
236 doubleton(f(c<0>), g(c<0>))
237 ));
238 BOOST_HANA_CONSTANT_CHECK(hana::equal(
239 hana::ap(doubleton(f, g), doubleton(c<0>, c<1>)),
240 hana::union_(doubleton(f(c<0>), f(c<1>)),
241 doubleton(g(c<0>), g(c<1>)))
242 ));
243 }
244
245 // lift
246 {
247 BOOST_HANA_CONSTANT_CHECK(hana::equal(
248 hana::lift<infinite_set_tag>(c<0>),
249 singleton(c<0>)
250 ));
251 }
252 }
253
254 // Monad
255 {
256 // flatten
257 {
258 BOOST_HANA_CONSTANT_CHECK(hana::equal(
259 hana::flatten(singleton(singleton(c<0>))),
260 singleton(c<0>)
261 ));
262 BOOST_HANA_CONSTANT_CHECK(hana::equal(
263 hana::flatten(singleton(doubleton(c<0>, c<1>))),
264 doubleton(c<0>, c<1>)
265 ));
266
267 BOOST_HANA_CONSTANT_CHECK(hana::equal(
268 hana::flatten(doubleton(singleton(c<0>), singleton(c<1>))),
269 doubleton(c<0>, c<1>)
270 ));
271 BOOST_HANA_CONSTANT_CHECK(hana::equal(
272 hana::flatten(doubleton(doubleton(c<0>, c<1>), singleton(c<2>))),
273 hana::union_(doubleton(c<0>, c<1>), singleton(c<2>))
274 ));
275 BOOST_HANA_CONSTANT_CHECK(hana::equal(
276 hana::flatten(doubleton(singleton(c<0>), doubleton(c<1>, c<2>))),
277 hana::union_(doubleton(c<0>, c<1>), singleton(c<2>))
278 ));
279 BOOST_HANA_CONSTANT_CHECK(hana::equal(
280 hana::flatten(doubleton(doubleton(c<0>, c<1>), doubleton(c<2>, c<3>))),
281 hana::union_(doubleton(c<0>, c<1>), doubleton(c<2>, c<3>))
282 ));
283 }
284 }
285
286 // Searchable
287 {
288 // any_of
289 {
290 BOOST_HANA_CONSTEXPR_CHECK(hana::any_of(singleton(n<0>), hana::equal.to(n<0>)));
291 BOOST_HANA_CONSTEXPR_CHECK(hana::not_(hana::any_of(singleton(n<0>), hana::equal.to(n<1>))));
292 BOOST_HANA_CONSTEXPR_CHECK(hana::any_of(doubleton(n<0>, n<1>), hana::equal.to(n<0>)));
293 BOOST_HANA_CONSTEXPR_CHECK(hana::any_of(doubleton(n<0>, n<1>), hana::equal.to(n<1>)));
294 BOOST_HANA_CONSTEXPR_CHECK(hana::not_(hana::any_of(doubleton(n<0>, n<1>), hana::equal.to(n<2>))));
295 }
296
297 // find_if
298 {
299 BOOST_HANA_CONSTANT_CHECK(hana::find_if(singleton(c<0>), hana::equal.to(c<0>)) == hana::just(c<0>));
300 BOOST_HANA_CONSTANT_CHECK(hana::find_if(singleton(c<1>), hana::equal.to(c<0>)) == hana::nothing);
301
302 BOOST_HANA_CONSTANT_CHECK(hana::find_if(doubleton(c<0>, c<1>), hana::equal.to(c<0>)) == hana::just(c<0>));
303 BOOST_HANA_CONSTANT_CHECK(hana::find_if(doubleton(c<0>, c<1>), hana::equal.to(c<1>)) == hana::just(c<1>));
304 BOOST_HANA_CONSTANT_CHECK(hana::find_if(doubleton(c<0>, c<1>), hana::equal.to(c<2>)) == hana::nothing);
305 }
306
307 // is_subset
308 {
309 BOOST_HANA_CONSTEXPR_CHECK(hana::is_subset(singleton(n<0>), singleton(n<0>)));
310 BOOST_HANA_CONSTEXPR_CHECK(hana::not_(hana::is_subset(singleton(n<1>), singleton(n<0>))));
311
312 BOOST_HANA_CONSTEXPR_CHECK(hana::is_subset(singleton(n<0>), doubleton(n<0>, n<1>)));
313 BOOST_HANA_CONSTEXPR_CHECK(hana::is_subset(singleton(n<1>), doubleton(n<0>, n<1>)));
314 BOOST_HANA_CONSTEXPR_CHECK(hana::not_(hana::is_subset(singleton(n<2>), doubleton(n<0>, n<1>))));
315
316 BOOST_HANA_CONSTEXPR_CHECK(hana::is_subset(doubleton(n<0>, n<1>), doubleton(n<0>, n<1>)));
317 BOOST_HANA_CONSTEXPR_CHECK(hana::not_(hana::is_subset(doubleton(n<0>, n<2>), doubleton(n<0>, n<1>))));
318 BOOST_HANA_CONSTEXPR_CHECK(hana::not_(hana::is_subset(doubleton(n<2>, n<3>), doubleton(n<0>, n<1>))));
319 }
320 }
321 }
322