• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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/ap.hpp>
7 #include <boost/hana/assert.hpp>
8 #include <boost/hana/concat.hpp>
9 #include <boost/hana/equal.hpp>
10 #include <boost/hana/flatten.hpp>
11 #include <boost/hana/fold_left.hpp>
12 #include <boost/hana/lift.hpp>
13 #include <boost/hana/sum.hpp>
14 #include <boost/hana/transform.hpp>
15 #include <boost/hana/tuple.hpp>
16 namespace hana = boost::hana;
17 
18 
19 struct tree_tag;
20 
21 template <typename X, typename Subforest>
22 struct node {
23     X value;
24     Subforest subforest;
25 
26     using hana_tag = tree_tag;
27 };
28 
29 constexpr auto make_forest = hana::make_tuple;
30 
31 template <typename X, typename Subforest>
make_node(X x,Subforest subforest)32 constexpr auto make_node(X x, Subforest subforest) {
33     return node<X, Subforest>{x, subforest};
34 }
35 
36 namespace boost { namespace hana {
37     //////////////////////////////////////////////////////////////////////////
38     // Comparable
39     //////////////////////////////////////////////////////////////////////////
40     template <>
41     struct equal_impl<tree_tag, tree_tag> {
42         template <typename Node1, typename Node2>
applyboost::hana::equal_impl43         static constexpr auto apply(Node1 node1, Node2 node2) {
44             return hana::and_(
45                 hana::equal(node1.value, node2.value),
46                 hana::equal(node1.subforest, node2.subforest)
47             );
48         }
49     };
50 
51     //////////////////////////////////////////////////////////////////////////
52     // Functor
53     //////////////////////////////////////////////////////////////////////////
54     template <>
55     struct transform_impl<tree_tag> {
56         template <typename Node, typename F>
applyboost::hana::transform_impl57         static constexpr auto apply(Node node, F f) {
58             return make_node(
59                 f(node.value),
60                 hana::transform(node.subforest, [=](auto subtree) {
61                     return hana::transform(subtree, f);
62                 })
63             );
64         }
65     };
66 
67     //////////////////////////////////////////////////////////////////////////
68     // Applicative
69     //////////////////////////////////////////////////////////////////////////
70     template <>
71     struct lift_impl<tree_tag> {
72         template <typename X>
applyboost::hana::lift_impl73         static constexpr auto apply(X x)
74         { return make_node(x, make_forest()); }
75     };
76 
77     template <>
78     struct ap_impl<tree_tag> {
79         template <typename F, typename X>
applyboost::hana::ap_impl80         static constexpr auto apply(F f, X x) {
81             return make_node(
82                 f.value(x.value),
83                 hana::concat(
84                     hana::transform(x.subforest, [=](auto subtree) {
85                         return hana::transform(subtree, f.value);
86                     }),
87                     hana::transform(f.subforest, [=](auto subtree) {
88                         return hana::ap(subtree, x);
89                     })
90                 )
91             );
92         }
93     };
94 
95     //////////////////////////////////////////////////////////////////////////
96     // Monad
97     //////////////////////////////////////////////////////////////////////////
98     template <>
99     struct flatten_impl<tree_tag> {
100         template <typename Node>
applyboost::hana::flatten_impl101         static constexpr auto apply(Node node) {
102             return make_node(
103                 node.value.value,
104                 hana::concat(
105                     node.value.subforest,
106                     hana::transform(node.subforest, hana::flatten)
107                 )
108             );
109         }
110     };
111 
112     //////////////////////////////////////////////////////////////////////////
113     // Foldable
114     //////////////////////////////////////////////////////////////////////////
115     template <>
116     struct fold_left_impl<tree_tag> {
117         template <typename Node, typename State, typename F>
applyboost::hana::fold_left_impl118         static constexpr auto apply(Node node, State state, F f) {
119             return hana::fold_left(node.subforest, f(state, node.value),
120                         [=](auto state, auto subtree) {
121                             return hana::fold_left(subtree, state, f);
122                         });
123         }
124     };
125 }}
126 
main()127 int main() {
128     constexpr auto tree = make_node(1, make_forest(
129         make_node(2, make_forest()),
130         make_node(3, make_forest()),
131         make_node(4, make_forest())
132     ));
133 
134     BOOST_HANA_CONSTEXPR_CHECK(hana::sum<>(tree) == 10);
135 
136     BOOST_HANA_CONSTEXPR_CHECK(hana::equal(
137         hana::transform(tree, [](int i) { return i + 1; }),
138         make_node(2, make_forest(
139             make_node(3, make_forest()),
140             make_node(4, make_forest()),
141             make_node(5, make_forest())
142         ))
143     ));
144 }
145