forked from functionaljava/functionaljava
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathZipper.java
More file actions
617 lines (563 loc) · 21.1 KB
/
Zipper.java
File metadata and controls
617 lines (563 loc) · 21.1 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
package fj.data;
import fj.Equal;
import fj.F;
import fj.F2;
import fj.F3;
import fj.Function;
import fj.Ord;
import fj.P;
import fj.P1;
import fj.P2;
import fj.P3;
import fj.Show;
import fj.function.Integers;
import java.util.Iterator;
import static fj.Function.compose;
import static fj.Function.curry;
import static fj.Function.flip;
import static fj.Function.join;
import static fj.Function.uncurryF2;
import static fj.data.Option.none;
import static fj.data.Option.some;
import static fj.data.Stream.nil;
import static fj.data.Stream.repeat;
/**
* Provides a pointed stream, which is a non-empty zipper-like stream structure that tracks an index (focus)
* position in a stream. Focus can be moved forward and backwards through the stream, elements can be inserted
* before or after the focused position, and the focused item can be deleted.
* <p/>
* Based on the pointedlist library by Jeff Wheeler.
*/
public final class Zipper<A> implements Iterable<Zipper<A>> {
private final Stream<A> left;
private final A focus;
private final Stream<A> right;
private Zipper(final Stream<A> left, final A focus, final Stream<A> right) {
this.left = left;
this.focus = focus;
this.right = right;
}
/**
* Creates a new Zipper with the given streams before and after the focus, and the given focused item.
*
* @param left The stream of elements before the focus.
* @param focus The element under focus.
* @param right The stream of elements after the focus.
* @return a new Zipper with the given streams before and after the focus, and the given focused item.
*/
public static <A> Zipper<A> zipper(final Stream<A> left, final A focus, final Stream<A> right) {
return new Zipper<A>(left, focus, right);
}
/**
* Creates a new Zipper from the given triple.
*
* @param p A triple of the elements before the focus, the focus element, and the elements after the focus,
* respectively.
* @return a new Zipper created from the given triple.
*/
public static <A> Zipper<A> zipper(final P3<Stream<A>, A, Stream<A>> p) {
return new Zipper<A>(p._1(), p._2(), p._3());
}
/**
* First-class constructor of zippers.
*
* @return A function that yields a new zipper given streams on the left and right and a focus element.
*/
public static <A> F3<Stream<A>, A, Stream<A>, Zipper<A>> zipper() {
return new F3<Stream<A>, A, Stream<A>, Zipper<A>>() {
public Zipper<A> f(final Stream<A> l, final A a, final Stream<A> r) {
return zipper(l, a, r);
}
};
}
/**
* Returns the product-3 representation of this Zipper.
*
* @return the product-3 representation of this Zipper.
*/
public P3<Stream<A>, A, Stream<A>> p() {
return P.p(left, focus, right);
}
/**
* A first-class function that yields the product-3 representation of a given Zipper.
*
* @return A first-class function that yields the product-3 representation of a given Zipper.
*/
public static <A> F<Zipper<A>, P3<Stream<A>, A, Stream<A>>> p_() {
return new F<Zipper<A>, P3<Stream<A>, A, Stream<A>>>() {
public P3<Stream<A>, A, Stream<A>> f(final Zipper<A> a) {
return a.p();
}
};
}
/**
* An Ord instance for Zippers.
*
* @param o An Ord instance for the element type.
* @return An Ord instance for Zippers.
*/
public static <A> Ord<Zipper<A>> ord(final Ord<A> o) {
final Ord<Stream<A>> so = Ord.streamOrd(o);
return Ord.p3Ord(so, o, so).comap(Zipper.<A>p_());
}
/**
* An Equal instance for Zippers.
*
* @param e An Equal instance for the element type.
* @return An Equal instance for Zippers.
*/
public static <A> Equal<Zipper<A>> eq(final Equal<A> e) {
final Equal<Stream<A>> se = Equal.streamEqual(e);
return Equal.p3Equal(se, e, se).comap(Zipper.<A>p_());
}
/**
* A Show instance for Zippers.
*
* @param s A Show instance for the element type.
* @return A Show instance for Zippers.
*/
public static <A> Show<Zipper<A>> show(final Show<A> s) {
final Show<Stream<A>> ss = Show.streamShow(s);
return Show.p3Show(ss, s, ss).comap(Zipper.<A>p_());
}
/**
* Maps the given function across the elements of this zipper (covariant functor pattern).
*
* @param f A function to map across this zipper.
* @return A new zipper with the given function applied to all elements.
*/
public <B> Zipper<B> map(final F<A, B> f) {
return zipper(left.map(f), f.f(focus), right.map(f));
}
/**
* Performs a right-fold reduction across this zipper.
*
* @param f The function to apply on each element of this zipper.
* @param z The beginning value to start the application from.
* @return the final result after the right-fold reduction.
*/
public <B> B foldRight(final F<A, F<B, B>> f, final B z) {
return left.foldLeft(flip(f),
right.cons(focus).foldRight(compose(
Function.<P1<B>, B, B>andThen().f(P1.<B>__1()), f), z));
}
/**
* Creates a new zipper with a single element.
*
* @param a The focus element of the new zipper.
* @return a new zipper with a single element which is in focus.
*/
public static <A> Zipper<A> single(final A a) {
return zipper(Stream.<A>nil(), a, Stream.<A>nil());
}
/**
* Possibly create a zipper if the provided stream has at least one element, otherwise None.
* The provided stream's head will be the focus of the zipper, and the rest of the stream will follow
* on the right side.
*
* @param a The stream from which to create a zipper.
* @return a new zipper if the provided stream has at least one element, otherwise None.
*/
@SuppressWarnings({"IfMayBeConditional"})
public static <A> Option<Zipper<A>> fromStream(final Stream<A> a) {
if (a.isEmpty())
return none();
else
return some(zipper(Stream.<A>nil(), a.head(), a.tail()._1()));
}
/**
* Possibly create a zipper if the provided stream has at least one element, otherwise None.
* The provided stream's last element will be the focus of the zipper, following the rest of the stream in order,
* to the left.
*
* @param a The stream from which to create a zipper.
* @return a new zipper if the provided stream has at least one element, otherwise None.
*/
public static <A> Option<Zipper<A>> fromStreamEnd(final Stream<A> a) {
if (a.isEmpty())
return none();
else {
final Stream<A> xs = a.reverse();
return some(zipper(xs.tail()._1(), xs.head(), Stream.<A>nil()));
}
}
/**
* Returns the focus element of this zipper.
*
* @return the focus element of this zipper.
*/
public A focus() {
return focus;
}
/**
* Possibly moves the focus to the next element in the list.
*
* @return An optional zipper with the focus moved one element to the right, if there are elements to the right of
* focus, otherwise None.
*/
public Option<Zipper<A>> next() {
return right.isEmpty() ? Option.<Zipper<A>>none() : some(tryNext());
}
/**
* Attempts to move the focus to the next element, or throws an error if there are no more elements.
*
* @return A zipper with the focus moved one element to the right, if there are elements to the right of
* focus, otherwise throws an error.
*/
public Zipper<A> tryNext() {
if (right.isEmpty())
throw new Error("Tried next at the end of a zipper.");
else
return zipper(left.cons(focus), right.head(), right.tail()._1());
}
/**
* Possibly moves the focus to the previous element in the list.
*
* @return An optional zipper with the focus moved one element to the left, if there are elements to the left of
* focus, otherwise None.
*/
public Option<Zipper<A>> previous() {
return left.isEmpty() ? Option.<Zipper<A>>none() : some(tryPrevious());
}
/**
* Attempts to move the focus to the previous element, or throws an error if there are no more elements.
*
* @return A zipper with the focus moved one element to the left, if there are elements to the left of
* focus, otherwise throws an error.
*/
public Zipper<A> tryPrevious() {
if (left.isEmpty())
throw new Error("Tried previous at the beginning of a zipper.");
else
return zipper(left.tail()._1(), left.head(), right.cons(focus));
}
/**
* First-class version of the next() function.
*
* @return A function that moves the given zipper's focus to the next element.
*/
public static <A> F<Zipper<A>, Option<Zipper<A>>> next_() {
return new F<Zipper<A>, Option<Zipper<A>>>() {
public Option<Zipper<A>> f(final Zipper<A> as) {
return as.next();
}
};
}
/**
* First-class version of the previous() function.
*
* @return A function that moves the given zipper's focus to the previous element.
*/
public static <A> F<Zipper<A>, Option<Zipper<A>>> previous_() {
return new F<Zipper<A>, Option<Zipper<A>>>() {
public Option<Zipper<A>> f(final Zipper<A> as) {
return as.previous();
}
};
}
/**
* Inserts an element to the left of the focus, then moves the focus to the new element.
*
* @param a A new element to insert into this zipper.
* @return A new zipper with the given element in focus, and the current focus element on its right.
*/
public Zipper<A> insertLeft(final A a) {
return zipper(left, a, right.cons(focus));
}
/**
* Inserts an element to the right of the focus, then moves the focus to the new element.
*
* @param a A new element to insert into this zipper.
* @return A new zipper with the given element in focus, and the current focus element on its left.
*/
public Zipper<A> insertRight(final A a) {
return zipper(left.cons(focus), a, right);
}
/**
* Possibly deletes the element at the focus, then moves the element on the left into focus.
* If no element is on the left, focus on the element to the right.
* Returns None if the focus element is the only element in this zipper.
*
* @return A new zipper with this zipper's focus element removed, or None if deleting the focus element
* would cause the zipper to be empty.
*/
public Option<Zipper<A>> deleteLeft() {
return left.isEmpty() && right.isEmpty()
? Option.<Zipper<A>>none()
: some(zipper(left.isEmpty() ? left : left.tail()._1(),
left.isEmpty() ? right.head() : left.head(),
left.isEmpty() ? right.tail()._1() : right));
}
/**
* Possibly deletes the element at the focus, then moves the element on the right into focus.
* If no element is on the right, focus on the element to the left.
* Returns None if the focus element is the only element in this zipper.
*
* @return A new zipper with this zipper's focus element removed, or None if deleting the focus element
* would cause the zipper to be empty.
*/
public Option<Zipper<A>> deleteRight() {
return left.isEmpty() && right.isEmpty()
? Option.<Zipper<A>>none()
: some(zipper(right.isEmpty() ? left.tail()._1() : left,
right.isEmpty() ? left.head() : right.head(),
right.isEmpty() ? right : right.tail()._1()));
}
/**
* Deletes all elements in the zipper except the focus.
*
* @return A new zipper with the focus element as the only element.
*/
public Zipper<A> deleteOthers() {
final Stream<A> nil = nil();
return zipper(nil, focus, nil);
}
/**
* Returns the length of this zipper.
*
* @return the length of this zipper.
*/
public int length() {
return foldRight(Function.<A, F<Integer, Integer>>constant(Integers.add.f(1)), 0);
}
/**
* Returns whether the focus is on the first element.
*
* @return true if the focus is on the first element, otherwise false.
*/
public boolean atStart() {
return left.isEmpty();
}
/**
* Returns whether the focus is on the last element.
*
* @return true if the focus is on the last element, otherwise false.
*/
public boolean atEnd() {
return right.isEmpty();
}
/**
* Creates a zipper of variations of this zipper, in which each element is focused,
* with this zipper as the focus of the zipper of zippers (comonad pattern).
*
* @return a zipper of variations of the provided zipper, in which each element is focused,
* with this zipper as the focus of the zipper of zippers.
*/
public Zipper<Zipper<A>> positions() {
final Stream<Zipper<A>> left = Stream.unfold(
new F<Zipper<A>, Option<P2<Zipper<A>, Zipper<A>>>>() {
public Option<P2<Zipper<A>, Zipper<A>>> f(final Zipper<A> p) {
return p.previous().map(join(P.<Zipper<A>, Zipper<A>>p2()));
}
}, this);
final Stream<Zipper<A>> right = Stream.unfold(
new F<Zipper<A>, Option<P2<Zipper<A>, Zipper<A>>>>() {
public Option<P2<Zipper<A>, Zipper<A>>> f(final Zipper<A> p) {
return p.next().map(join(P.<Zipper<A>, Zipper<A>>p2()));
}
}, this);
return zipper(left, this, right);
}
/**
* Maps over variations of this zipper, such that the given function is applied to each variation (comonad pattern).
*
* @param f The comonadic function to apply for each variation of this zipper.
* @return A new zipper, with the given function applied for each variation of this zipper.
*/
public <B> Zipper<B> cobind(final F<Zipper<A>, B> f) {
return positions().map(f);
}
/**
* Zips the elements of this zipper with a boolean that indicates whether that element has focus.
* All of the booleans will be false, except the focused element.
*
* @return A new zipper of pairs, with each element of this zipper paired with a boolean that is true if that
* element has focus, and false otherwise.
*/
public Zipper<P2<A, Boolean>> zipWithFocus() {
return zipper(left.zip(repeat(false)), P.p(focus, true), right.zip(repeat(false)));
}
/**
* Move the focus to the specified index.
*
* @param n The index to which to move the focus.
* @return A new zipper with the focus moved to the specified index, or none if there is no such index.
*/
public Option<Zipper<A>> move(final int n) {
final int ll = left.length();
final int rl = right.length();
Option<Zipper<A>> p = some(this);
if (n < 0 || n >= length())
return none();
else if (ll >= n)
for (int i = ll - n; i > 0; i--)
p = p.bind(Zipper.<A>previous_());
else if (rl >= n)
for (int i = rl - n; i > 0; i--)
p = p.bind(Zipper.<A>next_());
return p;
}
/**
* A first-class version of the move function.
*
* @return A function that moves the focus of the given zipper to the given index.
*/
public static <A> F<Integer, F<Zipper<A>, Option<Zipper<A>>>> move() {
return curry(new F2<Integer, Zipper<A>, Option<Zipper<A>>>() {
public Option<Zipper<A>> f(final Integer i, final Zipper<A> a) {
return a.move(i);
}
});
}
/**
* Moves the focus to the element matching the given predicate, if present.
*
* @param p A predicate to match.
* @return A new zipper with the nearest matching element focused if it is present in this zipper.
*/
public Option<Zipper<A>> find(final F<A, Boolean> p) {
if (p.f(focus()))
return some(this);
else {
final Zipper<Zipper<A>> ps = positions();
return ps.lefts().interleave(ps.rights()).find(new F<Zipper<A>, Boolean>() {
public Boolean f(final Zipper<A> zipper) {
return p.f(zipper.focus());
}
});
}
}
/**
* Returns the index of the focus.
*
* @return the index of the focus.
*/
public int index() {
return left.length();
}
/**
* Move the focus to the next element. If the last element is focused, loop to the first element.
*
* @return A new zipper with the next element focused, unless the last element is currently focused, in which case
* the first element becomes focused.
*/
public Zipper<A> cycleNext() {
if (left.isEmpty() && right.isEmpty())
return this;
else if (right.isEmpty()) {
final Stream<A> xs = left.reverse();
return zipper(Stream.<A>nil(), xs.head(), xs.tail()._1().snoc(P.p(focus)));
} else
return tryNext();
}
/**
* Move the focus to the previous element. If the first element is focused, loop to the last element.
*
* @return A new zipper with the previous element focused, unless the first element is currently focused,
* in which case the last element becomes focused.
*/
public Zipper<A> cyclePrevious() {
if (left.isEmpty() && right.isEmpty())
return this;
else if (left.isEmpty()) {
final Stream<A> xs = right.reverse();
return zipper(xs.tail()._1().snoc(P.p(focus)), xs.head(), Stream.<A>nil());
} else
return tryPrevious();
}
/**
* Possibly deletes the element at the focus, then move the element on the left into focus. If no element is on the
* left, focus on the last element. If the deletion will cause the list to be empty, return None.
*
* @return A new zipper with the focused element removed, and focus on the previous element to the left, or the last
* element if there is no element to the left.
*/
public Option<Zipper<A>> deleteLeftCycle() {
if (left.isEmpty() && right.isEmpty())
return none();
else if (left.isNotEmpty())
return some(zipper(left.tail()._1(), left.head(), right));
else {
final Stream<A> xs = right.reverse();
return some(zipper(xs.tail()._1(), xs.head(), Stream.<A>nil()));
}
}
/**
* Possibly deletes the element at the focus, then move the element on the right into focus. If no element is on the
* right, focus on the first element. If the deletion will cause the list to be empty, return None.
*
* @return A new zipper with the focused element removed, and focus on the next element to the right, or the first
* element if there is no element to the right.
*/
public Option<Zipper<A>> deleteRightCycle() {
if (left.isEmpty() && right.isEmpty())
return none();
else if (right.isNotEmpty())
return some(zipper(left, right.head(), right.tail()._1()));
else {
final Stream<A> xs = left.reverse();
return some(zipper(Stream.<A>nil(), xs.head(), xs.tail()._1()));
}
}
/**
* Replaces the element in focus with the given element.
*
* @param a An element to replace the focused element with.
* @return A new zipper with the given element in focus.
*/
public Zipper<A> replace(final A a) {
return zipper(left, a, right);
}
/**
* Returns the Stream representation of this zipper.
*
* @return A stream that contains all the elements of this zipper.
*/
public Stream<A> toStream() {
return left.reverse().snoc(P.p(focus)).append(right);
}
/**
* Returns a Stream of the elements to the left of focus.
*
* @return a Stream of the elements to the left of focus.
*/
public Stream<A> lefts() {
return left;
}
/**
* Returns a Stream of the elements to the right of focus.
*
* @return a Stream of the elements to the right of focus.
*/
public Stream<A> rights() {
return right;
}
/**
* Zips this Zipper with another, applying the given function lock-step over both zippers in both directions.
* The structure of the resulting Zipper is the structural intersection of the two Zippers.
*
* @param bs A Zipper to zip this one with.
* @param f A function with which to zip together the two Zippers.
* @return The result of applying the given function over this Zipper and the given Zipper, location-wise.
*/
public <B, C> Zipper<C> zipWith(final Zipper<B> bs, final F2<A, B, C> f) {
return f.zipZipperM().f(this, bs);
}
/**
* Zips this Zipper with another, applying the given function lock-step over both zippers in both directions.
* The structure of the resulting Zipper is the structural intersection of the two Zippers.
*
* @param bs A Zipper to zip this one with.
* @param f A function with which to zip together the two Zippers.
* @return The result of applying the given function over this Zipper and the given Zipper, location-wise.
*/
public <B, C> Zipper<C> zipWith(final Zipper<B> bs, final F<A, F<B, C>> f) {
return zipWith(bs, uncurryF2(f));
}
/**
* Returns an iterator of all the positions of this Zipper, starting from the leftmost position.
*
* @return An iterator of all the positions of this Zipper, starting from the leftmost position.
*/
public Iterator<Zipper<A>> iterator() { return positions().toStream().iterator(); }
}