3 files changed, 226 insertions, 0 deletions
diff --git a/users/wpcarro/emacs/pkgs/set/default.nix b/users/wpcarro/emacs/pkgs/set/default.nix
new file mode 100644
index 000000000000..319ba9274423
--- /dev/null
+++ b/users/wpcarro/emacs/pkgs/set/default.nix
@@ -0,0 +1,32 @@
+{ pkgs, depot, ... }:
+
+let
+  set = pkgs.callPackage
+    ({ emacsPackages }:
+      emacsPackages.trivialBuild {
+        pname = "set";
+        version = "1.0.0";
+        src = ./set.el;
+        packageRequires =
+          (with emacsPackages; [
+            dash
+            ht
+          ]) ++
+          (with depot.users.wpcarro.emacs.pkgs; [
+            struct
+          ]);
+      })
+    { };
+
+  emacs = (pkgs.emacsPackagesFor pkgs.emacs28).emacsWithPackages (epkgs: [
+    epkgs.dash
+    set
+  ]);
+in
+set.overrideAttrs (_old: {
+  doCheck = true;
+  checkPhase = ''
+    ${emacs}/bin/emacs -batch \
+      -l ert -l ${./tests.el} -f ert-run-tests-batch-and-exit
+  '';
+})
diff --git a/users/wpcarro/emacs/pkgs/set/set.el b/users/wpcarro/emacs/pkgs/set/set.el
new file mode 100644
index 000000000000..2d6e14917a45
--- /dev/null
+++ b/users/wpcarro/emacs/pkgs/set/set.el
@@ -0,0 +1,116 @@
+;;; set.el --- Working with mathematical sets -*- lexical-binding: t -*-
+
+;; Author: William Carroll <wpcarro@gmail.com>
+;; Version: 0.0.1
+;; Package-Requires: ((emacs "24.3"))
+
+;;; Commentary:
+;; The set data structure is a collection that deduplicates its elements.
+
+;;; Code:
+
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+;; Dependencies
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+
+(require 'cl-lib)
+(require 'dash)
+(require 'ht) ;; friendlier API for hash-tables
+(require 'struct)
+
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+;; Wish List
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+
+;; - TODO: Support enum protocol for set.
+;; - TODO: Prefer a different hash-table library that doesn't rely on mutative
+;;   code.
+
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+;; Library
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+
+(cl-defstruct set xs)
+
+(defun set-from-list (xs)
+  "Create a new set from the list XS."
+  (make-set :xs (->> xs
+                     (-map (lambda (x) (cons x nil)))
+                     ht-from-alist)))
+
+(defun set-new (&rest args)
+  "Create a new set from ARGS."
+  (set-from-list args))
+
+(defun set-to-list (xs)
+  "Map set XS into a list."
+  (->> xs
+       set-xs
+       ht-keys))
+
+(defun set-add (x xs)
+  "Add X to set XS."
+  (struct-update set
+                 xs
+                 (lambda (table)
+                   (let ((table-copy (ht-copy table)))
+                     (ht-set table-copy x nil)
+                     table-copy))
+                 xs))
+
+;; TODO: Ensure all `*/reduce' functions share the same API.
+(defun set-reduce (acc f xs)
+  "Return a new set by calling F on each element of XS and ACC."
+  (->> xs
+       set-to-list
+       (-reduce-from (lambda (acc x) (funcall f x acc)) acc)))
+
+(defun set-intersection (a b)
+  "Return the set intersection between A and B."
+  (set-reduce (set-new)
+              (lambda (x acc)
+                (if (set-contains? x b)
+                    (set-add x acc)
+                  acc))
+              a))
+
+(defun set-count (xs)
+  "Return the number of elements in XS."
+  (->> xs
+       set-xs
+       ht-size))
+
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+;; Predicates
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+
+(defun set-empty? (xs)
+  "Return t if XS has no elements in it."
+  (= 0 (set-count xs)))
+
+(defun set-contains? (x xs)
+  "Return t if set XS has X."
+  (ht-contains? (set-xs xs) x))
+
+;; TODO: Prefer using `ht.el' functions for this.
+(defun set-equal? (a b)
+  "Return t if A and B share the name members."
+  (ht-equal? (set-xs a)
+             (set-xs b)))
+
+(defun set-distinct? (a b)
+  "Return t if A and B have no shared members."
+  (set-empty? (set-intersection a b)))
+
+(defun set-superset? (a b)
+  "Return t if A has all of the members of B."
+  (->> b
+       set-to-list
+       (-all? (lambda (x) (set-contains? x a)))))
+
+(defun set-subset? (a b)
+  "Return t if each member of set A is present in set B."
+  (set-superset? b a))
+
+(provide 'set)
+;;; set.el ends here
diff --git a/users/wpcarro/emacs/pkgs/set/tests.el b/users/wpcarro/emacs/pkgs/set/tests.el
new file mode 100644
index 000000000000..3544364897d2
--- /dev/null
+++ b/users/wpcarro/emacs/pkgs/set/tests.el
@@ -0,0 +1,78 @@
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+;; Dependencies
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+
+(require 'ert)
+(require 'dash)
+(require 'set)
+
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+;; Tests
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+
+(ert-deftest set-from-list ()
+  (equal '(1 2 3)
+         (->> '(1 2 3 1 2 3)
+              set-from-list
+              set-to-list)))
+
+(ert-deftest set-distinct? ()
+  (and
+   (set-distinct? (set-new 'one 'two 'three)
+                  (set-new 'a 'b 'c))
+   (not
+    (set-distinct? (set-new 1 2 3)
+                   (set-new 3 4 5)))
+   (not
+    (set-distinct? (set-new 1 2 3)
+                   (set-new 1 2 3)))))
+
+(ert-deftest set-equal? ()
+  (and
+   (set-equal? (set-new 'a 'b 'c)
+               (set-new 'x 'y 'z))
+   (set-equal? (set-new 'a 'b 'c)
+               (set-new 'a 'b))
+   (set-equal? (set-new 'a 'b 'c)
+               (set-new 'a 'b 'c))))
+
+(ert-deftest set-intersection ()
+  (set-equal? (set-new 2 3)
+              (set-intersection (set-new 1 2 3)
+                                (set-new 2 3 4))))
+
+(ert-deftest set-to/from-list ()
+  (equal '(1 2 3)
+         (->> '(1 1 2 2 3 3)
+              set-from-list
+              set-to-list)))
+
+(ert-deftest set-subset? ()
+  (let ((primary-colors (set-new "red" "green" "blue")))
+    ;; set-subset?
+    (and
+     (set-subset? (set-new "black" "grey")
+                  primary-colors)
+     (set-subset? (set-new "red")
+                  primary-colors))))
+
+(ert-deftest set-subset/superset? ()
+  (let ((primary-colors (set-new "red" "green" "blue")))
+    ;; set-subset?
+    (and
+     (not (set-superset? primary-colors
+                         (set-new "black" "grey")))
+     (set-superset? primary-colors
+                    (set-new "red" "green" "blue"))
+     (set-superset? primary-colors
+                    (set-new "red" "blue")))))
+
+(ert-deftest set-empty? ()
+  (and
+   (set-empty? (set-new))
+   (set-empty? (set-new 1 2 3))))
+
+(ert-deftest set-count ()
+  (and
+   (= 0 (set-count (set-new)))
+   (= 2 (set-count (set-new 1 1 2 2)))))