001    package fj.pre;
002    
003    import fj.F;
004    import fj.F2;
005    import fj.Function;
006    import fj.P1;
007    import static fj.pre.Semigroup.*;
008    import static fj.Function.curry;
009    import static fj.Function.compose;
010    import static fj.Function.flip;
011    import fj.data.Array;
012    import fj.data.List;
013    import fj.data.Natural;
014    import fj.data.Option;
015    import fj.data.Set;
016    import fj.data.Stream;
017    import static fj.data.Stream.iterableStream;
018    
019    import java.math.BigInteger;
020    import java.math.BigDecimal;
021    
022    /**
023     * A monoid abstraction to be defined across types of the given type argument. Implementations must
024     * follow the monoidal laws:
025     * <ul>
026     * <li><em>Left Identity</em>; forall x. sum(zero(), x) == x</li>
027     * <li><em>Right Identity</em>; forall x. sum(x, zero()) == x</li>
028     * <li><em>Associativity</em>; forall x. forall y. forall z. sum(sum(x, y), z) == sum(x, sum(y, z))</li>
029     * </ul>
030     *
031     * @version %build.number%<br>
032     *          <ul>
033     *          <li>$LastChangedRevision: 290 $</li>
034     *          <li>$LastChangedDate: 2010-01-13 13:04:54 +1000 (Wed, 13 Jan 2010) $</li>
035     *          </ul>
036     */
037    public final class Monoid<A> {
038      private final F<A, F<A, A>> sum;
039      private final A zero;
040    
041      private Monoid(final F<A, F<A, A>> sum, final A zero) {
042        this.sum = sum;
043        this.zero = zero;
044      }
045    
046      /**
047       * Returns a semigroup projection of this monoid.
048       *
049       * @return A semigroup projection of this monoid.
050       */
051      public Semigroup<A> semigroup() {
052        return Semigroup.semigroup(sum);
053      }
054    
055      /**
056       * Sums the two given arguments.
057       *
058       * @param a1 A value to sum with another.
059       * @param a2 A value to sum with another.
060       * @return The of the two given arguments.
061       */
062      public A sum(final A a1, final A a2) {
063        return sum.f(a1).f(a2);
064      }
065    
066      /**
067       * Returns a function that sums the given value according to this monoid.
068       *
069       * @param a1 The value to sum.
070       * @return A function that sums the given value according to this monoid.
071       */
072      public F<A, A> sum(final A a1) {
073        return sum.f(a1);
074      }
075    
076      /**
077       * Returns a function that sums according to this monoid.
078       *
079       * @return A function that sums according to this monoid.
080       */
081      public F<A, F<A, A>> sum() {
082        return sum;
083      }
084    
085      /**
086       * The zero value for this monoid.
087       *
088       * @return The zero value for this monoid.
089       */
090      public A zero() {
091        return zero;
092      }
093    
094      /**
095       * Sums the given values with right-fold.
096       *
097       * @param as The values to sum.
098       * @return The sum of the given values.
099       */
100      public A sumRight(final List<A> as) {
101        return as.foldRight(sum, zero);
102      }
103    
104      /**
105       * Sums the given values with right-fold.
106       *
107       * @param as The values to sum.
108       * @return The sum of the given values.
109       */
110      public A sumRight(final Stream<A> as) {
111        return as.foldRight(new F2<A, P1<A>, A>() {
112          public A f(final A a, final P1<A> ap1) {
113            return sum(a, ap1._1());
114          }
115        }, zero);
116      }
117    
118      /**
119       * Sums the given values with left-fold.
120       *
121       * @param as The values to sum.
122       * @return The sum of the given values.
123       */
124      public A sumLeft(final List<A> as) {
125        return as.foldLeft(sum, zero);
126      }
127    
128      /**
129       * Sums the given values with left-fold.
130       *
131       * @param as The values to sum.
132       * @return The sum of the given values.
133       */
134      public A sumLeft(final Stream<A> as) {
135        return as.foldLeft(sum, zero);
136      }
137    
138      /**
139       * Returns a function that sums the given values with left-fold.
140       *
141       * @return a function that sums the given values with left-fold.
142       */
143      public F<List<A>, A> sumLeft() {
144        return new F<List<A>, A>() {
145          public A f(final List<A> as) {
146            return sumLeft(as);
147          }
148        };
149      }
150    
151      /**
152       * Returns a function that sums the given values with right-fold.
153       *
154       * @return a function that sums the given values with right-fold.
155       */
156      public F<List<A>, A> sumRight() {
157        return new F<List<A>, A>() {
158          public A f(final List<A> as) {
159            return sumRight(as);
160          }
161        };
162      }
163    
164      /**
165       * Returns a function that sums the given values with left-fold.
166       *
167       * @return a function that sums the given values with left-fold.
168       */
169      public F<Stream<A>, A> sumLeftS() {
170        return new F<Stream<A>, A>() {
171          public A f(final Stream<A> as) {
172            return sumLeft(as);
173          }
174        };
175      }
176    
177      /**
178       * Intersperses the given value between each two elements of the iterable, and sums the result.
179       *
180       * @param as An iterable of values to sum.
181       * @param a  The value to intersperse between values of the given iterable.
182       * @return The sum of the given values and the interspersed value.
183       */
184      public A join(final Iterable<A> as, final A a) {
185        final Stream<A> s = iterableStream(as);
186        return s.isEmpty() ?
187               zero :
188               s.foldLeft1(compose(sum, flip(sum).f(a)));
189      }
190    
191      /**
192       * Constructs a monoid from the given sum function and zero value, which must follow the monoidal
193       * laws.
194       *
195       * @param sum  The sum function for the monoid.
196       * @param zero The zero for the monoid.
197       * @return A monoid instance that uses the given sun function and zero value.
198       */
199      public static <A> Monoid<A> monoid(final F<A, F<A, A>> sum, final A zero) {
200        return new Monoid<A>(sum, zero);
201      }
202    
203      /**
204       * Constructs a monoid from the given sum function and zero value, which must follow the monoidal
205       * laws.
206       *
207       * @param sum  The sum function for the monoid.
208       * @param zero The zero for the monoid.
209       * @return A monoid instance that uses the given sun function and zero value.
210       */
211      public static <A> Monoid<A> monoid(final F2<A, A, A> sum, final A zero) {
212        return new Monoid<A>(curry(sum), zero);
213      }
214    
215      /**
216       * Constructs a monoid from the given semigroup and zero value, which must follow the monoidal laws.
217       *
218       * @param s    The semigroup for the monoid.
219       * @param zero The zero for the monoid.
220       * @return A monoid instance that uses the given sun function and zero value.
221       */
222      public static <A> Monoid<A> monoid(final Semigroup<A> s, final A zero) {
223        return new Monoid<A>(s.sum(), zero);
224      }
225    
226      /**
227       * A monoid that adds integers.
228       */
229      public static final Monoid<Integer> intAdditionMonoid = monoid(intAdditionSemigroup, 0);
230    
231      /**
232       * A monoid that multiplies integers.
233       */
234      public static final Monoid<Integer> intMultiplicationMonoid = monoid(intMultiplicationSemigroup, 1);
235    
236      /**
237       * A monoid that adds big integers.
238       */
239      public static final Monoid<BigInteger> bigintAdditionMonoid = monoid(bigintAdditionSemigroup, BigInteger.ZERO);
240    
241      /**
242       * A monoid that multiplies big integers.
243       */
244      public static final Monoid<BigInteger> bigintMultiplicationMonoid =
245          monoid(bigintMultiplicationSemigroup, BigInteger.ONE);
246    
247      /**
248       * A monoid that adds big decimals.
249       */
250      public static final Monoid<BigDecimal> bigdecimalAdditionMonoid =
251          monoid(bigdecimalAdditionSemigroup, BigDecimal.ZERO);
252    
253      /**
254       * A monoid that multiplies big decimals.
255       */
256      public static final Monoid<BigDecimal> bigdecimalMultiplicationMonoid =
257          monoid(bigdecimalMultiplicationSemigroup, BigDecimal.ONE);
258    
259      /**
260       * A monoid that adds natural numbers.
261       */
262      public static final Monoid<Natural> naturalAdditionMonoid =
263          monoid(naturalAdditionSemigroup, Natural.ZERO);
264    
265      /**
266       * A monoid that multiplies natural numbers.
267       */
268      public static final Monoid<Natural> naturalMultiplicationMonoid =
269          monoid(naturalMultiplicationSemigroup, Natural.ONE);
270    
271      /**
272       * A monoid that adds longs.
273       */
274      public static final Monoid<Long> longAdditionMonoid = monoid(longAdditionSemigroup, 0L);
275    
276      /**
277       * A monoid that multiplies longs.
278       */
279      public static final Monoid<Long> longMultiplicationMonoid = monoid(longMultiplicationSemigroup, 1L);
280    
281      /**
282       * A monoid that ORs booleans.
283       */
284      public static final Monoid<Boolean> disjunctionMonoid = monoid(disjunctionSemigroup, false);
285    
286      /**
287       * A monoid that XORs booleans.
288       */
289      public static final Monoid<Boolean> exclusiveDisjunctionMonoid = monoid(exclusiveDisjunctionSemiGroup, false);
290    
291      /**
292       * A monoid that ANDs booleans.
293       */
294      public static final Monoid<Boolean> conjunctionMonoid = monoid(conjunctionSemigroup, true);
295    
296      /**
297       * A monoid that appends strings.
298       */
299      public static final Monoid<String> stringMonoid = monoid(stringSemigroup, "");
300    
301      /**
302       * A monoid that appends string buffers.
303       */
304      public static final Monoid<StringBuffer> stringBufferMonoid = monoid(stringBufferSemigroup, new StringBuffer());
305    
306      /**
307       * A monoid that appends string builders.
308       */
309      public static final Monoid<StringBuilder> stringBuilderMonoid = monoid(stringBuilderSemigroup, new StringBuilder());
310    
311      /**
312       * A monoid for functions.
313       *
314       * @param mb The monoid for the function codomain.
315       * @return A monoid for functions.
316       */
317      public static <A, B> Monoid<F<A, B>> functionMonoid(final Monoid<B> mb) {
318        return monoid(Semigroup.<A, B>functionSemigroup(mb.semigroup()), Function.<A, B>constant(mb.zero));
319      }
320    
321      /**
322       * A monoid for lists.
323       *
324       * @return A monoid for lists.
325       */
326      public static <A> Monoid<List<A>> listMonoid() {
327        return monoid(Semigroup.<A>listSemigroup(), List.<A>nil());
328      }
329    
330      /**
331       * A monoid for options.
332       *
333       * @return A monoid for options.
334       */
335      public static <A> Monoid<Option<A>> optionMonoid() {
336        return monoid(Semigroup.<A>optionSemigroup(), Option.<A>none());
337      }
338    
339      /**
340       * A monoid for streams.
341       *
342       * @return A monoid for streams.
343       */
344      public static <A> Monoid<Stream<A>> streamMonoid() {
345        return monoid(Semigroup.<A>streamSemigroup(), Stream.<A>nil());
346      }
347    
348      /**
349       * A monoid for arrays.
350       *
351       * @return A monoid for arrays.
352       */
353      @SuppressWarnings({"unchecked"})
354      public static <A> Monoid<Array<A>> arrayMonoid() {
355        return monoid(Semigroup.<A>arraySemigroup(), Array.<A>empty());
356      }
357    
358      /**
359       * A monoid for sets.
360       *
361       * @param o An order for set elements.
362       * @return A monoid for sets whose elements have the given order.
363       */
364      public static <A> Monoid<Set<A>> setMonoid(final Ord<A> o) {
365        return monoid(Semigroup.<A>setSemigroup(), Set.empty(o));
366      }
367    
368    }