|
0
|
1 package fj.data;
|
|
|
2
|
|
|
3 import fj.F;
|
|
|
4 import fj.F2;
|
|
|
5 import fj.F2Functions;
|
|
|
6 import fj.P;
|
|
|
7 import fj.P1;
|
|
|
8 import fj.P2;
|
|
|
9 import static fj.Function.*;
|
|
|
10 import static fj.data.Stream.*;
|
|
|
11 import fj.Monoid;
|
|
|
12 import fj.Show;
|
|
|
13
|
|
|
14 import java.util.Collection;
|
|
|
15 import java.util.Iterator;
|
|
|
16
|
|
|
17 /**
|
|
|
18 * Provides a lazy, immutable, non-empty, multi-way tree (a rose tree).
|
|
|
19 *
|
|
|
20 * @version %build.number%
|
|
|
21 */
|
|
|
22 public final class Tree<A> implements Iterable<A> {
|
|
|
23 /**
|
|
|
24 * Returns an iterator for this tree. This method exists to permit the use in a <code>for</code>-each loop.
|
|
|
25 *
|
|
|
26 * @return A iterator for this tree.
|
|
|
27 */
|
|
|
28 public Iterator<A> iterator() {
|
|
|
29 return flatten().iterator();
|
|
|
30 }
|
|
|
31
|
|
|
32 private final A root;
|
|
|
33 private final P1<Stream<Tree<A>>> subForest;
|
|
|
34
|
|
|
35 private Tree(final A root, final P1<Stream<Tree<A>>> subForest) {
|
|
|
36 this.root = root;
|
|
|
37 this.subForest = subForest;
|
|
|
38 }
|
|
|
39
|
|
|
40 /**
|
|
|
41 * Creates a nullary tree.
|
|
|
42 *
|
|
|
43 * @param root The root element of the tree.
|
|
|
44 * @return A nullary tree with the root element in it.
|
|
|
45 */
|
|
|
46 public static <A> Tree<A> leaf(final A root) {
|
|
|
47 return node(root, Stream.<Tree<A>>nil());
|
|
|
48 }
|
|
|
49
|
|
|
50 /**
|
|
|
51 * Creates a new tree given a root and a (potentially infinite) subforest.
|
|
|
52 *
|
|
|
53 * @param root The root element of the tree.
|
|
|
54 * @param forest A stream of the tree's subtrees.
|
|
|
55 * @return A newly sprouted tree.
|
|
|
56 */
|
|
|
57 public static <A> Tree<A> node(final A root, final P1<Stream<Tree<A>>> forest) {
|
|
|
58 return new Tree<A>(root, forest);
|
|
|
59 }
|
|
|
60
|
|
|
61 /**
|
|
|
62 * Creates a new tree given a root and a (potentially infinite) subforest.
|
|
|
63 *
|
|
|
64 * @param root The root element of the tree.
|
|
|
65 * @param forest A stream of the tree's subtrees.
|
|
|
66 * @return A newly sprouted tree.
|
|
|
67 */
|
|
|
68 public static <A> Tree<A> node(final A root, final Stream<Tree<A>> forest) {
|
|
|
69 return new Tree<A>(root, P.p(forest));
|
|
|
70 }
|
|
|
71
|
|
|
72 /**
|
|
|
73 * Creates a new n-ary given a root and a subforest of length n.
|
|
|
74 *
|
|
|
75 * @param root The root element of the tree.
|
|
|
76 * @param forest A list of the tree's subtrees.
|
|
|
77 * @return A newly sprouted tree.
|
|
|
78 */
|
|
|
79 public static <A> Tree<A> node(final A root, final List<Tree<A>> forest) {
|
|
|
80 return node(root, forest.toStream());
|
|
|
81 }
|
|
|
82
|
|
|
83 /**
|
|
|
84 * First-class constructor of trees.
|
|
|
85 *
|
|
|
86 * @return A function that constructs an n-ary tree given a root and a subforest or length n.
|
|
|
87 */
|
|
|
88 public static <A> F<A, F<P1<Stream<Tree<A>>>, Tree<A>>> node() {
|
|
|
89 return curry(new F2<A, P1<Stream<Tree<A>>>, Tree<A>>() {
|
|
|
90 public Tree<A> f(final A a, final P1<Stream<Tree<A>>> p1) {
|
|
|
91 return node(a, p1);
|
|
|
92 }
|
|
|
93 });
|
|
|
94 }
|
|
|
95
|
|
|
96 /**
|
|
|
97 * Returns the root element of the tree.
|
|
|
98 *
|
|
|
99 * @return The root element of the tree.
|
|
|
100 */
|
|
|
101 public A root() {
|
|
|
102 return root;
|
|
|
103 }
|
|
|
104
|
|
|
105 /**
|
|
|
106 * Returns a stream of the tree's subtrees.
|
|
|
107 *
|
|
|
108 * @return A stream of the tree's subtrees.
|
|
|
109 */
|
|
|
110 public P1<Stream<Tree<A>>> subForest() {
|
|
|
111 return subForest;
|
|
|
112 }
|
|
|
113
|
|
|
114 /**
|
|
|
115 * Provides a transformation from a tree to its root.
|
|
|
116 *
|
|
|
117 * @return A transformation from a tree to its root.
|
|
|
118 */
|
|
|
119 public static <A> F<Tree<A>, A> root_() {
|
|
|
120 return new F<Tree<A>, A>() {
|
|
|
121 public A f(final Tree<A> a) {
|
|
|
122 return a.root();
|
|
|
123 }
|
|
|
124 };
|
|
|
125 }
|
|
|
126
|
|
|
127 /**
|
|
|
128 * Provides a transformation from a tree to its subforest.
|
|
|
129 *
|
|
|
130 * @return A transformation from a tree to its subforest.
|
|
|
131 */
|
|
|
132 public static <A> F<Tree<A>, P1<Stream<Tree<A>>>> subForest_() {
|
|
|
133 return new F<Tree<A>, P1<Stream<Tree<A>>>>() {
|
|
|
134 public P1<Stream<Tree<A>>> f(final Tree<A> a) {
|
|
|
135 return a.subForest();
|
|
|
136 }
|
|
|
137 };
|
|
|
138 }
|
|
|
139
|
|
|
140 /**
|
|
|
141 * Puts the elements of the tree into a Stream, in pre-order.
|
|
|
142 *
|
|
|
143 * @return The elements of the tree in pre-order.
|
|
|
144 */
|
|
|
145 public Stream<A> flatten() {
|
|
|
146 final F2<Tree<A>, P1<Stream<A>>, Stream<A>> squish = new F2<Tree<A>, P1<Stream<A>>, Stream<A>>() {
|
|
|
147 public Stream<A> f(final Tree<A> t, final P1<Stream<A>> xs) {
|
|
|
148 return cons(t.root(), t.subForest().map(Stream.<Tree<A>, Stream<A>>foldRight().f(F2Functions.curry(this)).f(xs._1())));
|
|
|
149 }
|
|
|
150 };
|
|
|
151 return squish.f(this, P.p(Stream.<A>nil()));
|
|
|
152 }
|
|
|
153
|
|
|
154 /**
|
|
|
155 * flatten :: Tree a -> [a]
|
|
|
156 * flatten t = squish t []
|
|
|
157 * where squish (Node x ts) xs = x:Prelude.foldr squish xs ts
|
|
|
158 * Puts the elements of the tree into a Stream, in pre-order.
|
|
|
159 *
|
|
|
160 * @return The elements of the tree in pre-order.
|
|
|
161 */
|
|
|
162 public static <A> F<Tree<A>, Stream<A>> flatten_() {
|
|
|
163 return new F<Tree<A>, Stream<A>>() {
|
|
|
164 public Stream<A> f(final Tree<A> t) {
|
|
|
165 return t.flatten();
|
|
|
166 }
|
|
|
167 };
|
|
|
168 }
|
|
|
169
|
|
|
170 /**
|
|
|
171 * Provides a stream of the elements of the tree at each level, in level order.
|
|
|
172 *
|
|
|
173 * @return The elements of the tree at each level.
|
|
|
174 */
|
|
|
175 public Stream<Stream<A>> levels() {
|
|
|
176 final F<Stream<Tree<A>>, Stream<Tree<A>>> flatSubForests =
|
|
|
177 Stream.<Tree<A>, Tree<A>>bind_().f(compose(P1.<Stream<Tree<A>>>__1(), Tree.<A>subForest_()));
|
|
|
178 final F<Stream<Tree<A>>, Stream<A>> roots = Stream.<Tree<A>, A>map_().f(Tree.<A>root_());
|
|
|
179 return iterateWhile(flatSubForests, Stream.<Tree<A>>isNotEmpty_(), single(this)).map(roots);
|
|
|
180 }
|
|
|
181
|
|
|
182 /**
|
|
|
183 * Maps the given function over this tree.
|
|
|
184 *
|
|
|
185 * @param f The function to map over this tree.
|
|
|
186 * @return The new Tree after the function has been applied to each element in this Tree.
|
|
|
187 */
|
|
|
188 public <B> Tree<B> fmap(final F<A, B> f) {
|
|
|
189 return node(f.f(root()), subForest().map(Stream.<Tree<A>, Tree<B>>map_().f(Tree.<A, B>fmap_().f(f))));
|
|
|
190 }
|
|
|
191
|
|
|
192 /**
|
|
|
193 * Provides a transformation to lift any function so that it maps over Trees.
|
|
|
194 *
|
|
|
195 * @return A transformation to lift any function so that it maps over Trees.
|
|
|
196 */
|
|
|
197 public static <A, B> F<F<A, B>, F<Tree<A>, Tree<B>>> fmap_() {
|
|
|
198 return new F<F<A, B>, F<Tree<A>, Tree<B>>>() {
|
|
|
199 public F<Tree<A>, Tree<B>> f(final F<A, B> f) {
|
|
|
200 return new F<Tree<A>, Tree<B>>() {
|
|
|
201 public Tree<B> f(final Tree<A> a) {
|
|
|
202 return a.fmap(f);
|
|
|
203 }
|
|
|
204 };
|
|
|
205 }
|
|
|
206 };
|
|
|
207 }
|
|
|
208
|
|
|
209 /**
|
|
|
210 * Folds this tree using the given monoid.
|
|
|
211 *
|
|
|
212 * @param f A transformation from this tree's elements, to the monoid.
|
|
|
213 * @param m The monoid to fold this tree with.
|
|
|
214 * @return The result of folding the tree with the given monoid.
|
|
|
215 */
|
|
|
216 public <B> B foldMap(final F<A, B> f, final Monoid<B> m) {
|
|
|
217 return m.sum(f.f(root()), m.sumRight(subForest()._1().map(foldMap_(f, m)).toList()));
|
|
|
218 }
|
|
|
219
|
|
|
220 /**
|
|
|
221 * Projects an immutable collection of this tree.
|
|
|
222 *
|
|
|
223 * @return An immutable collection of this tree.
|
|
|
224 */
|
|
|
225 public Collection<A> toCollection() {
|
|
|
226 return flatten().toCollection();
|
|
|
227 }
|
|
|
228
|
|
|
229 /**
|
|
|
230 * Provides a function that folds a tree with the given monoid.
|
|
|
231 *
|
|
|
232 * @param f A transformation from a tree's elements to the monoid.
|
|
|
233 * @param m A monoid to fold the tree with.
|
|
|
234 * @return A function that, given a tree, folds it with the given monoid.
|
|
|
235 */
|
|
|
236 public static <A, B> F<Tree<A>, B> foldMap_(final F<A, B> f, final Monoid<B> m) {
|
|
|
237 return new F<Tree<A>, B>() {
|
|
|
238 public B f(final Tree<A> t) {
|
|
|
239 return t.foldMap(f, m);
|
|
|
240 }
|
|
|
241 };
|
|
|
242 }
|
|
|
243
|
|
|
244 /**
|
|
|
245 * Builds a tree from a seed value.
|
|
|
246 *
|
|
|
247 * @param f A function with which to build the tree.
|
|
|
248 * @return A function which, given a seed value, yields a tree.
|
|
|
249 */
|
|
|
250 public static <A, B> F<B, Tree<A>> unfoldTree(final F<B, P2<A, P1<Stream<B>>>> f) {
|
|
|
251 return new F<B, Tree<A>>() {
|
|
|
252 public Tree<A> f(final B b) {
|
|
|
253 final P2<A, P1<Stream<B>>> p = f.f(b);
|
|
|
254 return node(p._1(), p._2().map(Stream.<B, Tree<A>>map_().f(unfoldTree(f))));
|
|
|
255 }
|
|
|
256 };
|
|
|
257 }
|
|
|
258
|
|
|
259 /**
|
|
|
260 * Applies the given function to all subtrees of this tree, returning a tree of the results (comonad pattern).
|
|
|
261 *
|
|
|
262 * @param f A function to bind across all the subtrees of this tree.
|
|
|
263 * @return A new tree, with the results of applying the given function to each subtree of this tree. The result
|
|
|
264 * of applying the function to the entire tree is the root label, and the results of applying to the
|
|
|
265 * root's children are labels of the root's subforest, etc.
|
|
|
266 */
|
|
|
267 public <B> Tree<B> cobind(final F<Tree<A>, B> f) {
|
|
|
268 return unfoldTree(new F<Tree<A>, P2<B, P1<Stream<Tree<A>>>>>() {
|
|
|
269 public P2<B, P1<Stream<Tree<A>>>> f(final Tree<A> t) {
|
|
|
270 return P.p(f.f(t), t.subForest());
|
|
|
271 }
|
|
|
272 }).f(this);
|
|
|
273 }
|
|
|
274
|
|
|
275 /**
|
|
|
276 * Expands this tree into a tree of trees, with this tree as the root label, and subtrees as the labels of
|
|
|
277 * child nodes (comonad pattern).
|
|
|
278 *
|
|
|
279 * @return A tree of trees, with this tree as its root label, and subtrees of this tree as the labels of
|
|
|
280 * its child nodes.
|
|
|
281 */
|
|
|
282 public Tree<Tree<A>> cojoin() {
|
|
|
283 final F<Tree<A>, Tree<A>> id = identity();
|
|
|
284 return cobind(id);
|
|
|
285 }
|
|
|
286
|
|
|
287 private static <A> Stream<String> drawSubTrees(final Show<A> s, final Stream<Tree<A>> ts) {
|
|
|
288 return ts.isEmpty() ? Stream.<String>nil()
|
|
|
289 : ts.tail()._1().isEmpty() ? shift("`- ", " ", ts.head().drawTree(s)).cons("|")
|
|
|
290 : shift("+- ", "| ", ts.head().drawTree(s))
|
|
|
291 .append(drawSubTrees(s, ts.tail()._1()));
|
|
|
292 }
|
|
|
293
|
|
|
294 private static Stream<String> shift(final String f, final String o, final Stream<String> s) {
|
|
|
295 return Stream.repeat(o).cons(f).zipWith(s, Monoid.stringMonoid.sum());
|
|
|
296 }
|
|
|
297
|
|
|
298 private Stream<String> drawTree(final Show<A> s) {
|
|
|
299 return drawSubTrees(s, subForest._1()).cons(s.showS(root));
|
|
|
300 }
|
|
|
301
|
|
|
302 /**
|
|
|
303 * Draws a 2-dimensional representation of a tree.
|
|
|
304 *
|
|
|
305 * @param s A show instance for the elements of the tree.
|
|
|
306 * @return a String showing this tree in two dimensions.
|
|
|
307 */
|
|
|
308 public String draw(final Show<A> s) {
|
|
|
309 return Monoid.stringMonoid.join(drawTree(s), "\n");
|
|
|
310 }
|
|
|
311
|
|
|
312 /**
|
|
|
313 * Provides a show instance that draws a 2-dimensional representation of a tree.
|
|
|
314 *
|
|
|
315 * @param s A show instance for the elements of the tree.
|
|
|
316 * @return a show instance that draws a 2-dimensional representation of a tree.
|
|
|
317 */
|
|
|
318 public static <A> Show<Tree<A>> show2D(final Show<A> s) {
|
|
|
319 return Show.showS(new F<Tree<A>, String>() {
|
|
|
320 public String f(final Tree<A> tree) {
|
|
|
321 return tree.draw(s);
|
|
|
322 }
|
|
|
323 });
|
|
|
324 }
|
|
|
325
|
|
|
326 /**
|
|
|
327 * Zips this tree with another, using the given function. The resulting tree is the structural intersection
|
|
|
328 * of the two trees.
|
|
|
329 *
|
|
|
330 * @param bs A tree to zip this tree with.
|
|
|
331 * @param f A function with which to zip together the two trees.
|
|
|
332 * @return A new tree of the results of applying the given function over this tree and the given tree, position-wise.
|
|
|
333 */
|
|
|
334 public <B, C> Tree<C> zipWith(final Tree<B> bs, final F2<A, B, C> f) {
|
|
|
335 return F2Functions.zipTreeM(f).f(this, bs);
|
|
|
336 }
|
|
|
337
|
|
|
338 /**
|
|
|
339 * Zips this tree with another, using the given function. The resulting tree is the structural intersection
|
|
|
340 * of the two trees.
|
|
|
341 *
|
|
|
342 * @param bs A tree to zip this tree with.
|
|
|
343 * @param f A function with which to zip together the two trees.
|
|
|
344 * @return A new tree of the results of applying the given function over this tree and the given tree, position-wise.
|
|
|
345 */
|
|
|
346 public <B, C> Tree<C> zipWith(final Tree<B> bs, final F<A, F<B, C>> f) {
|
|
|
347 return zipWith(bs, uncurryF2(f));
|
|
|
348 }
|
|
|
349
|
|
|
350 /**
|
|
|
351 * Folds a Tree<A> into a Tree<B> by applying the function f from the bottom of the Tree to the top
|
|
|
352 *
|
|
|
353 * @param t A tree to fold from the bottom to the top.
|
|
|
354 * @param f A function transforming the current node and a stream of already transformed nodes (its children) into a new node
|
|
|
355 * @return The folded tree
|
|
|
356 */
|
|
|
357 public static <A, B> Tree<B> bottomUp(Tree<A> t, final F<P2<A, Stream<B>>, B> f) {
|
|
|
358 final F<Tree<A>, Tree<B>> recursiveCall = new F<Tree<A>, Tree<B>>() {
|
|
|
359 @Override public Tree<B> f(Tree<A> a) {
|
|
|
360 return bottomUp(a, f);
|
|
|
361 }
|
|
|
362 };
|
|
|
363
|
|
|
364 final Stream<Tree<B>> tbs = t.subForest()._1().map(recursiveCall);
|
|
|
365 return Tree.node(f.f(P.p(t.root(), tbs.map(Tree.<B> getRoot()))), tbs);
|
|
|
366 }
|
|
|
367
|
|
|
368 /**
|
|
|
369 * @return a function getting the root of a Tree
|
|
|
370 */
|
|
|
371 private static <A> F<Tree<A>, A> getRoot() {
|
|
|
372 return new F<Tree<A>, A>() {
|
|
|
373 @Override public A f(Tree<A> a) {
|
|
|
374 return a.root();
|
|
|
375 }
|
|
|
376 };
|
|
|
377 }
|
|
|
378
|
|
|
379 } |
