Closures of sets

Some operations are common in mathematical reasoning, but are not traditionally used in programming, even when they make sense. I stumbled on one of these recently: I described something as the closure of a set under an operation, and then sought some other way to compute it, because the mathematical description didn't sound like an implementation. After a few minutes I realized there was no reason it shouldn't be:

(defn closure-unary "Closure of a set under a function." [f xs]
  (loop [done #{}
	 pending xs]
    (if (empty? pending)
      done
      (let [x (first pending)]
        (if (contains? done x)
	  (recur done (rest pending))
	  (recur (conj done x) (cons (f x) (rest pending))))))))

user=> (closure-unary - (range 3))
#{0 1 2 -2 -1}
user=> (closure-unary #(mod (inc %) 10) [0])
#{0 1 2 3 4 5 6 7 8 9}
user=> (defn collatz [n] (if (even? n) (quot n 2) (inc (* n 3))))
#'user/collatz
user=> (closure-unary collatz [27])
#{160 1 161 577 2 1154 1186 322 866 2051 35 4 2308 484 1732 5 3077
 325 4102 70 3238 71 103 167 263 8 40 488 4616 41 137 233 425 10
 6154 106 650 107 395 1132 364 46 2158 142 206 334 526 2734 47 175
 719 911 16 9232 80 976 433 593 82 242 274 466 754 850 1619 20 244
 1300 1780 53 182 214 310 502 566 790 23 1079 1367 7288 184 1336
 121 377 122 4858 890 27 91 155 251 283 92 124 1276 412 3644 668
 700 61 2429 445 62 94 350 1438 638 1822 958 31 319 479}

That was the version I wanted, but closure under a binary operator is probably more common:

(defn closure-binary "Closure of a set under a binary operator." [f xs]
  (loop [done #{}
	 pending xs]
    (if (empty? pending)
      done
      (let [x (first pending)]
	(if (contains? done x)
	  (recur done (rest pending))
	  (recur (conj done x)
		 (concat (map #(f x %) done)
			 (map #(f % x) done) ;in case it's not associative
			 (list (f x x))
			 (rest pending))))))))

user=> (closure-binary #(not (or %1 %2)) [false])
#{true false}
user=> (closure-binary #(mod (- %1 %2) 11) [1])
#{0 1 2 3 4 5 6 7 8 9 10}

The two variants are identical except in how they generate new elements. The common part could be factored out...

(defn closure* "Closure of a set under a function generating new elements:
(children element old-elements) should return a seq of elements to add."
  [children xs]
  (loop [done #{}
	 pending xs]
    (if (empty? pending)
      done
      (let [x (first pending)]
        (if (contains? done x)
	  (recur done (rest pending))
	  (recur (conj done x) (into (rest pending) (children x done))))))))

(defn closure-unary [f xs]
  (closure* (fn [x done] (list (f x))) xs))

(defn closure-binary [f xs]
  (closure* (fn [x done]
	       (concat (map #(f x %) done)
		       (map #(f % x) done)
		       (list (f x x))))
	    xs))

...but passing done to children is not very intuitive.

2 comments:

  1. Why "defn"? A (potentially infinite) lazy seq may be more to the point, no?

    ReplyDelete
  2. Yeah, it could be lazy, although to be useful on infinite sets it would need to explore breadth-first instead of depth-first. (The case I wanted it for was finite, though.)

    Why defn: because it's in Clojure?

    ReplyDelete

It's OK to comment on old posts.