about summary refs log tree commit diff
path: root/users/wpcarro/emacs/.emacs.d/wpc/bag.el
diff options
context:
space:
mode:
authorVincent Ambo <mail@tazj.in>2021-12-13T22·51+0300
committerVincent Ambo <mail@tazj.in>2021-12-13T23·15+0300
commit019f8fd2113df4c5247c3969c60fd4f0e08f91f7 (patch)
tree76a857f61aa88f62a30e854651e8439db77fd0ea /users/wpcarro/emacs/.emacs.d/wpc/bag.el
parent464bbcb15c09813172c79820bcf526bb10cf4208 (diff)
parent6123e976928ca3d8d93f0b2006b10b5f659eb74d (diff)
subtree(users/wpcarro): docking briefcase at '24f5a642' r/3226
git-subtree-dir: users/wpcarro
git-subtree-mainline: 464bbcb15c09813172c79820bcf526bb10cf4208
git-subtree-split: 24f5a642af3aa1627bbff977f0a101907a02c69f
Change-Id: I6105b3762b79126b3488359c95978cadb3efa789
Diffstat (limited to 'users/wpcarro/emacs/.emacs.d/wpc/bag.el')
-rw-r--r--users/wpcarro/emacs/.emacs.d/wpc/bag.el71
1 files changed, 71 insertions, 0 deletions
diff --git a/users/wpcarro/emacs/.emacs.d/wpc/bag.el b/users/wpcarro/emacs/.emacs.d/wpc/bag.el
new file mode 100644
index 000000000000..38a09d94f900
--- /dev/null
+++ b/users/wpcarro/emacs/.emacs.d/wpc/bag.el
@@ -0,0 +1,71 @@
+;;; bag.el --- Working with bags (aka multi-sets) -*- lexical-binding: t -*-
+
+;; Author: William Carroll <wpcarro@gmail.com>
+;; Version: 0.0.1
+;; URL: https://git.wpcarro.dev/wpcarro/briefcase
+;; 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 bag 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 'number)
+
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+;; Library
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+
+(cl-defstruct bag xs)
+
+(defun bag-update (f xs)
+  "Call F on alist in XS."
+  (let ((ys (bag-xs xs)))
+    (setf (bag-xs xs) (funcall f ys))))
+
+(defun bag-new ()
+  "Create an empty bag."
+  (make-bag :xs (al-new)))
+
+(defun bag-contains? (x xs)
+  "Return t if XS has X."
+  (al-has-key? x (bag-xs xs)))
+
+;; TODO: Tabling this for now since working with structs seems to be
+;; disappointingly difficult.  Where is `struct-update'?
+;; (defun bag-add (x xs)
+;;   "Add X to XS.")
+
+;; TODO: What do we name delete vs. remove?
+;; (defun bag-remove (x xs)
+;;   "Remove X from XS.
+;; This is a no-op is X doesn't exist in XS.")
+
+(defun bag-from-list (xs)
+  "Map a list of `XS' into a bag."
+  (->> xs
+       (list-reduce
+        (bag-new)
+        (lambda (x acc)
+          (bag-add x 1 #'number-inc acc)))))
+
+(provide 'bag)
+;;; bag.el ends here