Skip to content

Instantly share code, notes, and snippets.

@Bill Bill/MonoidMenagerie.java
Last active Jun 19, 2019

Embed
What would you like to do?
Monoid Menagerie, or, the uncanny usefulness of four lines of Java
import java.util.Comparator;
import java.util.List;
import java.util.function.BinaryOperator;
import java.util.function.Supplier;
import java.util.stream.Collectors;
import java.util.stream.Stream;
/*
Code to accompany presentation "Monoid Menagerie"
https://docs.google.com/presentation/d/1spxbemxtvuPKa9qjLXifDtVsgm1M_cDjFQb0dyrbDhI/edit#slide=id.p
*/
class MonoidMenagerie {
private MonoidMenagerie() {}
public static void main(String[] args) {
/*
Let's add some integers
*/
final int sum1 = sum(0, 1, 2);
/*
Now let's multiply some integers
*/
final int product1 = product(3, 4, 5);
/*
Do we really need two different functions or will one do it?
*/
final Integer sum2 = reduce(
0,
Integer::sum,
0, 1, 2);
final Integer product2 = reduce(
1,
(x, y) -> x * y,
3, 4, 5);
/*
Reducing an empty collection
*/
final Integer sum4 = reduce(0, Integer::sum);
final Integer product4 = reduce(1, (x, y) -> x * y);
/*
Reducing a one element collection
*/
final Integer sum5 = reduce(0, Integer::sum,6);
final Integer product5 = reduce(1, (x, y) -> x * y, 11);
/*
But reduce() is not limited to operating on integers, or even numbers for that matter
*/
final Boolean and1 = reduce(
true,
Boolean::logicalAnd,
true, true, true);
final Boolean and2 = reduce(
true,
Boolean::logicalAnd,
true, false, true);
final Boolean or1 = reduce(
false,
Boolean::logicalOr,
false, false, false);
final Boolean or2 = reduce(
false,
Boolean::logicalOr,
false, true, false);
/*
All you need is:
1. a binary operation (function) fn that obeys certain laws:
is a _closed_ mapping: T fn(T a, T b)
is associative: fn(a, fn(b, c)) == fn( fn(a, b), c)
2. an identity value id: fn(id, x) == x for all x
That's a Monoid: a closed, associative, binary operation and an identity value
*/
/*
The monoid of strings under concatenation with identity value "" (the empty string)
*/
final String concatenatedString =
reduce(
"",
String::concat,
"quick", "brown", "fox");
/*
The monoid of integer streams under concatenation with identity value Stream.empty()
*/
final List<Integer> concatenatedStreamAsList = toList(
reduce(
Stream.empty(),
Stream::concat,
Stream.of(1, 2), Stream.of(3, 4)));
/*
The monoid of person comparators under thenComparing with identity value (p1,p2)->0
*/
final Comparator<Person>
compareByFirst =
Comparator.comparing(Person::getFirst, String.CASE_INSENSITIVE_ORDER);
final Comparator<Person>
compareByLast =
Comparator.comparing(Person::getLast, String.CASE_INSENSITIVE_ORDER);
final Person person1 = new Person("Samuel", "Chase");
final Person person2 = new Person("Ruth", "Ginsburg");
final Person person3 = new Person("Salmon", "Chase");
final Supplier<Stream<Person>>
peopleSupplier = () -> Stream.of(person1, person2, person3);
final List<Person> sortedByLast = toList(
peopleSupplier.get().sorted(compareByLast));
// but what if we want to sort by last, then by first? um:
final Comparator<Person>
handwrittenLastFirstComparator =
(final Person p1, final Person p2) -> {
final int comparisonOnLast = p1.getLast()
.compareToIgnoreCase(p2.getLast());
if (comparisonOnLast == 0)
return p1.getFirst()
.compareToIgnoreCase(p2.getFirst());
else
return comparisonOnLast;
};
final List<Person> sortedByLastThenFirst = toList(
peopleSupplier.get().sorted(handwrittenLastFirstComparator));
// but what if we had more that two fields--hand-writing comparator is error-prone! so:
final Comparator<Person> IDENTITY_COMPARATOR = (p1, p2) -> 0;
final Comparator<Person> generatedLastFirstComparator = reduce(
IDENTITY_COMPARATOR,
Comparator::thenComparing,
compareByLast, compareByFirst);
final List<Person> sortedByLastThenFirst2 = toList(
peopleSupplier.get().sorted(generatedLastFirstComparator));
// and what if we wished to compare none of the fields--leaving the original order unchanged?
final Comparator<Person> generatedIdentityComparator = reduce(
IDENTITY_COMPARATOR,
Comparator::thenComparing
/* EMPTY COLLECTION OF COMPARATORS */ );
final List<Person> sortedByNothing = toList(
peopleSupplier.get().sorted(generatedIdentityComparator));
/*
------------------------------------------------------------------------------------
Java's Stream.reduce() works (with monoids)--just like the reduce() we just wrote...
------------------------------------------------------------------------------------
*/
/*
The monoid of integers under addition with identity value 0
*/
final int sum = Stream.of(1, 2, 3).reduce(0, Integer::sum);
/*
Stream.reduce() works in parallel--just convert the stream to a parallel one first
NB: don't try this with the single-parameter Stream.reduce()--it only works for the
variants that take an identity parameter. Further: be sure you provide the actual identity
value. You can certainly provide other values--and the reduce() method will be none the
wiser. But if you do that, you'll get wrong results when you parallelize.
*/
final int sum3 = Stream.of(1, 2, 3)
.parallel()
.reduce(0, Integer::sum);
/*
The monoid of integers under multiplication with identity value 1
*/
final int product = Stream.of(1, 2, 3).reduce(1,(a, b) -> a * b);
/*
The monoid of booleans under disjunction (OR) with identity value false
*/
final boolean disjunction = Stream.of(true, true, false).reduce(false, Boolean::logicalOr);
/*
The monoid of booleans under conjunction (AND) with identity value true
*/
final Boolean conjunction = Stream.of(false, true, false).reduce(true, Boolean::logicalAnd);
/*
The monoid of strings under concatenation with identity value "" (the empty string)
*/
final String concatenatedString2 = Stream.of("quick", "brown", "fox").reduce("", String::concat);
/*
But how since String::concat is not a static method? Ah, see: Java will convert a reference
to a non-static method, as a binary operator
*/
BinaryOperator<String> concatFunction = String::concat;
final String nacho = concatFunction.apply("Nacho", "Libre");
// reversal!
final String reversedConcatenatedString = Stream.of("quick", "brown", "fox").reduce("", (a,b)->b.concat(a));
/*
The monoid of integer streams under concatenation with identity value Stream.empty()
*/
final List<Integer> concatenatedStream2 = toList(
Stream.of(Stream.of(1, 2), Stream.of(3, 4)).reduce(Stream.empty(), Stream::concat));
/*
The monoid of person comparators under thenComparing with identity value (p1,p2)->0
*/
final List<Person> sortedByLast2 = toList(
peopleSupplier.get().sorted(compareByLast));
// but what if we want to sort by last, then by first? um:
final Comparator<Person>
handwrittenLastFirstComparator2 =
(final Person p1, final Person p2) -> {
final int comparisonOnLast = p1.getLast()
.compareToIgnoreCase(p2.getLast());
if (comparisonOnLast == 0)
return p1.getFirst()
.compareToIgnoreCase(p2.getFirst());
else
return comparisonOnLast;
};
final List<Person> sortedByLastThenFirst3 = toList(
peopleSupplier.get().sorted(handwrittenLastFirstComparator2));
// but what if we had more that two fields--hand-writing comparator is error-prone! so:
final Comparator<Person>
generatedLastFirstComparator2 =
Stream.of(compareByLast, compareByFirst)
.reduce(IDENTITY_COMPARATOR,Comparator::thenComparing);
final List<Person> sortedByLastThenFirst4 = toList(
peopleSupplier.get().sorted(generatedLastFirstComparator2));
// and what if we wished to compare none of the fields--leaving the original order unchanged?
final Comparator<Person>
generatedIdentityComparator2 =
Stream.<Comparator<Person>>empty()
.reduce(IDENTITY_COMPARATOR,Comparator::thenComparing);
final List<Person> sortedByNothing2 = toList(
peopleSupplier.get().sorted(generatedIdentityComparator2));
/*
------------------------------------------------------------------------------------
This little section isn't in the slides. Let's write LISP/Clojure-style sum,
product, and, or--that encode their identity value into the 0-ary variant and
let's leverage reduce() in those functions, to handle N=3,4,5... arguments
------------------------------------------------------------------------------------
*/
final Integer sum6 = plus(0, 1, 2);
final Integer product3 = multiply(3, 4, 5);
final Boolean and3 = and(true, true, true);
final Boolean and4 = and(true, false, true);
final Boolean or3 = or(false, false, false);
final Boolean or4 = or(false, true, false);
System.out.println();
}
static int sum(final int ... values) {
int accumulator = 0;
for (final int value : values) {
accumulator = accumulator + value;
}
return accumulator;
}
static int product(final int ... values) {
int accumulator = 1;
for (final int value : values) {
accumulator = accumulator * value;
}
return accumulator;
}
static int reduceInt(
final int identity,
final BinaryOperator<Integer> fn, final int ... values) {
int accumulator = identity;
for (final int value : values) {
accumulator = fn.apply(accumulator, value);
}
return accumulator;
}
@SafeVarargs
static <T> T reduce(
final T identity,
final BinaryOperator<T> fn, final T ... values) {
T accumulator = identity;
for (final T value : values) {
accumulator = fn.apply(accumulator, value);
}
return accumulator;
}
static <T> List<T> toList(final Stream<T> s) {
return s.collect(Collectors.toList());
}
static class Person {
private final String first; private final String last;
Person(final String first, final String last) {
this.first = first; this.last = last;
}
String getFirst() { return first;}
String getLast() { return last;}
}
/*
LISP/Clojure-style monoidal +/-/and/or with optimization to avoid calling reduce() for
arity < 3...
Each of these encodes its identity value in the 0-ary case, and avoids calling reduce
unless there are more than 2 values to process.
TODO: the use of BinaryOperator<Integer> seems to infect this code with auto-boxing--
see if we can eliminate that since it kind of defeats the purpose of the switch-
statement optimization. If e.g. we declare plus(final int ... values) we get a compile
error on return reduce(plus(), Integer::sum, values):
Cannot resolve method(int, <method reference>, int[])
*/
static int plus(final Integer ... values) {
switch(values.length) {
case 0: return 0; // identity
case 1: return values[0];
case 2: return Integer.sum(values[0], values[1]);
default:
return reduce(plus(), Integer::sum, values);
}
}
static int multiply2(final int a, final int b) {
return a * b;
}
static int multiply(final Integer ... values) {
switch(values.length) {
case 0: return 1; // identity
case 1: return values[0];
case 2: return multiply2(values[0], values[1]);
default:
return reduce(multiply(), MonoidMenagerie::multiply2, values);
}
}
static boolean and(final Boolean ... values) {
switch (values.length) {
case 0: return true; // identity
case 1: return values[0];
case 2: return Boolean.logicalAnd(values[0], values[1]);
default:
return reduce(and(), Boolean::logicalAnd, values);
}
}
static boolean or(final Boolean ... values) {
switch(values.length) {
case 0: return false; // identity
case 1: return values[0];
case 2: return Boolean.logicalOr(values[0], values[1]);
default:
return reduce(or(), Boolean::logicalOr, values);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.