Skip to content

Commit 24703d5

Browse files
mperrymperry
authored
Merge pull request functionaljava#2 from jbgi/pqueue
Improvements for functionaljava/functionaljava#279
2 parents a506f06 + f21c310 commit 24703d5

File tree

5 files changed

+99
-98
lines changed

5 files changed

+99
-98
lines changed

‎core/src/main/java/fj/F1Functions.java‎

Lines changed: 9 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -670,11 +670,18 @@ public static <A, B> ArrayList<B> mapJ(final F<A, B> f, final ArrayList<A> as) {
670670
}
671671

672672
public static <A, B, C> F<A, C> map(F<A, B> target, F<B, C> f) {
673-
return andThen(target, f);
673+
return o(f, target);
674674
}
675675

676676
public static <A, B, C> F<C, B> contramap(F<A, B> target, F<C, A> f) {
677-
return andThen(f, target);
677+
return o(target, f);
678+
}
679+
680+
/**
681+
* Both map (with g) and contramap (with f) the target function. (Profunctor pattern)
682+
*/
683+
public static <A, B, C, D> F<C, D> dimap(F<A, B> target, F<C, A> f, F<B, D> g) {
684+
return c -> g.f(target.f(f.f(c)));
678685
}
679686

680687
}

‎core/src/main/java/fj/Function.java‎

Lines changed: 12 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -718,7 +718,18 @@ public static <A, B, C> F<C, B> bind(final F<C, A> ma, final F<A, F<C, B>> f) {
718718
* @return A new function after applying the given higher-order function to the given function.
719719
*/
720720
public static <A, B, C> F<C, B> apply(final F<C, F<A, B>> cab, final F<C, A> ca) {
721-
return bind(cab, f -> compose(f, ca));
721+
return apply(uncurryF2(cab), ca);
722+
}
723+
724+
/**
725+
* Performs function application within a higher-order function (applicative functor pattern).
726+
*
727+
* @param cab The higher-order function to apply a function to.
728+
* @param ca A function to apply within a higher-order function.
729+
* @return A new function after applying the given higher-order function to the given function.
730+
*/
731+
public static <A, B, C> F<C, B> apply(final F2<C, A, B> cab, final F<C, A> ca) {
732+
return c -> cab.f(c, ca.f(c));
722733
}
723734

724735
/**

‎core/src/main/java/fj/Ord.java‎

Lines changed: 34 additions & 73 deletions
Original file line numberDiff line numberDiff line change
@@ -14,6 +14,8 @@
1414
import java.math.BigInteger;
1515
import java.util.Comparator;
1616

17+
import static fj.Function.apply;
18+
import static fj.Function.compose;
1719
import static fj.Function.curry;
1820
import static fj.Semigroup.semigroup;
1921

@@ -27,6 +29,8 @@ public final class Ord<A> {
2729

2830
private Ord(final F<A, F<A, Ordering>> f) {
2931
this.f = f;
32+
this.max = a1 -> apply((a2, o) -> o == Ordering.GT ? a1 : a2, f.f(a1));
33+
this.min = a1 -> apply((a2, o) -> o == Ordering.LT ? a1 : a2, f.f(a1));
3034
}
3135

3236
/**
@@ -66,7 +70,7 @@ public boolean eq(final A a1, final A a2) {
6670
* @return An <code>Equal</code> for this order.
6771
*/
6872
public Equal<A> equal() {
69-
return Equal.equal(curry(this::eq));
73+
return Equal.equal(a -> compose(o -> o == Ordering.EQ, f.f(a)));
7074
}
7175

7276
/**
@@ -102,7 +106,7 @@ public boolean isLessThan(final A a1, final A a2) {
102106
* <code>false</code> otherwise.
103107
*/
104108
public boolean isLessThanOrEqualTo(final A a1, final A a2) {
105-
return isLessThan(a1, a2) || eq(a1, a2);
109+
return compare(a1, a2) != Ordering.GT;
106110
}
107111

108112
/**
@@ -125,7 +129,7 @@ public boolean isGreaterThan(final A a1, final A a2) {
125129
* @return A function that returns true if its argument is less than the argument to this method.
126130
*/
127131
public F<A, Boolean> isLessThan(final A a) {
128-
return a2 -> compare(a2, a) == Ordering.LT;
132+
return compose(o -> o != Ordering.LT, f.f(a));
129133
}
130134

131135
/**
@@ -135,7 +139,7 @@ public F<A, Boolean> isLessThan(final A a) {
135139
* @return A function that returns true if its argument is greater than the argument to this method.
136140
*/
137141
public F<A, Boolean> isGreaterThan(final A a) {
138-
return a2 -> compare(a2, a) == Ordering.GT;
142+
return compose(o -> o != Ordering.GT, f.f(a));
139143
}
140144

141145
/**
@@ -164,19 +168,19 @@ public A min(final A a1, final A a2) {
164168
/**
165169
* A function that returns the greater of its two arguments.
166170
*/
167-
public final F<A, F<A, A>> max = curry(this::max);
171+
public final F<A, F<A, A>> max;
168172

169173
/**
170174
* A function that returns the lesser of its two arguments.
171175
*/
172-
public final F<A, F<A, A>> min = curry(this::min);
176+
public final F<A, F<A, A>> min;
173177

174178
public final Semigroup<A> minSemigroup() {
175-
return semigroup(this::min);
179+
return semigroup(min);
176180
}
177181

178182
public final Semigroup<A> maxSemigroup() {
179-
return semigroup(this::max);
183+
return semigroup(max);
180184
}
181185

182186
public final Ord<A> reverse() { return ord(Function.flip(f)); }
@@ -194,92 +198,52 @@ public static <A> Ord<A> ord(final F<A, F<A, Ordering>> f) {
194198
/**
195199
* An order instance for the <code>boolean</code> type.
196200
*/
197-
public static final Ord<Boolean> booleanOrd = ord(
198-
a1 -> a2 -> {
199-
final int x = a1.compareTo(a2);
200-
return x < 0 ? Ordering.LT : x == 0 ? Ordering.EQ : Ordering.GT;
201-
});
201+
public static final Ord<Boolean> booleanOrd = comparableOrd();
202202

203203
/**
204204
* An order instance for the <code>byte</code> type.
205205
*/
206-
public static final Ord<Byte> byteOrd = ord(
207-
a1 -> a2 -> {
208-
final int x = a1.compareTo(a2);
209-
return x < 0 ? Ordering.LT : x == 0 ? Ordering.EQ : Ordering.GT;
210-
});
206+
public static final Ord<Byte> byteOrd = comparableOrd();
211207

212208
/**
213209
* An order instance for the <code>char</code> type.
214210
*/
215-
public static final Ord<Character> charOrd = ord(
216-
a1 -> a2 -> {
217-
final int x = a1.compareTo(a2);
218-
return x < 0 ? Ordering.LT : x == 0 ? Ordering.EQ : Ordering.GT;
219-
});
211+
public static final Ord<Character> charOrd = comparableOrd();
220212

221213
/**
222214
* An order instance for the <code>double</code> type.
223215
*/
224-
public static final Ord<Double> doubleOrd = ord(
225-
a1 -> a2 -> {
226-
final int x = a1.compareTo(a2);
227-
return x < 0 ? Ordering.LT : x == 0 ? Ordering.EQ : Ordering.GT;
228-
});
216+
public static final Ord<Double> doubleOrd = comparableOrd();
229217

230218
/**
231219
* An order instance for the <code>float</code> type.
232220
*/
233-
public static final Ord<Float> floatOrd = ord(
234-
a1 -> a2 -> {
235-
final int x = a1.compareTo(a2);
236-
return x < 0 ? Ordering.LT : x == 0 ? Ordering.EQ : Ordering.GT;
237-
});
221+
public static final Ord<Float> floatOrd = comparableOrd();
238222

239223
/**
240224
* An order instance for the <code>int</code> type.
241225
*/
242-
public static final Ord<Integer> intOrd = ord(
243-
a1 -> a2 -> {
244-
final int x = a1.compareTo(a2);
245-
return x < 0 ? Ordering.LT : x == 0 ? Ordering.EQ : Ordering.GT;
246-
});
226+
public static final Ord<Integer> intOrd = comparableOrd();
247227

248228
/**
249229
* An order instance for the <code>BigInteger</code> type.
250230
*/
251-
public static final Ord<BigInteger> bigintOrd = ord(
252-
a1 -> a2 -> {
253-
final int x = a1.compareTo(a2);
254-
return x < 0 ? Ordering.LT : x == 0 ? Ordering.EQ : Ordering.GT;
255-
});
231+
public static final Ord<BigInteger> bigintOrd = comparableOrd();
256232

257233
/**
258234
* An order instance for the <code>BigDecimal</code> type.
259235
*/
260-
public static final Ord<BigDecimal> bigdecimalOrd = ord(
261-
a1 -> a2 -> {
262-
final int x = a1.compareTo(a2);
263-
return x < 0 ? Ordering.LT : x == 0 ? Ordering.EQ : Ordering.GT;
264-
});
236+
public static final Ord<BigDecimal> bigdecimalOrd = comparableOrd();
265237

266238
/**
267239
* An order instance for the <code>long</code> type.
268240
*/
269-
public static final Ord<Long> longOrd = ord(
270-
a1 -> a2 -> {
271-
final int x = a1.compareTo(a2);
272-
return x < 0 ? Ordering.LT : x == 0 ? Ordering.EQ : Ordering.GT;
273-
});
241+
public static final Ord<Long> longOrd = comparableOrd();
274242

275243
/**
276244
* An order instance for the <code>short</code> type.
277245
*/
278-
public static final Ord<Short> shortOrd = ord(
279-
a1 -> a2 -> {
280-
final int x = a1.compareTo(a2);
281-
return x < 0 ? Ordering.LT : x == 0 ? Ordering.EQ : Ordering.GT;
282-
});
246+
public static final Ord<Short> shortOrd = comparableOrd();
283247

284248
/**
285249
* An order instance for the {@link Ordering} type.
@@ -297,23 +261,17 @@ public static <A> Ord<A> ord(final F<A, F<A, Ordering>> f) {
297261
/**
298262
* An order instance for the {@link String} type.
299263
*/
300-
public static final Ord<String> stringOrd = ord(
301-
a1 -> a2 -> {
302-
final int x = a1.compareTo(a2);
303-
return x < 0 ? Ordering.LT : x == 0 ? Ordering.EQ : Ordering.GT;
304-
});
264+
public static final Ord<String> stringOrd = comparableOrd();
305265

306266
/**
307267
* An order instance for the {@link StringBuffer} type.
308268
*/
309-
public static final Ord<StringBuffer> stringBufferOrd =
310-
ord(a1 -> a2 -> stringOrd.compare(a1.toString(), a2.toString()));
269+
public static final Ord<StringBuffer> stringBufferOrd = stringOrd.contramap(StringBuffer::toString);
311270

312271
/**
313272
* An order instance for the {@link StringBuffer} type.
314273
*/
315-
public static final Ord<StringBuilder> stringBuilderOrd =
316-
ord(a1 -> a2 -> stringOrd.compare(a1.toString(), a2.toString()));
274+
public static final Ord<StringBuilder> stringBuilderOrd = stringOrd.contramap(StringBuilder::toString);
317275

318276
/**
319277
* An order instance for the {@link Option} type.
@@ -527,9 +485,9 @@ public static <A extends Comparable<A>> Ord<A> comparableOrd() {
527485
* @see #hashEqualsOrd()
528486
*/
529487
public static <A> Ord<A> hashOrd() {
530-
return ord(a -> a2 -> {
531-
final int x = a.hashCode() - a2.hashCode();
532-
return x < 0 ? Ordering.LT : x == 0 ? Ordering.EQ : Ordering.GT;
488+
return ord(a -> {
489+
int aHash = a.hashCode();
490+
return a2 -> Ordering.fromInt(Integer.compare(aHash, a2.hashCode()));
533491
});
534492
}
535493

@@ -541,9 +499,12 @@ public static <A> Ord<A> hashOrd() {
541499
* @return An order instance that is based on {@link Object#hashCode()} and {@link Object#equals}.
542500
*/
543501
public static <A> Ord<A> hashEqualsOrd() {
544-
return ord(a -> a2 -> {
545-
final int x = a.hashCode() - a2.hashCode();
546-
return x < 0 ? Ordering.LT : x == 0 && a.equals(a2) ? Ordering.EQ : Ordering.GT;
502+
return ord(a -> {
503+
int aHash = a.hashCode();
504+
return a2 -> {
505+
final int a2Hash = a2.hashCode();
506+
return aHash < a2Hash ? Ordering.LT : aHash == a2Hash && a.equals(a2) ? Ordering.EQ : Ordering.GT;
507+
};
547508
});
548509
}
549510

‎core/src/main/java/fj/data/PriorityQueue.java‎

Lines changed: 32 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -2,15 +2,17 @@
22

33
import fj.Equal;
44
import fj.F;
5+
import fj.F2;
56
import fj.Monoid;
67
import fj.Ord;
78
import fj.P;
89
import fj.P2;
9-
import fj.P3;
1010
import fj.Show;
1111
import fj.data.fingertrees.FingerTree;
1212

13-
import static fj.data.List.list;
13+
import static fj.Function.compose;
14+
import static fj.data.Option.none;
15+
import static fj.data.Option.some;
1416

1517
/**
1618
* A priority queue implementation backed by a
@@ -91,22 +93,17 @@ public boolean isEmpty() {
9193
* If the tree is not empty, returns the node with highest priority otherwise returns nothing.
9294
*/
9395
public Option<P2<K, A>> top() {
94-
K top = ftree.measure();
95-
P2<FingerTree<K, P2<K, A>>, FingerTree<K, P2<K, A>>> p = ftree.split(k -> equal.eq(top, k));
96-
return p._2().headOption();
96+
return unqueue(none(), (top, tail) -> some(top));
9797
}
9898

9999
/**
100100
* Returns all the elements of the queue with the highest (same) priority.
101101
*/
102102
public List<P2<K, A>> topN() {
103-
Stream<P2<K, A>> s = toStream();
104-
if (s.isEmpty()) {
105-
return List.nil();
106-
} else {
107-
final K k = s.head()._1();
108-
return s.takeWhile(p -> equal.eq(k, p._1())).toList();
109-
}
103+
return toStream().uncons(
104+
List.nil(),
105+
top -> tail -> List.cons(top, tail._1().takeWhile(compose(equal.eq(top._1()), P2.__1())).toList())
106+
);
110107
}
111108

112109
/**
@@ -127,7 +124,7 @@ public PriorityQueue<K, A> enqueue(List<P2<K, A>> list) {
127124
* Does the priority k exist already?
128125
*/
129126
public boolean contains(final K k) {
130-
return !ftree.split(k2 -> equal.eq(k, k2))._2().isEmpty();
127+
return !ftree.split(equal.eq(k))._2().isEmpty();
131128
}
132129

133130
/**
@@ -152,17 +149,30 @@ public PriorityQueue<K, A> enqueue(P2<K, A> p) {
152149
* Removes the node with the highest priority.
153150
*/
154151
public PriorityQueue<K, A> dequeue() {
155-
K top = ftree.measure();
156-
P2<FingerTree<K, P2<K, A>>, FingerTree<K, P2<K, A>>> p = ftree.split(k -> equal.eq(k, top));
157-
FingerTree<K, P2<K, A>> right = p._2();
158-
return right.isEmpty() ? this : priorityQueue(equal, p._1().append(right.tail()));
152+
return unqueue(this, (top, tail) -> tail);
159153
}
160154

161155
/**
162156
* Returns a tuple of the node with the highest priority and the rest of the priority queue.
163157
*/
164158
public P2<Option<P2<K, A>>, PriorityQueue<K, A>> topDequeue() {
165-
return P.p(top(), dequeue());
159+
return unqueue(P.p(none(), this), (top, tail) -> P.p(some(top), tail));
160+
}
161+
162+
/**
163+
* Performs a reduction on this priority queue using the given arguments.
164+
*
165+
* @param empty The value to return if this queue is empty.
166+
* @param topDequeue The function to apply to the top priority element and the tail of the queue (without its top element).
167+
* @return A reduction on this queue.
168+
*/
169+
public <B> B unqueue(B empty, F2<P2<K, A>, PriorityQueue<K, A>, B> topDequeue) {
170+
K top = ftree.measure();
171+
P2<FingerTree<K, P2<K, A>>, FingerTree<K, P2<K, A>>> p = ftree.split(equal.eq(top));
172+
return p._2().uncons(
173+
empty,
174+
(head, tail) -> topDequeue.f(head, priorityQueue(equal, p._1().append(tail)))
175+
);
166176
}
167177

168178
/**
@@ -182,22 +192,22 @@ public PriorityQueue<K, A> dequeue(int n) {
182192
* Does the top of the queue have lower priority than k?
183193
*/
184194
public boolean isLessThan(Ord<K> ok, K k) {
185-
return top().map(p -> ok.isLessThan(p._1(), k)).orSome(true);
195+
return top().option(true, p -> ok.isLessThan(p._1(), k));
186196
}
187197

188198
public boolean isGreaterThan(Ord<K> ok, K k) {
189-
return top().map(p -> ok.isGreaterThan(p._1(), k)).orSome(false);
199+
return top().option(false, p -> ok.isGreaterThan(p._1(), k));
190200
}
191201

192202
public boolean isEqual(Ord<K> ok, K k) {
193-
return top().map(p -> ok.eq(p._1(), k)).orSome(false);
203+
return top().option(false, p -> ok.eq(p._1(), k));
194204
}
195205

196206
/**
197207
* Returns a stream of products with priority k and value a.
198208
*/
199209
public Stream<P2<K, A>> toStream() {
200-
return top().map(p -> Stream.cons(p, () -> dequeue().toStream())).orSome(() -> Stream.nil());
210+
return unqueue(Stream.nil(), (top, tail) -> Stream.cons(top, () -> tail.toStream()));
201211
}
202212

203213
/**

0 commit comments

Comments
 (0)