1// Copyright Louis Dionne 2013-2022
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>
16namespace hana = boost::hana;
17
18
19struct tree_tag;
20
21template <typename X, typename Subforest>
22struct node {
23 X value;
24 Subforest subforest;
25
26 using hana_tag = tree_tag;
27};
28
29constexpr auto make_forest = hana::make_tuple;
30
31template <typename X, typename Subforest>
32constexpr auto make_node(X x, Subforest subforest) {
33 return node<X, Subforest>{x, subforest};
34}
35
36namespace boost { namespace hana {
37 //////////////////////////////////////////////////////////////////////////
38 // Comparable
39 //////////////////////////////////////////////////////////////////////////
40 template <>
41 struct equal_impl<tree_tag, tree_tag> {
42 template <typename Node1, typename Node2>
43 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>
57 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>
73 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>
80 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>
101 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>
118 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
127int main() {
128 constexpr auto tree = make_node(x: 1, subforest: make_forest(
129 make_node(x: 2, subforest: make_forest()),
130 make_node(x: 3, subforest: make_forest()),
131 make_node(x: 4, subforest: 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

source code of boost/libs/hana/example/misc/tree.cpp