404 - PurelyFunctional.tv Newsletter

00 Boolean combinators.md

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.

Please submit your solutions as comments on this gist.

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))

@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!

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

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?