1 /*
2 Copyright 2015 Atlassian
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 */
16
17 package io.atlassian.fugue;
18
19 import static io.atlassian.fugue.Pair.pair;
20
21 /**
22 * A Semigroup is an algebraic structure consisting of an associative binary
23 * operation across the values of a given type (the Semigroup type argument).
24 * Implementations must satisfy the law of associativity:
25 * <ul>
26 * <li><em>Associativity</em>; forall x y z. append(append(x, y), z) ==
27 * append(x, append(y, z))</li>
28 * </ul>
29 * Methods {@link #sumNonEmpty(Object, Iterable)} and
30 * {@link #multiply1p(int, Object)} can be overriden for performance reason,
31 * especially if {@link #sumNonEmpty(Object, Iterable)} can be implemented to
32 * not require evaluation of the whole iterable.
33 *
34 * @see Monoid
35 * @since 3.1
36 */
37 public interface Semigroup<A> {
38
39 /**
40 * Combine the two given arguments.
41 *
42 * @param a1 left value to combine
43 * @param a2 right value to combine
44 * @return the combination of the left and right value.
45 */
46 A append(final A a1, final A a2);
47
48 /**
49 * Reduce a 'non-empty' Iterable with {@link #append(Object, Object)}
50 *
51 * @param head the head of the 'non-empty' Iterable
52 * @param tail the tail (maybe an empty Iterable).
53 * @return the sum of all elements.
54 */
55 default A sumNonEmpty(A head, Iterable<A> tail) {
56
57 A currentValue = head;
58 for (final A a : tail) {
59 currentValue = append(currentValue, a);
60 }
61 return currentValue;
62
63 }
64
65 /**
66 * Returns a value summed <code>n + 1</code> times (
67 * <code>a + a + ... + a</code>) The default definition uses peasant
68 * multiplication, exploiting associativity to only require `O(log n)` uses of
69 * {@link #append(Object, Object)}.
70 *
71 * @param n multiplier
72 * @param a the value to be reapeatly summed n + 1 times
73 * @return {@code a} summed {@code n} times. If {@code n <= 0}, returns
74 * {@code zero()}
75 */
76 default A multiply1p(int n, A a) {
77 if (n <= 0) {
78 return a;
79 }
80
81 A xTmp = a;
82 int yTmp = n;
83 A zTmp = a;
84 while (true) {
85 if ((yTmp & 1) == 1) {
86 zTmp = append(xTmp, zTmp);
87 if (yTmp == 1) {
88 return zTmp;
89 }
90 }
91 xTmp = append(xTmp, xTmp);
92 yTmp = (yTmp) >>> 1;
93 }
94 }
95
96 /**
97 * Composes a semigroup with another.
98 */
99 static <A, B> Semigroup<Pair<A, B>> compose(Semigroup<A> sa, Semigroup<B> sb) {
100 return new Semigroup<Pair<A, B>>() {
101 @Override public Pair<A, B> append(Pair<A, B> ab1, Pair<A, B> ab2) {
102 return pair(sa.append(ab1.left(), ab2.left()), sb.append(ab1.right(), ab2.right()));
103 }
104
105 @Override public Pair<A, B> multiply1p(int n, Pair<A, B> ab) {
106 return pair(sa.multiply1p(n, ab.left()), sb.multiply1p(n, ab.right()));
107 }
108 };
109 }
110
111 /**
112 * Return the dual Semigroup of a semigroup
113 *
114 * @param semigroup base semigroup to create the dual from
115 * @return a semigroup appending in reverse order
116 */
117 static <A> Semigroup<A> dual(Semigroup<A> semigroup) {
118 return new Semigroup<A>() {
119 @Override public A append(A a1, A a2) {
120 return semigroup.append(a2, a1);
121 }
122
123 @Override public A multiply1p(int n, A a) {
124 return semigroup.multiply1p(n, a);
125 }
126 };
127 }
128
129 }