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 }