Monoid Menagerie, or, the uncanny usefulness of four lines of Java

MonoidMenagerie.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);
    }
  }



}