Short-circuiting in relevant monoids

jnape · jnape · commit 85a79ef1ce56 · 2018-05-13T14:34:55.000-05:00
diff --git a/CHANGELOG.md b/CHANGELOG.md
@@ -7,6 +7,8 @@ The format is based on [Keep a Changelog](http://keepachangelog.com/).
 ### Changed
 - `ToMap` accepts an `Iterable` covariant in `Map.Entry`
 - `RecursiveResult#invert` is also a `RecursiveResult`
+- `First`/`And`/`Or` monoids all utilize short-circuiting
+- `Monoid#foldLeft/foldRight` delegate to `Monoid#reduceLeft/reduceRight`, respectively 
 
 ### Added
 - `Upcast` for safely casting up a type hierarchy
diff --git a/src/main/java/com/jnape/palatable/lambda/monoid/Monoid.java b/src/main/java/com/jnape/palatable/lambda/monoid/Monoid.java
@@ -8,7 +8,9 @@
 import java.util.function.Function;
 import java.util.function.Supplier;
 
+import static com.jnape.palatable.lambda.functions.builtin.fn2.Cons.cons;
 import static com.jnape.palatable.lambda.functions.builtin.fn2.Map.map;
+import static com.jnape.palatable.lambda.functions.builtin.fn2.Snoc.snoc;
 
 /**
  * A {@link Monoid} is the pairing of a {@link Semigroup} with an identity element.
@@ -64,6 +66,22 @@ default <B> A foldMap(Function<? super B, ? extends A> fn, Iterable<B> bs) {
         return reduceLeft(map(fn, bs));
     }
 
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    default A foldLeft(A a, Iterable<A> as) {
+        return reduceLeft(cons(a, as));
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    default A foldRight(A a, Iterable<A> as) {
+        return reduceRight(snoc(a, as));
+    }
+
     /**
      * {@inheritDoc}
      */
diff --git a/src/main/java/com/jnape/palatable/lambda/monoid/builtin/And.java b/src/main/java/com/jnape/palatable/lambda/monoid/builtin/And.java
@@ -4,6 +4,10 @@
 import com.jnape.palatable.lambda.functions.specialized.BiPredicate;
 import com.jnape.palatable.lambda.monoid.Monoid;
 
+import static com.jnape.palatable.lambda.functions.builtin.fn1.Id.id;
+import static com.jnape.palatable.lambda.functions.builtin.fn1.Not.not;
+import static com.jnape.palatable.lambda.functions.builtin.fn2.Find.find;
+
 /**
  * A {@link Monoid} instance formed by <code>Boolean</code>. Equivalent to logical <code>&amp;&amp;</code>.
  *
@@ -27,6 +31,11 @@ public Boolean apply(Boolean x, Boolean y) {
         return x && y;
     }
 
+    @Override
+    public Boolean reduceLeft(Iterable<Boolean> bools) {
+        return find(not(id()), bools).orElse(true);
+    }
+
     @Override
     public boolean test(Boolean x, Boolean y) {
         return apply(x, y);
diff --git a/src/main/java/com/jnape/palatable/lambda/monoid/builtin/First.java b/src/main/java/com/jnape/palatable/lambda/monoid/builtin/First.java
@@ -5,6 +5,8 @@
 import com.jnape.palatable.lambda.monoid.Monoid;
 
 import static com.jnape.palatable.lambda.adt.Maybe.nothing;
+import static com.jnape.palatable.lambda.functions.builtin.fn1.CatMaybes.catMaybes;
+import static com.jnape.palatable.lambda.functions.builtin.fn1.Head.head;
 
 /**
  * A {@link Monoid} instance formed by <code>{@link Maybe}&lt;A&gt;</code>. The application to two {@link Maybe} values
@@ -33,6 +35,11 @@ public Maybe<A> apply(Maybe<A> x, Maybe<A> y) {
         return x.fmap(Maybe::just).orElse(y);
     }
 
+    @Override
+    public Maybe<A> reduceLeft(Iterable<Maybe<A>> maybes) {
+        return head(catMaybes(maybes));
+    }
+
     @SuppressWarnings("unchecked")
     public static <A> First<A> first() {
         return INSTANCE;
diff --git a/src/main/java/com/jnape/palatable/lambda/monoid/builtin/Or.java b/src/main/java/com/jnape/palatable/lambda/monoid/builtin/Or.java
@@ -4,6 +4,9 @@
 import com.jnape.palatable.lambda.functions.specialized.BiPredicate;
 import com.jnape.palatable.lambda.monoid.Monoid;
 
+import static com.jnape.palatable.lambda.functions.builtin.fn1.Id.id;
+import static com.jnape.palatable.lambda.functions.builtin.fn2.Find.find;
+
 /**
  * A {@link Monoid} instance formed by <code>Boolean</code>. Equivalent to logical <code>||</code>.
  *
@@ -32,6 +35,11 @@ public boolean test(Boolean x, Boolean y) {
         return apply(x, y);
     }
 
+    @Override
+    public Boolean reduceLeft(Iterable<Boolean> bools) {
+        return find(id(), bools).orElse(false);
+    }
+
     @Override
     public Or flip() {
         return this;
diff --git a/src/test/java/com/jnape/palatable/lambda/monoid/builtin/AndTest.java b/src/test/java/com/jnape/palatable/lambda/monoid/builtin/AndTest.java
@@ -2,6 +2,9 @@
 
 import org.junit.Test;
 
+import static com.jnape.palatable.lambda.functions.builtin.fn1.Id.id;
+import static com.jnape.palatable.lambda.functions.builtin.fn1.Repeat.repeat;
+import static com.jnape.palatable.lambda.functions.builtin.fn2.Cons.cons;
 import static com.jnape.palatable.lambda.monoid.builtin.And.and;
 import static org.junit.Assert.assertEquals;
 
@@ -20,4 +23,15 @@ public void monoid() {
         assertEquals(false, and.apply(true, false));
         assertEquals(false, and.apply(false, false));
     }
+
+    @Test(timeout = 500)
+    public void shortCircuiting() {
+        Iterable<Boolean> bools = cons(false, repeat(true));
+        And and = and();
+
+        assertEquals(false, and.foldLeft(false, bools));
+        assertEquals(false, and.foldLeft(true, bools));
+        assertEquals(false, and.reduceLeft(bools));
+        assertEquals(false, and.foldMap(id(), bools));
+    }
 }
diff --git a/src/test/java/com/jnape/palatable/lambda/monoid/builtin/FirstTest.java b/src/test/java/com/jnape/palatable/lambda/monoid/builtin/FirstTest.java
@@ -1,9 +1,12 @@
 package com.jnape.palatable.lambda.monoid.builtin;
 
+import com.jnape.palatable.lambda.adt.Maybe;
 import org.junit.Test;
 
 import static com.jnape.palatable.lambda.adt.Maybe.just;
 import static com.jnape.palatable.lambda.adt.Maybe.nothing;
+import static com.jnape.palatable.lambda.functions.builtin.fn1.Id.id;
+import static com.jnape.palatable.lambda.functions.builtin.fn1.Repeat.repeat;
 import static com.jnape.palatable.lambda.monoid.builtin.First.first;
 import static org.junit.Assert.assertEquals;
 
@@ -22,4 +25,15 @@ public void monoid() {
         assertEquals(just(2), first.apply(nothing(), just(2)));
         assertEquals(nothing(), first.apply(nothing(), nothing()));
     }
+
+    @Test(timeout = 500)
+    public void shortCircuiting() {
+        Iterable<Maybe<Integer>> maybeInts = repeat(just(1));
+        First<Integer> first = First.first();
+
+        assertEquals(just(1), first.foldLeft(nothing(), maybeInts));
+        assertEquals(just(1), first.foldLeft(just(1), maybeInts));
+        assertEquals(just(1), first.reduceLeft(maybeInts));
+        assertEquals(just(1), first.foldMap(id(), maybeInts));
+    }
 }
diff --git a/src/test/java/com/jnape/palatable/lambda/monoid/builtin/OrTest.java b/src/test/java/com/jnape/palatable/lambda/monoid/builtin/OrTest.java
@@ -2,6 +2,9 @@
 
 import org.junit.Test;
 
+import static com.jnape.palatable.lambda.functions.builtin.fn1.Id.id;
+import static com.jnape.palatable.lambda.functions.builtin.fn1.Repeat.repeat;
+import static com.jnape.palatable.lambda.functions.builtin.fn2.Cons.cons;
 import static com.jnape.palatable.lambda.monoid.builtin.Or.or;
 import static org.junit.Assert.assertEquals;
 
@@ -20,4 +23,15 @@ public void monoid() {
         assertEquals(true, or.apply(false, true));
         assertEquals(false, or.apply(false, false));
     }
+
+    @Test(timeout = 500)
+    public void shortCircuiting() {
+        Iterable<Boolean> bools = cons(true, repeat(false));
+        Or or = or();
+
+        assertEquals(true, or.foldLeft(false, bools));
+        assertEquals(true, or.foldLeft(true, bools));
+        assertEquals(true, or.reduceLeft(bools));
+        assertEquals(true, or.foldMap(id(), bools));
+    }
 }
