Difference

jnape · jnape · commit 8cfcc2d12494 · 2018-06-10T18:42:15.000-05:00
diff --git a/CHANGELOG.md b/CHANGELOG.md
@@ -10,11 +10,12 @@ The format is based on [Keep a Changelog](http://keepachangelog.com/).
 - `CmpEqBy`, `CmpEq`, `GTBy`, `GT`, `LTBy`, `LT`, `GTEBy`, `GTE`, `LTEBy`, and `LTE` inequality checks
 - `MinBy`, `MaxBy`, `Min`, and `Max` semigroups
 - `Product2-8` interfaces, representing general product types
-- `Union`, a semigroup that behaves like a lazy set union on `Iterable`s 
+- `Union`, a semigroup that behaves like a lazy set union on `Iterable`s
+- `Difference`, a semigroup that behaves like a partially lazy set difference on `Iterable`s
 
 ### Changed
 - `Tuple2-8` now implement `Product2-8`
-- `Into2-8` now accepts a product of the same cardinality, instead of requiring a tuple
+- `Into2-8` now accept a product of the same cardinality, instead of requiring a tuple
 - `CoProduct2-8#project` now return generalized products
 - `Choice2-8#project` return tuples
 
diff --git a/src/main/java/com/jnape/palatable/lambda/monoid/Difference.java b/src/main/java/com/jnape/palatable/lambda/monoid/Difference.java
@@ -0,0 +1,53 @@
+package com.jnape.palatable.lambda.monoid;
+
+import com.jnape.palatable.lambda.functions.Fn1;
+
+import java.util.Collections;
+import java.util.HashSet;
+
+import static com.jnape.palatable.lambda.functions.builtin.fn1.Distinct.distinct;
+import static com.jnape.palatable.lambda.functions.builtin.fn1.Empty.empty;
+import static com.jnape.palatable.lambda.functions.builtin.fn2.Filter.filter;
+import static com.jnape.palatable.lambda.functions.builtin.fn2.ToCollection.toCollection;
+
+public final class Difference<A> implements Monoid<Iterable<A>> {
+
+    private static final Difference INSTANCE = new Difference();
+
+    private Difference() {
+    }
+
+    @Override
+    public Iterable<A> identity() {
+        return Collections::emptyIterator;
+    }
+
+
+    @Override
+    public Iterable<A> apply(Iterable<A> xs, Iterable<A> ys) {
+        return () -> {
+            if (empty(xs))
+                return xs.iterator();
+
+            if (empty(ys))
+                return distinct(xs).iterator();
+
+            //todo: pre-order dfs fold the expression tree to make stack-safe
+            HashSet<A> uniqueYs = toCollection(HashSet::new, ys);
+            return distinct(filter(a -> !uniqueYs.contains(a), xs)).iterator();
+        };
+    }
+
+    @SuppressWarnings("unchecked")
+    public static <A> Difference<A> difference() {
+        return INSTANCE;
+    }
+
+    public static <A> Fn1<Iterable<A>, Iterable<A>> difference(Iterable<A> xs) {
+        return Difference.<A>difference().apply(xs);
+    }
+
+    public static <A> Iterable<A> difference(Iterable<A> xs, Iterable<A> ys) {
+        return difference(xs).apply(ys);
+    }
+}
diff --git a/src/test/java/com/jnape/palatable/lambda/monoid/DifferenceTest.java b/src/test/java/com/jnape/palatable/lambda/monoid/DifferenceTest.java
@@ -0,0 +1,44 @@
+package com.jnape.palatable.lambda.monoid;
+
+import com.jnape.palatable.lambda.functions.Fn1;
+import com.jnape.palatable.traitor.annotations.TestTraits;
+import com.jnape.palatable.traitor.runners.Traits;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import testsupport.traits.EmptyIterableSupport;
+import testsupport.traits.FiniteIteration;
+import testsupport.traits.ImmutableIteration;
+import testsupport.traits.InfiniteIterableSupport;
+import testsupport.traits.Laziness;
+
+import static com.jnape.palatable.lambda.monoid.Difference.difference;
+import static java.util.Arrays.asList;
+import static java.util.Collections.emptyList;
+import static java.util.Collections.singletonList;
+import static org.junit.Assert.assertThat;
+import static testsupport.matchers.IterableMatcher.isEmpty;
+import static testsupport.matchers.IterableMatcher.iterates;
+
+@RunWith(Traits.class)
+public class DifferenceTest {
+
+    @TestTraits({Laziness.class, InfiniteIterableSupport.class, EmptyIterableSupport.class, FiniteIteration.class, ImmutableIteration.class})
+    public Fn1<Iterable<Integer>, Iterable<Integer>> testSubject() {
+        return Difference.<Integer>difference().flip().apply(asList(1, 2, 3));
+    }
+
+    @Test
+    public void identity() {
+        assertThat(difference().identity(), isEmpty());
+    }
+
+    @Test
+    public void semigroup() {
+        assertThat(difference(emptyList(), emptyList()), isEmpty());
+        assertThat(difference(asList(1, 2, 3), emptyList()), iterates(1, 2, 3));
+        assertThat(difference(asList(1, 2, 2, 3), emptyList()), iterates(1, 2, 3));
+        assertThat(difference(emptyList(), asList(1, 2, 3)), isEmpty());
+        assertThat(difference(asList(1, 2, 3), singletonList(4)), iterates(1, 2, 3));
+        assertThat(difference(asList(1, 2, 3), asList(2, 4)), iterates(1, 3));
+    }
+}
