1 files changed, 78 insertions, 0 deletions
diff --git a/users/wpcarro/emacs/pkgs/bag/bag.el b/users/wpcarro/emacs/pkgs/bag/bag.el
new file mode 100644
index 000000000000..502f5672536e
--- /dev/null
+++ b/users/wpcarro/emacs/pkgs/bag/bag.el
@@ -0,0 +1,78 @@
+;;; bag.el --- Working with bags (aka multi-sets) -*- lexical-binding: t -*-
+
+;; Author: William Carroll <wpcarro@gmail.com>
+;; Version: 0.0.1
+;; Package-Requires: ((emacs "24.3"))
+
+;;; Commentary:
+;; What is a bag?  A bag should be thought of as a frequency table.  It's a way
+;; to convert a list of something into a set that allows duplicates.  Isn't
+;; allowing duplicates the whole thing with Sets?  Kind of.  But the interface
+;; of Sets is something that bags resemble, so multi-set isn't as bad of a name
+;; as it may first seem.
+;;
+;; If you've used Python's collections.Counter, the concept of a bag should be
+;; familiar already.
+;;
+;; Interface:
+;; - add        :: x -> Bag(x) -> Bag(x)
+;; - remove     :: x -> Bag(x) -> Bag(x)
+;; - union      :: Bag(x) -> Bag(x) -> Bag(x)
+;; - difference :: Bag(x) -> Bag(x) -> Bag(x)
+
+;;; Code:
+
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+;; Dependencies
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+
+(require 'al)
+(require 'list)
+
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+;; Library
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+
+(cl-defstruct bag xs)
+
+(defun bag-new ()
+  "Create an empty bag."
+  (make-bag :xs (al-new)))
+
+(defun bag-from-list (xs)
+  "Map a list of `XS' into a bag."
+  (->> xs
+       (list-reduce (bag-new) #'bag-add)))
+
+(defun bag-add (x xs)
+  "Add X to XS."
+  (if (bag-contains? x xs)
+      (struct-update
+       bag xs (lambda (xs) (al-update x (lambda (x) (+ 1 x)) xs)) xs)
+    (struct-update bag xs (lambda (xs) (al-set x 1 xs)) xs)))
+
+(defun bag-remove (x xs)
+  "Remove X from XS.
+This is a no-op is X doesn't exist in XS."
+  (when (bag-contains? x xs)
+    (struct-update bag xs (lambda (xs) (al-delete x xs)) xs)))
+
+(defun bag-count (x xs)
+  "Return the number of occurrences of X in XS."
+  (al-get x (bag-xs xs) 0))
+
+(defun bag-total (xs)
+  "Return the total number of elements in XS."
+  (->> (bag-xs xs)
+       (al-reduce 0 (lambda (_key v acc) (+ acc v)))))
+
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+;; Predicates
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+
+(defun bag-contains? (x xs)
+  "Return t if XS has X."
+  (al-has-key? x (bag-xs xs)))
+
+(provide 'bag)
+;;; bag.el ends here