|
0
|
1 package fj;
|
|
|
2
|
|
|
3 import static fj.Function.curry;
|
|
|
4 import static fj.Function.compose;
|
|
|
5 import static fj.Function.flip;
|
|
|
6 import fj.data.Array;
|
|
|
7 import fj.data.List;
|
|
|
8 import fj.data.Natural;
|
|
|
9 import fj.data.Option;
|
|
|
10 import fj.data.Set;
|
|
|
11 import fj.data.Stream;
|
|
|
12 import static fj.data.Stream.iterableStream;
|
|
|
13
|
|
|
14 import java.math.BigInteger;
|
|
|
15 import java.math.BigDecimal;
|
|
|
16
|
|
|
17 /**
|
|
|
18 * A monoid abstraction to be defined across types of the given type argument. Implementations must
|
|
|
19 * follow the monoidal laws:
|
|
|
20 * <ul>
|
|
|
21 * <li><em>Left Identity</em>; forall x. sum(zero(), x) == x</li>
|
|
|
22 * <li><em>Right Identity</em>; forall x. sum(x, zero()) == x</li>
|
|
|
23 * <li><em>Associativity</em>; forall x. forall y. forall z. sum(sum(x, y), z) == sum(x, sum(y, z))</li>
|
|
|
24 * </ul>
|
|
|
25 *
|
|
|
26 * @version %build.number%
|
|
|
27 */
|
|
|
28 public final class Monoid<A> {
|
|
|
29 private final F<A, F<A, A>> sum;
|
|
|
30 private final A zero;
|
|
|
31
|
|
|
32 private Monoid(final F<A, F<A, A>> sum, final A zero) {
|
|
|
33 this.sum = sum;
|
|
|
34 this.zero = zero;
|
|
|
35 }
|
|
|
36
|
|
|
37 /**
|
|
|
38 * Returns a semigroup projection of this monoid.
|
|
|
39 *
|
|
|
40 * @return A semigroup projection of this monoid.
|
|
|
41 */
|
|
|
42 public Semigroup<A> semigroup() {
|
|
|
43 return Semigroup.semigroup(sum);
|
|
|
44 }
|
|
|
45
|
|
|
46 /**
|
|
|
47 * Sums the two given arguments.
|
|
|
48 *
|
|
|
49 * @param a1 A value to sum with another.
|
|
|
50 * @param a2 A value to sum with another.
|
|
|
51 * @return The of the two given arguments.
|
|
|
52 */
|
|
|
53 public A sum(final A a1, final A a2) {
|
|
|
54 return sum.f(a1).f(a2);
|
|
|
55 }
|
|
|
56
|
|
|
57 /**
|
|
|
58 * Returns a function that sums the given value according to this monoid.
|
|
|
59 *
|
|
|
60 * @param a1 The value to sum.
|
|
|
61 * @return A function that sums the given value according to this monoid.
|
|
|
62 */
|
|
|
63 public F<A, A> sum(final A a1) {
|
|
|
64 return sum.f(a1);
|
|
|
65 }
|
|
|
66
|
|
|
67 /**
|
|
|
68 * Returns a function that sums according to this monoid.
|
|
|
69 *
|
|
|
70 * @return A function that sums according to this monoid.
|
|
|
71 */
|
|
|
72 public F<A, F<A, A>> sum() {
|
|
|
73 return sum;
|
|
|
74 }
|
|
|
75
|
|
|
76 /**
|
|
|
77 * The zero value for this monoid.
|
|
|
78 *
|
|
|
79 * @return The zero value for this monoid.
|
|
|
80 */
|
|
|
81 public A zero() {
|
|
|
82 return zero;
|
|
|
83 }
|
|
|
84
|
|
|
85 /**
|
|
|
86 * Sums the given values with right-fold.
|
|
|
87 *
|
|
|
88 * @param as The values to sum.
|
|
|
89 * @return The sum of the given values.
|
|
|
90 */
|
|
|
91 public A sumRight(final List<A> as) {
|
|
|
92 return as.foldRight(sum, zero);
|
|
|
93 }
|
|
|
94
|
|
|
95 /**
|
|
|
96 * Sums the given values with right-fold.
|
|
|
97 *
|
|
|
98 * @param as The values to sum.
|
|
|
99 * @return The sum of the given values.
|
|
|
100 */
|
|
|
101 public A sumRight(final Stream<A> as) {
|
|
|
102 return as.foldRight(new F2<A, P1<A>, A>() {
|
|
|
103 public A f(final A a, final P1<A> ap1) {
|
|
|
104 return sum(a, ap1._1());
|
|
|
105 }
|
|
|
106 }, zero);
|
|
|
107 }
|
|
|
108
|
|
|
109 /**
|
|
|
110 * Sums the given values with left-fold.
|
|
|
111 *
|
|
|
112 * @param as The values to sum.
|
|
|
113 * @return The sum of the given values.
|
|
|
114 */
|
|
|
115 public A sumLeft(final List<A> as) {
|
|
|
116 return as.foldLeft(sum, zero);
|
|
|
117 }
|
|
|
118
|
|
|
119 /**
|
|
|
120 * Sums the given values with left-fold.
|
|
|
121 *
|
|
|
122 * @param as The values to sum.
|
|
|
123 * @return The sum of the given values.
|
|
|
124 */
|
|
|
125 public A sumLeft(final Stream<A> as) {
|
|
|
126 return as.foldLeft(sum, zero);
|
|
|
127 }
|
|
|
128
|
|
|
129 /**
|
|
|
130 * Returns a function that sums the given values with left-fold.
|
|
|
131 *
|
|
|
132 * @return a function that sums the given values with left-fold.
|
|
|
133 */
|
|
|
134 public F<List<A>, A> sumLeft() {
|
|
|
135 return new F<List<A>, A>() {
|
|
|
136 public A f(final List<A> as) {
|
|
|
137 return sumLeft(as);
|
|
|
138 }
|
|
|
139 };
|
|
|
140 }
|
|
|
141
|
|
|
142 /**
|
|
|
143 * Returns a function that sums the given values with right-fold.
|
|
|
144 *
|
|
|
145 * @return a function that sums the given values with right-fold.
|
|
|
146 */
|
|
|
147 public F<List<A>, A> sumRight() {
|
|
|
148 return new F<List<A>, A>() {
|
|
|
149 public A f(final List<A> as) {
|
|
|
150 return sumRight(as);
|
|
|
151 }
|
|
|
152 };
|
|
|
153 }
|
|
|
154
|
|
|
155 /**
|
|
|
156 * Returns a function that sums the given values with left-fold.
|
|
|
157 *
|
|
|
158 * @return a function that sums the given values with left-fold.
|
|
|
159 */
|
|
|
160 public F<Stream<A>, A> sumLeftS() {
|
|
|
161 return new F<Stream<A>, A>() {
|
|
|
162 public A f(final Stream<A> as) {
|
|
|
163 return sumLeft(as);
|
|
|
164 }
|
|
|
165 };
|
|
|
166 }
|
|
|
167
|
|
|
168 /**
|
|
|
169 * Intersperses the given value between each two elements of the iterable, and sums the result.
|
|
|
170 *
|
|
|
171 * @param as An iterable of values to sum.
|
|
|
172 * @param a The value to intersperse between values of the given iterable.
|
|
|
173 * @return The sum of the given values and the interspersed value.
|
|
|
174 */
|
|
|
175 public A join(final Iterable<A> as, final A a) {
|
|
|
176 final Stream<A> s = iterableStream(as);
|
|
|
177 return s.isEmpty() ?
|
|
|
178 zero :
|
|
|
179 s.foldLeft1(compose(sum, flip(sum).f(a)));
|
|
|
180 }
|
|
|
181
|
|
|
182 /**
|
|
|
183 * Constructs a monoid from the given sum function and zero value, which must follow the monoidal
|
|
|
184 * laws.
|
|
|
185 *
|
|
|
186 * @param sum The sum function for the monoid.
|
|
|
187 * @param zero The zero for the monoid.
|
|
|
188 * @return A monoid instance that uses the given sun function and zero value.
|
|
|
189 */
|
|
|
190 public static <A> Monoid<A> monoid(final F<A, F<A, A>> sum, final A zero) {
|
|
|
191 return new Monoid<A>(sum, zero);
|
|
|
192 }
|
|
|
193
|
|
|
194 /**
|
|
|
195 * Constructs a monoid from the given sum function and zero value, which must follow the monoidal
|
|
|
196 * laws.
|
|
|
197 *
|
|
|
198 * @param sum The sum function for the monoid.
|
|
|
199 * @param zero The zero for the monoid.
|
|
|
200 * @return A monoid instance that uses the given sun function and zero value.
|
|
|
201 */
|
|
|
202 public static <A> Monoid<A> monoid(final F2<A, A, A> sum, final A zero) {
|
|
|
203 return new Monoid<A>(curry(sum), zero);
|
|
|
204 }
|
|
|
205
|
|
|
206 /**
|
|
|
207 * Constructs a monoid from the given semigroup and zero value, which must follow the monoidal laws.
|
|
|
208 *
|
|
|
209 * @param s The semigroup for the monoid.
|
|
|
210 * @param zero The zero for the monoid.
|
|
|
211 * @return A monoid instance that uses the given sun function and zero value.
|
|
|
212 */
|
|
|
213 public static <A> Monoid<A> monoid(final Semigroup<A> s, final A zero) {
|
|
|
214 return new Monoid<A>(s.sum(), zero);
|
|
|
215 }
|
|
|
216
|
|
|
217 /**
|
|
|
218 * A monoid that adds integers.
|
|
|
219 */
|
|
|
220 public static final Monoid<Integer> intAdditionMonoid = monoid(Semigroup.intAdditionSemigroup, 0);
|
|
|
221
|
|
|
222 /**
|
|
|
223 * A monoid that multiplies integers.
|
|
|
224 */
|
|
|
225 public static final Monoid<Integer> intMultiplicationMonoid = monoid(Semigroup.intMultiplicationSemigroup, 1);
|
|
|
226
|
|
|
227 /**
|
|
|
228 * A monoid that adds doubles.
|
|
|
229 */
|
|
|
230 public static final Monoid<Double> doubleAdditionMonoid = monoid(Semigroup.doubleAdditionSemigroup, 0.0);
|
|
|
231
|
|
|
232 /**
|
|
|
233 * A monoid that multiplies doubles.
|
|
|
234 */
|
|
|
235 public static final Monoid<Double> doubleMultiplicationMonoid = monoid(Semigroup.doubleMultiplicationSemigroup, 1.0);
|
|
|
236
|
|
|
237 /**
|
|
|
238 * A monoid that adds big integers.
|
|
|
239 */
|
|
|
240 public static final Monoid<BigInteger> bigintAdditionMonoid = monoid(Semigroup.bigintAdditionSemigroup, BigInteger.ZERO);
|
|
|
241
|
|
|
242 /**
|
|
|
243 * A monoid that multiplies big integers.
|
|
|
244 */
|
|
|
245 public static final Monoid<BigInteger> bigintMultiplicationMonoid =
|
|
|
246 monoid(Semigroup.bigintMultiplicationSemigroup, BigInteger.ONE);
|
|
|
247
|
|
|
248 /**
|
|
|
249 * A monoid that adds big decimals.
|
|
|
250 */
|
|
|
251 public static final Monoid<BigDecimal> bigdecimalAdditionMonoid =
|
|
|
252 monoid(Semigroup.bigdecimalAdditionSemigroup, BigDecimal.ZERO);
|
|
|
253
|
|
|
254 /**
|
|
|
255 * A monoid that multiplies big decimals.
|
|
|
256 */
|
|
|
257 public static final Monoid<BigDecimal> bigdecimalMultiplicationMonoid =
|
|
|
258 monoid(Semigroup.bigdecimalMultiplicationSemigroup, BigDecimal.ONE);
|
|
|
259
|
|
|
260 /**
|
|
|
261 * A monoid that adds natural numbers.
|
|
|
262 */
|
|
|
263 public static final Monoid<Natural> naturalAdditionMonoid =
|
|
|
264 monoid(Semigroup.naturalAdditionSemigroup, Natural.ZERO);
|
|
|
265
|
|
|
266 /**
|
|
|
267 * A monoid that multiplies natural numbers.
|
|
|
268 */
|
|
|
269 public static final Monoid<Natural> naturalMultiplicationMonoid =
|
|
|
270 monoid(Semigroup.naturalMultiplicationSemigroup, Natural.ONE);
|
|
|
271
|
|
|
272 /**
|
|
|
273 * A monoid that adds longs.
|
|
|
274 */
|
|
|
275 public static final Monoid<Long> longAdditionMonoid = monoid(Semigroup.longAdditionSemigroup, 0L);
|
|
|
276
|
|
|
277 /**
|
|
|
278 * A monoid that multiplies longs.
|
|
|
279 */
|
|
|
280 public static final Monoid<Long> longMultiplicationMonoid = monoid(Semigroup.longMultiplicationSemigroup, 1L);
|
|
|
281
|
|
|
282 /**
|
|
|
283 * A monoid that ORs booleans.
|
|
|
284 */
|
|
|
285 public static final Monoid<Boolean> disjunctionMonoid = monoid(Semigroup.disjunctionSemigroup, false);
|
|
|
286
|
|
|
287 /**
|
|
|
288 * A monoid that XORs booleans.
|
|
|
289 */
|
|
|
290 public static final Monoid<Boolean> exclusiveDisjunctionMonoid = monoid(Semigroup.exclusiveDisjunctionSemiGroup, false);
|
|
|
291
|
|
|
292 /**
|
|
|
293 * A monoid that ANDs booleans.
|
|
|
294 */
|
|
|
295 public static final Monoid<Boolean> conjunctionMonoid = monoid(Semigroup.conjunctionSemigroup, true);
|
|
|
296
|
|
|
297 /**
|
|
|
298 * A monoid that appends strings.
|
|
|
299 */
|
|
|
300 public static final Monoid<String> stringMonoid = monoid(Semigroup.stringSemigroup, "");
|
|
|
301
|
|
|
302 /**
|
|
|
303 * A monoid that appends string buffers.
|
|
|
304 */
|
|
|
305 public static final Monoid<StringBuffer> stringBufferMonoid = monoid(Semigroup.stringBufferSemigroup, new StringBuffer());
|
|
|
306
|
|
|
307 /**
|
|
|
308 * A monoid that appends string builders.
|
|
|
309 */
|
|
|
310 public static final Monoid<StringBuilder> stringBuilderMonoid = monoid(Semigroup.stringBuilderSemigroup, new StringBuilder());
|
|
|
311
|
|
|
312 /**
|
|
|
313 * A monoid for functions.
|
|
|
314 *
|
|
|
315 * @param mb The monoid for the function codomain.
|
|
|
316 * @return A monoid for functions.
|
|
|
317 */
|
|
|
318 public static <A, B> Monoid<F<A, B>> functionMonoid(final Monoid<B> mb) {
|
|
|
319 return monoid(Semigroup.<A, B>functionSemigroup(mb.semigroup()), Function.<A, B>constant(mb.zero));
|
|
|
320 }
|
|
|
321
|
|
|
322 /**
|
|
|
323 * A monoid for lists.
|
|
|
324 *
|
|
|
325 * @return A monoid for lists.
|
|
|
326 */
|
|
|
327 public static <A> Monoid<List<A>> listMonoid() {
|
|
|
328 return monoid(Semigroup.<A>listSemigroup(), List.<A>nil());
|
|
|
329 }
|
|
|
330
|
|
|
331 /**
|
|
|
332 * A monoid for options.
|
|
|
333 *
|
|
|
334 * @return A monoid for options.
|
|
|
335 */
|
|
|
336 public static <A> Monoid<Option<A>> optionMonoid() {
|
|
|
337 return monoid(Semigroup.<A>optionSemigroup(), Option.<A>none());
|
|
|
338 }
|
|
|
339
|
|
|
340 /**
|
|
|
341 * A monoid for options that take the first available value.
|
|
|
342 *
|
|
|
343 * @return A monoid for options that take the first available value.
|
|
|
344 */
|
|
|
345 public static <A> Monoid<Option<A>> firstOptionMonoid() {
|
|
|
346 return monoid(Semigroup.<A>firstOptionSemigroup(), Option.<A>none());
|
|
|
347 }
|
|
|
348
|
|
|
349 /**
|
|
|
350 * A monoid for options that take the last available value.
|
|
|
351 *
|
|
|
352 * @return A monoid for options that take the last available value.
|
|
|
353 */
|
|
|
354 public static <A> Monoid<Option<A>> lastOptionMonoid() {
|
|
|
355 return monoid(Semigroup.<A>lastOptionSemigroup(), Option.<A>none());
|
|
|
356 }
|
|
|
357
|
|
|
358 /**
|
|
|
359 * A monoid for streams.
|
|
|
360 *
|
|
|
361 * @return A monoid for streams.
|
|
|
362 */
|
|
|
363 public static <A> Monoid<Stream<A>> streamMonoid() {
|
|
|
364 return monoid(Semigroup.<A>streamSemigroup(), Stream.<A>nil());
|
|
|
365 }
|
|
|
366
|
|
|
367 /**
|
|
|
368 * A monoid for arrays.
|
|
|
369 *
|
|
|
370 * @return A monoid for arrays.
|
|
|
371 */
|
|
|
372 @SuppressWarnings({"unchecked"})
|
|
|
373 public static <A> Monoid<Array<A>> arrayMonoid() {
|
|
|
374 return monoid(Semigroup.<A>arraySemigroup(), Array.<A>empty());
|
|
|
375 }
|
|
|
376
|
|
|
377 /**
|
|
|
378 * A monoid for sets.
|
|
|
379 *
|
|
|
380 * @param o An order for set elements.
|
|
|
381 * @return A monoid for sets whose elements have the given order.
|
|
|
382 */
|
|
|
383 public static <A> Monoid<Set<A>> setMonoid(final Ord<A> o) {
|
|
|
384 return monoid(Semigroup.<A>setSemigroup(), Set.empty(o));
|
|
|
385 }
|
|
|
386
|
|
|
387 }
|
