blob: 2d6e14917a45b2a872487df95d7708c6253b4b99 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
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
|
