Skip to content

Commit 5007203

Browse files
orionllorionll
committed
Fixed some methods that were implemented inefficiently or failed with StackOverflow. Added Ordering.reverse(), Ord.reverse().
1 parent 05f7dbf commit 5007203

File tree

9 files changed

+63
-28
lines changed

9 files changed

+63
-28
lines changed

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

Lines changed: 20 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -157,6 +157,8 @@ public A min(final A a1, final A a2) {
157157
*/
158158
public final F<A, F<A, A>> min = curry((a, a1) -> min(a, a1));
159159

160+
public final Ord<A> reverse() { return ord(Function.flip(f)); }
161+
160162
/**
161163
* Returns an order instance that uses the given equality test and ordering function.
162164
*
@@ -343,14 +345,25 @@ public static <A, B> Ord<Validation<A, B>> validationOrd(final Ord<A> oa, final
343345
*/
344346
public static <A> Ord<List<A>> listOrd(final Ord<A> oa) {
345347
return ord(l1 -> l2 -> {
346-
if (l1.isEmpty())
347-
return l2.isEmpty() ? Ordering.EQ : Ordering.LT;
348-
else if (l2.isEmpty())
349-
return l1.isEmpty() ? Ordering.EQ : Ordering.GT;
350-
else {
351-
final Ordering c = oa.compare(l1.head(), l2.head());
352-
return c == Ordering.EQ ? listOrd(oa).f.f(l1.tail()).f(l2.tail()) : c;
348+
List<A> x1 = l1;
349+
List<A> x2 = l2;
350+
351+
while (x1.isNotEmpty() && x2.isNotEmpty()) {
352+
final Ordering o = oa.compare(x1.head(), x2.head());
353+
if (o == Ordering.LT || o == Ordering.GT) {
354+
return o;
353355
}
356+
x1 = x1.tail();
357+
x2 = x2.tail();
358+
}
359+
360+
if (x1.isEmpty() && x2.isEmpty()) {
361+
return Ordering.EQ;
362+
} else if (x1.isEmpty()) {
363+
return Ordering.LT;
364+
} else {
365+
return Ordering.GT;
366+
}
354367
});
355368
}
356369

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

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,15 @@ public enum Ordering {
2323
GT;
2424

2525
public int toInt() { return ordinal() - 1 ; }
26+
27+
public Ordering reverse() {
28+
switch (this) {
29+
case LT: return GT;
30+
case GT: return LT;
31+
}
32+
return EQ;
33+
}
34+
2635
public static Ordering fromInt(int cmp) {
2736
return cmp == 0 ? EQ : cmp > 0 ? GT : LT;
2837
}

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

Lines changed: 10 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -15,10 +15,8 @@
1515
import fj.P2;
1616
import fj.Show;
1717
import fj.Unit;
18-
import static fj.Function.curry;
19-
import static fj.Function.constant;
20-
import static fj.Function.identity;
21-
import static fj.Function.compose;
18+
19+
import static fj.Function.*;
2220
import static fj.P.p;
2321
import static fj.P.p2;
2422
import static fj.Unit.unit;
@@ -169,9 +167,10 @@ public final Stream<A> toStream() {
169167
*/
170168
@SuppressWarnings({"unchecked"})
171169
public final Array<A> toArray() {
172-
final Object[] a = new Object[length()];
170+
final int length = length();
171+
final Object[] a = new Object[length];
173172
List<A> x = this;
174-
for (int i = 0; i < length(); i++) {
173+
for (int i = 0; i < length; i++) {
175174
a[i] = x.head();
176175
x = x.tail();
177176
}
@@ -629,14 +628,14 @@ public final List<A> append(final List<A> as) {
629628
}
630629

631630
/**
632-
* Performs a right-fold reduction across this list. This function uses O(length) stack space.
631+
* Performs a right-fold reduction across this list.
633632
*
634633
* @param f The function to apply on each element of the list.
635634
* @param b The beginning value to start the application from.
636635
* @return The final result after the right-fold reduction.
637636
*/
638637
public final <B> B foldRight(final F<A, F<B, B>> f, final B b) {
639-
return isEmpty() ? b : f.f(head()).f(tail().foldRight(f, b));
638+
return reverse().foldLeft(flip(f), b);
640639
}
641640

642641
/**
@@ -1581,7 +1580,9 @@ public static <A, B> P2<List<A>, List<B>> unzip(final List<P2<A, B>> xs) {
15811580
* @return A list of the given value replicated the given number of times.
15821581
*/
15831582
public static <A> List<A> replicate(final int n, final A a) {
1584-
return n <= 0 ? List.<A>nil() : replicate(n - 1, a).cons(a);
1583+
List<A> list = List.nil();
1584+
for (int i = 0; i < n; i++) { list = list.cons(a); }
1585+
return list;
15851586
}
15861587

15871588
/**

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

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1233,7 +1233,10 @@ public final A index(final int i) {
12331233
* <code>false</code> otherwise.
12341234
*/
12351235
public final boolean forall(final F<A, Boolean> f) {
1236-
return isEmpty() || f.f(head()) && tail()._1().forall(f);
1236+
for (final A a : this) {
1237+
if (!f.f(a)) return false;
1238+
}
1239+
return true;
12371240
}
12381241

12391242
@Override

‎props-core/src/test/java/fj/data/properties/ListProperties.java‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,10 @@
11
package fj.data.properties;
22

3+
import fj.Ord;
34
import fj.P;
45
import fj.P2;
56
import fj.data.List;
7+
import fj.test.reflect.CheckParams;
68
import fj.test.runner.PropertyTestRunner;
79
import fj.test.Gen;
810
import fj.test.Property;
@@ -18,6 +20,7 @@
1820
* Created by Zheka Kozlov on 02.06.2015.
1921
*/
2022
@RunWith(PropertyTestRunner.class)
23+
@CheckParams(maxSize = 10000)
2124
public class ListProperties {
2225

2326
public Property isPrefixOf() {
@@ -53,4 +56,14 @@ public Property isSuffixOfDifferentHeads() {
5356
return property(arbList(arbInteger), arbList(arbInteger), arbInteger, arbInteger, (list1, list2, h1, h2) ->
5457
implies(intEqual.notEq(h1, h2), () -> prop(!list1.snoc(h1).isSuffixOf(intEqual, list2.snoc(h2)))));
5558
}
59+
60+
public Property listOrdEqual() {
61+
return property(arbList(arbInteger), list -> prop(Ord.listOrd(Ord.intOrd).equal().eq(list, list)));
62+
}
63+
64+
public Property listOrdReverse() {
65+
final Ord<List<Integer>> ord = Ord.listOrd(Ord.intOrd);
66+
return property(arbList(arbInteger), arbList(arbInteger), (list1, list2) ->
67+
prop(ord.compare(list1, list2) == ord.reverse().compare(list1, list2).reverse()));
68+
}
5669
}

‎props-core/src/test/java/fj/data/properties/NonEmptyListProperties.java‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@
55
import fj.P2;
66
import fj.data.List;
77
import fj.data.NonEmptyList;
8+
import fj.test.reflect.CheckParams;
89
import fj.test.runner.PropertyTestRunner;
910
import fj.test.Property;
1011
import org.junit.runner.RunWith;
@@ -28,6 +29,7 @@
2829
* Created by Zheka Kozlov on 02.06.2015.
2930
*/
3031
@RunWith(PropertyTestRunner.class)
32+
@CheckParams(maxSize = 10000)
3133
public class NonEmptyListProperties {
3234

3335
private static final Equal<NonEmptyList<Integer>> eq = nonEmptyListEqual(intEqual);

‎props-core/src/test/java/fj/data/properties/SeqProperties.java‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@
55
import fj.P2;
66
import fj.data.Option;
77
import fj.data.Seq;
8+
import fj.test.reflect.CheckParams;
89
import fj.test.runner.PropertyTestRunner;
910
import fj.test.Arbitrary;
1011
import fj.test.Gen;
@@ -24,6 +25,7 @@
2425
* Created by Zheka Kozlov on 01.06.2015.
2526
*/
2627
@RunWith(PropertyTestRunner.class)
28+
@CheckParams(maxSize = 10000)
2729
public class SeqProperties {
2830

2931
public Property consHead() {

‎quickcheck/src/main/java/fj/test/Gen.java‎

Lines changed: 1 addition & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -337,15 +337,7 @@ public static <A> Gen<A> gen(final F<Integer, F<Rand, A>> f) {
337337
* @return A generator of lists after sequencing the given generators.
338338
*/
339339
public static <A> Gen<List<A>> sequence(final List<Gen<A>> gs) {
340-
return gs.foldRight(new F<Gen<A>, F<Gen<List<A>>, Gen<List<A>>>>() {
341-
public F<Gen<List<A>>, Gen<List<A>>> f(final Gen<A> ga) {
342-
return new F<Gen<List<A>>, Gen<List<A>>>() {
343-
public Gen<List<A>> f(final Gen<List<A>> gas) {
344-
return ga.bind(gas, List.<A>cons());
345-
}
346-
};
347-
}
348-
}, value(List.<A>nil()));
340+
return gen(i -> r -> gs.map(g -> g.gen(i, r)));
349341
}
350342

351343
/**

‎quickcheck/src/main/java/fj/test/reflect/Check.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -273,7 +273,7 @@ public T f(final Constructor<T> ctor) {
273273
ctor.setAccessible(true);
274274
return ctor.newInstance();
275275
} catch(Exception e) {
276-
throw error(e.toString());
276+
throw new Error(e.getMessage(), e);
277277
}
278278
}
279279
});
@@ -324,7 +324,7 @@ public P3<Property, String, Option<CheckParams>> f(final PropertyMember m) {
324324
final String name = fromNull(m.element().getAnnotation(Name.class)).map(nameS).orSome(m.name());
325325
return p(m.invoke(t.orSome(P.<T>p(null))), name, params);
326326
} catch(Exception e) {
327-
throw error(e.toString());
327+
throw new Error(e.getMessage(), e);
328328
}
329329
}
330330
});

0 commit comments

Comments
 (0)