{{ message }}

Instantly share code, notes, and snippets.

# ericnormand/00 Boolean combinators.md

Created Nov 23, 2020

Boolean combinators

In the Clojure Tip above, I described a kind of Boolean combinator that lets us build complex rules out of simpler rules. Your task is to build those combinators. Please define:

```(defn rule-and
([])
([rule])
([rule1 rule2])
([rule1 rule2 & rules]))
(defn rule-or
([])
([rule])
([rule1 rule2])
([rule1 rule2 & rules]))
(defn rule-not [rule])```

Note that `rule-and` and `rule-or` are monoids and so they follow the monoid pattern.

For a bonus, write the functions `rule-if` (that implements the logical if arrow operator) and `rule-iff` (that implements the logical if and only if double-arrow operator). Not that `rule-if` is different from the programming `if` since it returns `true` if the condition is `false`.

### steffan-westcott commented Nov 23, 2020 • edited

```(defn rule-and
([]
(constantly true))
([rule]
rule)
([rule1 rule2]
(fn [& args]
(and (apply rule1 args) (apply rule2 args))))
([rule1 rule2 & rules]
(fn [& args]
(and (apply rule1 args) (apply rule2 args) (apply (apply rule-and rules) args)))))

(defn rule-or
([]
(constantly false))
([rule]
rule)
([rule1 rule2]
(fn [& args]
(or (apply rule1 args) (apply rule2 args))))
([rule1 rule2 & rules]
(fn [& args]
(or (apply rule1 args) (apply rule2 args) (apply (apply rule-or rules) args)))))

(defn rule-not [rule]
(complement rule))

(defn rule-if [p q]
(rule-or (rule-not p) q))

(defn rule-iff [p q]
(rule-and
(rule-if p q)
(rule-if q p)))```

Edit: Changed `rule-not` to use `complement`

### NPException commented Nov 23, 2020

```(defn rule-and
([] (constantly true))
([rule] rule)
([rule1 rule2]
#(and (apply rule1 %&) (apply rule2 %&)))
([rule1 rule2 & rules]
(apply rule-and (rule-and rule1 rule2) rules)))

(defn rule-or
([] (constantly false))
([rule] rule)
([rule1 rule2]
#(or (apply rule1 %&) (apply rule2 %&)))
([rule1 rule2 & rules]
(apply rule-or (rule-or rule1 rule2) rules)))

(defn rule-not [rule]
#(not (apply rule %&)))

(defn rule-if [rule-p rule-q]
(rule-or (rule-not rule-p) rule-q))

(defn rule-iff [rule-p rule-q]
(rule-and (rule-if rule-p rule-q)
(rule-if rule-q rule-p)))```

### mchampine commented Nov 24, 2020

Note: "every?/some identity" is a hack to pass and/or as functions because you can't take the value of a macro.

```(defn mk-rule-combo [dboo andor]
(fn thisfn
([] (fn [] dboo))
([rule] rule)
([rule1 rule2] (fn [& args] (andor (apply rule1 args) (apply rule2 args))))
([rule1 rule2 & rules] (apply thisfn (thisfn rule1 rule2) rules))))

(def rule-and (mk-rule-combo true #(every? identity %&)))
(def rule-or (mk-rule-combo false #(some identity %&)))
(defn rule-not [rule] (fn [& args] (not (apply rule args))))```

### steffan-westcott commented Nov 24, 2020 • edited

If we're willing to forego macro expansions (`and` and `or`), then we could have this:

```(defn junction [f rules]
(fn [& args]
(f identity (map #(apply % args) rules))))

(defn rule-and [& rules]
(junction every? rules))

(defn rule-or [& rules]
(junction some rules))

(def rule-not complement)

(defn rule-if [p q]
(rule-or (rule-not p) q))

(defn rule-iff [p q]
(rule-and (rule-if p q) (rule-if q p)))```

Edit: Updated `junction` to allow short-circuit evaluation

### steffan-westcott commented Nov 24, 2020

@mchampine Nice! As always, the discussion here leads to more elegant solutions. I suggest though looking at `constantly` to make a function which takes any number of arguments. `(fn [] dboo)` is a function which can only take exactly 0 arguments.

### miner commented Nov 24, 2020

You can use a macro to generate the similar rule-and and rule-or definitions.

```(defmacro mkrule [andor]
`(fn rule-name#
([] (constantly (~andor)))
([rule#] rule#)
([rule1# rule2#] (fn [& args#] (~andor (apply rule1# args#) (apply rule2# args#))))
([rule1# rule2# & rules#] (apply rule-name#
(rule-name# rule1# rule2#)
rules#))))

(def rule-and (mkrule and))

(def rule-or (mkrule or))```

### mchampine commented Nov 24, 2020

@steffan-westcott Yup, the zero args vs any-arity issue didn't show up in my testing, and I didn't notice the lack of generality. Nice solution with junction, btw.

@miner Cool! My macro-fu is weak, so I tend to take refuge in The First Rule of Clojure Macro Club. :) In practice, I wouldn't bother golfing this stuff down (original w/ duplication is fine) but I wanted to offer at least something different. It's fun and educational to see the other approaches here!

### KingCode commented Nov 25, 2020 • edited

Very interesting comments and elegant solutions above! I was working on a macro as well. Since `rule-and` and `rule-or` are the only ones where sugar-coating is handy, I ended up adding a number of combinators (`rule-xor`, `rule-oneof`, `rule-count` etc) to try and push the idea further.

I remember writing a logical rule-based system in Java years ago, due to complex specifications written in tabular form, where the outcome was predicated on some 30 rules, some of which required and some optional etc....The naive approach of spaghetti style nested if-else junk would have been a nightmare. This exercise reminds me of that experience (but much more fun and less work:)

```(defn monoid* [init body]
`(fn f#
([]
(fn [& ~'xs] ~init))
([~'r]
(fn [& ~'xs] (~body (apply ~'r ~'xs))))
([~'r1 ~'r2]
(fn [& ~'xs] (~body(apply ~'r1 ~'xs) (apply ~'r2 ~'xs))))
([~'r1 ~'r2 & ~'rs]
(fn [& ~'xs]
(~body(apply ~'r1 ~'xs)
(~body (apply ~'r2 ~'xs)
(apply (apply f# ~'rs) ~'xs)))))))

(defn ->1+2ary [ary-1 ary-2]
`(fn ([~'x] (~ary-1 ~'x))
([~'x ~'y] (~ary-2 ~'x ~'y))))

(defmacro defmonoid
([rule-name-sym init cdecl]
`(def ~rule-name-sym  ~(monoid* init cdecl)))
([rule-name-sym init ary1-body ary2-body]
`(def ~rule-name-sym ~(monoid* init (->1+2ary ary1-body
ary2-body)))))
;; utilities for rule counting combinators
(defn ->bit [bool-or-bit]
(cond
(= 0 bool-or-bit) 0
(number? bool-or-bit) bool-or-bit
bool-or-bit 1
:else 0))

(defn +bool
([] 0)
([x] (+ (->bit x)))
([x y]
(+ (->bit x) (->bit y))))

;; COMBINATORS
(defmonoid rule-and true and)

(defmonoid rule-or false or)

(def rule-not complement)

(defn rule-if [p q]
(rule-or (rule-not p) q))

(defn rule-iff [p q]
(rule-and (rule-if p q) (rule-if q p)))

(defn rule-xor [p q]
(rule-and (rule-or p q) (rule-not (rule-and p q))))

(defmonoid rule-oneof (comp boolean identity) identity
#(= 1 (+ (->bit %) (->bit %2))))

;; A combinator yielding the number of satisfied rules.
;; Each argument rule is a boolean predicate, or results are undetermined.
(defmonoid rule-count* (+bool) +bool)

;; Same as rule-count*, but rule return types are auto-converted to booleans.
(defn rule-count [& rules]
(->> rules (map #(comp boolean %))
(apply rule-count*)))

;; Yields a rule returning the result of applying 'pred to the number
;; of satisfied rules; 'rules are wrapped/converted to boolean predicates
(defn rule-filter-count [pred rules]
(let [cmbtr (apply rule-count rules)]
(fn [& xs]
(apply (comp pred cmbtr) xs))))

(defn rule-at-least [n & rules]
(rule-filter-count #(<= n %) rules))

(defn rule-at-most [n & rules]
(rule-filter-count #(<= % n) rules))

(defn rule-exactly [n & rules]
(rule-filter-count #(= n %) rules))

;; tests
(-> (rule-and odd? #(< 2 %) #(< % 6))
(map (range 2 7))) ;; => (false, true, false, true, false)

(-> (rule-or even? #(zero? (rem % 5)))
(map [2 7 15 300])) ;;=> (true false true true)

(-> (rule-if #(zero? (rem % 4)) even?)
(map [10 16 3])) ;;=> (true true true)

(-> (rule-iff #(zero? (rem % 2)) even?)
(map (range 4))) ;;=> (true true true true)

(-> (rule-xor even? odd?)
(map (range 4))) ;;=> (true true true true)

(-> (rule-xor #(zero? (rem % 5)) #(zero? (rem % 3)))
(map '(1 2 3 5 10 15 25 30)))
;;=> (false false true true true false true false)

(-> (rule-oneof :berlin :rome :new-york)
(map '({:berlin true} {:rome true} {:new-york :work :rome :home})))
;;=> (true true false)

(-> (rule-oneof :berlin :rome :new-york)
(map '({} {:rome :ok} {:new-york :work :rome :home})))
;;=> (false true false)

(-> (rule-at-least 2 :berlin :rome :new-york)
(map '({:berlin :sales} {:new-york :home :rome :overseas} {})))
;;=> (false true false
(-> (rule-at-most 2 :berlin :rome :new-york)
(map '({:berlin :away :rome :summer} {:rome :summer :berlin 1 :new-york 2} {:new-york :sales})))
;;=> (true false true)

(def can-vote? (rule-and
(rule-and #(<= 18 (:age %)) :citizen?)
(rule-at-least 1 :affiliated? :registered?)))

(->> '({:age 17 :citizen? :acquired} {:age 40 :citizen? :at-birth :registered? :yes})
(map can-vote?)) ;;=> (false true)```

EDITS: some refactoring and shameless copy of better ideas: passing `and`/`or` directly to the macro from @miner (passing a macro to a fn is a no-no but a macro will take anything), and using `complement` for `rule-not` from @steffan-westcott

### KingCode commented Nov 26, 2020 • edited

This is just a thought, but while "testing" rule-if/iff, I remembered that these are tautologies, i.e. that timeless properties such as `(rule-iff even? (complement odd?))` and `(rule-if #(= 0 (rem % 4)) even?)` are always true.

In the limited experience I had with spec and test.check, I have always struggled to identify (timeless) properties: `rule-if` would probably be a great way to test-discover properties using test.check generators.

Has anyone here tried this before?