Mercurial > hg > Members > tatsuki > functionaljava-master > core
comparison src/main/java/fj/data/Tree.java @ 0:fe80c1edf1be
add getLoop
author | tatsuki |
---|---|
date | Fri, 20 Mar 2015 21:04:03 +0900 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:fe80c1edf1be |
---|---|
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 } |