Skip to content

Commit e287a58

Browse files
jbgijbgi
authored
Merge pull request functionaljava#391 from yaroslavok/set_intersection_monoid
Implement intersection monoid and semigroup
2 parents eedeb3d + dc9e0a9 commit e287a58

File tree

6 files changed

+161
-15
lines changed

6 files changed

+161
-15
lines changed

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

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
package fj;
2+
3+
/**
4+
* The Bounded class is used to name the upper and lower limits of a type.
5+
* Ord is not a superclass of Bounded since types that are not totally ordered may also have upper and lower bounds.
6+
*/
7+
public final class Bounded<A> {
8+
9+
private final Definition<A> def;
10+
11+
/**
12+
* Minimal definition of Bounded
13+
*/
14+
public interface Definition<A> {
15+
A min();
16+
17+
A max();
18+
}
19+
20+
private Bounded(Definition<A> definition) {
21+
this.def = definition;
22+
}
23+
24+
public A min() {
25+
return def.min();
26+
}
27+
28+
public A max() {
29+
return def.max();
30+
}
31+
32+
public static <A> Bounded<A> boundedDef(Definition<A> def) {
33+
return new Bounded<>(def);
34+
}
35+
36+
public static <A> Bounded<A> bounded(A min, A max) {
37+
return boundedDef(new Definition<A>() {
38+
@Override
39+
public A min() {
40+
return min;
41+
}
42+
43+
@Override
44+
public A max() {
45+
return max;
46+
}
47+
});
48+
}
49+
50+
}

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

Lines changed: 23 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -2,14 +2,7 @@
22

33
import static fj.F1Functions.dimap;
44

5-
import fj.data.Array;
6-
import fj.data.DList;
7-
import fj.data.List;
8-
import fj.data.IO;
9-
import fj.data.Natural;
10-
import fj.data.Option;
11-
import fj.data.Set;
12-
import fj.data.Stream;
5+
import fj.data.*;
136

147
import static fj.Function.*;
158
import static fj.Semigroup.semigroupDef;
@@ -1090,7 +1083,7 @@ public Unit append(Unit a1, Unit a2) {
10901083
});
10911084

10921085
/**
1093-
* A monoid for sets.
1086+
* A union monoid for sets.
10941087
*
10951088
* @param o An order for set elements.
10961089
* @return A monoid for sets whose elements have the given order.
@@ -1109,6 +1102,27 @@ public Set<A> append(Set<A> a1, Set<A> a2) {
11091102
});
11101103
}
11111104

1105+
/**
1106+
* A intersection monoid for sets.
1107+
*
1108+
* @param bounded A bound for all possible elements
1109+
* @param enumerator An enumerator for all possible elements
1110+
* @return A monoid for sets whose elements have the given order.
1111+
*/
1112+
public static <A> Monoid<Set<A>> setIntersectionMonoid(final Bounded<A> bounded, final Enumerator<A> enumerator) {
1113+
return monoidDef(new Definition<Set<A>>() {
1114+
@Override
1115+
public Set<A> empty() {
1116+
return Set.iteratorSet(enumerator.order(), enumerator.toStream(bounded).iterator());
1117+
}
1118+
1119+
@Override
1120+
public Set<A> append(Set<A> a1, Set<A> a2) {
1121+
return a1.intersect(a2);
1122+
}
1123+
});
1124+
}
1125+
11121126
/**
11131127
* A monoid for the maximum of elements with ordering o.
11141128
* @deprecated since 4.7. Use {@link Ord#maxMonoid(Object)}

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

Lines changed: 10 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -621,12 +621,21 @@ public static <A> Semigroup<IO<A>> ioSemigroup(final Semigroup <A> sa) {
621621
public static final Semigroup<Unit> unitSemigroup = unitMonoid.semigroup();
622622

623623
/**
624-
* A semigroup for sets.
624+
* A union semigroup for sets.
625625
*
626626
* @return a semigroup for sets.
627627
*/
628628
public static <A> Semigroup<Set<A>> setSemigroup() {
629629
return semigroupDef(Set::union);
630630
}
631631

632+
/**
633+
* A intersection semigroup for sets.
634+
*
635+
* @return a semigroup for sets.
636+
*/
637+
public static <A> Semigroup<Set<A>> setIntersectionSemigroup() {
638+
return semigroupDef(Set::intersect);
639+
}
640+
632641
}

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

Lines changed: 13 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,16 +1,12 @@
11
package fj.data;
22

3-
import fj.F;
3+
import fj.*;
44

55
import static fj.Function.*;
66
import static fj.data.Option.none;
77
import static fj.data.Option.some;
88

9-
import fj.Function;
10-
import fj.Ord;
11-
129
import static fj.Ord.*;
13-
import fj.Ordering;
1410
import static fj.Ordering.*;
1511

1612
import java.math.BigDecimal;
@@ -185,6 +181,18 @@ public Stream<A> toStream(final A a) {
185181
return Stream.fromFunction(this, id, a);
186182
}
187183

184+
/**
185+
* Returns a stream of the values from this enumerator,
186+
* starting at the min of given Bounded, ending at the max, counting up.
187+
*
188+
* @param bounded A value at which to begin the stream.
189+
* @return a stream of the values from this enumerator, cut by bounded, counting up.
190+
*/
191+
public Stream<A> toStream(final Bounded<A> bounded) {
192+
final F<A, A> id = identity();
193+
return Stream.fromFunction(this, id, bounded.min()).takeWhile(item -> order.isLessThanOrEqualTo(item, bounded.max()));
194+
}
195+
188196
/**
189197
* Create a new enumerator with the given minimum value.
190198
*

‎core/src/test/java/fj/MonoidTest.java

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,8 @@
11
package fj;
22

3+
import fj.data.Enumerator;
34
import fj.data.Option;
5+
import fj.data.Set;
46
import fj.data.Stream;
57
import org.junit.Test;
68

@@ -16,4 +18,41 @@ public void lifted_sum_of_two_numbers() {
1618
assertThat(optionMonoid.sum(some(3), some(5)), is(some(8)));
1719
assertThat(optionMonoid.sumLeft(Stream.arrayStream(some(3), some(5))), is(some(8)));
1820
}
21+
22+
@Test
23+
public void intersection_monoid_test() {
24+
Bounded<Integer> integersBounded = Bounded.bounded(0, 10);
25+
Monoid<Set<Integer>> intersectionMonoid = Monoid.setIntersectionMonoid(integersBounded, Enumerator.intEnumerator);
26+
Set<Integer> first = Set.set(Ord.intOrd, 1, 2, 3, 4);
27+
Set<Integer> second = Set.set(Ord.intOrd, 3, 4, 5, 6);
28+
Set<Integer> actual = intersectionMonoid.sum(first, second);
29+
assertThat(actual, is(Set.set(Ord.intOrd, 3, 4)));
30+
}
31+
32+
@Test
33+
public void union_monoid_test() {
34+
Monoid<Set<Integer>> unionMonoid = Monoid.setMonoid(Ord.intOrd);
35+
Set<Integer> first = Set.set(Ord.intOrd, 1, 2, 3, 4);
36+
Set<Integer> second = Set.set(Ord.intOrd, 3, 4, 5, 6);
37+
Set<Integer> actual = unionMonoid.sum(first, second);
38+
assertThat(actual, is(Set.set(Ord.intOrd, 1, 2, 3, 4, 5, 6)));
39+
}
40+
41+
@Test
42+
public void intersection_monoid_zero_test() {
43+
Bounded<Integer> integersBounded = Bounded.bounded(0, 10);
44+
Monoid<Set<Integer>> monoid = Monoid.setIntersectionMonoid(integersBounded, Enumerator.intEnumerator);
45+
Set<Integer> set = Set.set(Ord.intOrd, 7, 8, 9, 10);
46+
Set<Integer> zero = monoid.zero();
47+
assertThat(monoid.sum(zero, set), is(set));
48+
}
49+
50+
@Test
51+
public void union_monoid_zero_test() {
52+
Monoid<Set<Integer>> monoid = Monoid.setMonoid(Ord.intOrd);
53+
Set<Integer> set = Set.set(Ord.intOrd, 1, 2, 3, 4);
54+
Set<Integer> zero = monoid.zero();
55+
assertThat(monoid.sum(zero, set), is(set));
56+
}
57+
1958
}

‎core/src/test/java/fj/SemigroupTest.java

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package fj;
2+
3+
import fj.data.Set;
4+
import org.junit.Test;
5+
6+
import static org.hamcrest.core.Is.is;
7+
import static org.hamcrest.MatcherAssert.assertThat;
8+
9+
public class SemigroupTest {
10+
11+
@Test
12+
public void intersection_semigroup_test() {
13+
Semigroup<Set<Integer>> intersectionSemigroup = Semigroup.setIntersectionSemigroup();
14+
Set<Integer> first = Set.set(Ord.intOrd, 1, 2, 3, 4);
15+
Set<Integer> second = Set.set(Ord.intOrd, 3, 4, 5, 6);
16+
assertThat(intersectionSemigroup.sum(first, second), is(Set.set(Ord.intOrd, 3, 4)));
17+
}
18+
19+
@Test
20+
public void union_semigroup_test() {
21+
Semigroup<Set<Integer>> unionSemigroup = Semigroup.setSemigroup();
22+
Set<Integer> first = Set.set(Ord.intOrd, 1, 2, 3, 4);
23+
Set<Integer> second = Set.set(Ord.intOrd, 3, 4, 5, 6);
24+
assertThat(unionSemigroup.sum(first, second), is(Set.set(Ord.intOrd, 1, 2, 3, 4, 5, 6)));
25+
}
26+
}

0 commit comments

Comments
 (0)